Cod sursa(job #1774463)

Utilizator DevilOnFieldTudor Horia Niculescu DevilOnField Data 8 octombrie 2016 23:35:03
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include<stdio.h>

#define DPTMAX 21
FILE *in, *out;

int maxxo = -1, maxst, maxdr;

struct nod
{
    nod *ze = NULL, *un = NULL;
    int ord = 3;
};

void baga(int ilbag, int turn, nod *incep) {
    int e = 1 << (DPTMAX - 1);
    for(int i = DPTMAX; i > 0; i--) {
        if(e > ilbag) {
            if(incep->ze == NULL) {
                incep->ze = new nod;
            }
            incep = incep->ze;
            //printf("0");
        } else {
            if(incep->un == NULL) {
                incep->un = new nod;
            }
            //printf("1");
            incep = incep->un;
            ilbag = ilbag - e;
        }
        e = (e >> 1);
    }
    //printf("\n");
    incep->ord = turn;
}

void findopt(int ilam, nod *start, int tura)
{
    int kanker[23], ilfac = 0;
    int e = 1 << (DPTMAX - 1);
    for(int i = DPTMAX; i > 0; i--) {
        if(e > ilam) {
            kanker[i] = 0;
        } else {
            kanker[i] = 1;
            ilam -= e;
        }
        e = (e >> 1);
    }
    for(int i = DPTMAX; i > 0; i--) {
        ilfac = (ilfac << 1);
        if(kanker[i] == 0) {
            if(start->un != NULL) {
                ilfac++;
                start = start->un;
            } else {
                start = start->ze;
            }
        } else {
            if(start->ze != NULL) {
                ilfac++;
                start = start->ze;
            } else {
                start = start->un;
            }
        }
    }
    if(ilfac > maxxo) {
        maxxo = ilfac;
        maxst = start->ord + 1;
        maxdr = tura;
    }
}


int main ()
{
    int n;

    in = fopen("xormax.in", "r");
    out = fopen("xormax.out", "w");

    fscanf(in, "%d", &n);

    int v[100000];
    for(int i = 0; i < n; i++) {
        fscanf(in, "%d", &v[i]);
    }

    nod *start;
    start = new nod;
    //printf("%d", start->ord);
    baga(0, 0, start);

    int xortot = 0;
    for(int i = 0; i < n; i++) {
        xortot = (xortot ^ v[i]);
        findopt(xortot, start, i + 1);
        baga(xortot, i + 1, start);
    }

    fprintf(out, "%d %d %d\n", maxxo, maxst, maxdr);

    fclose(in);
    fclose(out);

    return 0;
}