Cod sursa(job #596578)

Utilizator SpiderManSimoiu Robert SpiderMan Data 17 iunie 2011 19:31:53
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
# include <cstdio>

const char *FIN = "xormax.in", *FOU = "xormax.out";
const int MAX_A = 1 << 22, MAX_N = 100002;

struct vec {
    int A;
    bool B;
};

vec V[MAX_A];
int X[MAX_N], N;

void update (int nod, int st, int dr) {
    if (dr == -1) {
        V[nod].A = st, V[nod].B = 1;
        return ;
    }
    update (X[st] & 1 << dr ? (nod << 1) + 1 : nod << 1, st, dr - 1);
    V[nod].B = V[nod << 1].B | V[(nod << 1) + 1].B;
}

int query (int nod, int st, int dr) {
    if (dr == -1) return V[nod].A;
    return query ((st & 1 << dr) && V[nod << 1].B == 1 || V[(nod << 1) + 1].B == 0 ? nod << 1 : (nod << 1) + 1, st, dr - 1);
}

int main (void) {
    freopen (FIN, "r", stdin);

    scanf ("%d", &N);
    for (int i = 1; i <= N; X[i++] ^= X[i - 1])
        scanf ("%d", X + i);
    update (1, 0, 20);
    int maxim = -1, st = 0, dr = 0;
    for (int i = 1; i <= N; ++i) {
        int poz = query (1, X[i], 20);
        if (maxim < (X[i] ^ X[poz]))
            maxim = X[i] ^ X[poz], st = poz + 1, dr = i;
        update (1, i, 20);
    }
    fprintf (fopen (FOU, "w"), "%d %d %d", maxim, st, dr);
}