Cod sursa(job #214244)

Utilizator savimSerban Andrei Stan savim Data 13 octombrie 2008 16:13:57
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <stdio.h>
#define maxl 100010

int n,m,i,j,k,last,p,q,rez,max,e1,e2,w;
int a[maxl],v[maxl];
int trie[21 * maxl][2];

void tr() {
     p = 0;
     for (i = 0; i <= 20; i++) {
         k = v[w] & (1<< (20 - i));
         if (k != 0) k = 1;

         if (trie[p][k] == 0) {
            trie[p][k] = ++last;
            p = last;
         }
         else p = trie[p][k];
     }
}

void dfs(int p, int q, int x, int y, int pas) {

     if (trie[p][0] != 0) {
        if (trie[q][1] != 0) {
            rez += 1 << (20 - pas);
            dfs(trie[p][0], trie[q][1], x, y + 1 << (20 - pas), pas + 1);
            rez -= 1 << (20 - pas);
        }
        dfs(trie[p][0], trie[q][0], x, y, pas + 1);
     }

     if (trie[p][1] != 0)
     {
         if (trie[q][0] != 0) {
            rez += 1 << (20 - pas);
            dfs(trie[p][1], trie[q][0], x + 1 << (20 - pas), y, pas + 1);
            rez -= 1 << (20 - pas);
         }
         dfs(trie[p][0], trie[q][0], x, y, pas + 1);
     }

     if (rez > max) {
        max = rez;
        e1 = x;
        e2 = y;
     }
}

int poz(int x) {
    for (i = 1; i <= n; i++)
        if (v[i] == x) return i;
}
    

int main() {
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    
    scanf("%d", &n);
    for (w = 1; w <= n; w++) {
        scanf("%d", &a[w]);
        v[w] = v[w - 1] ^ a[w];
        tr();
    }

    rez = 0; max = 0;
    dfs(0,0,0,0,0);

    p = poz(e1); q = poz(e2);
    if (p > q) {
       rez = p; p = q; q = rez;
    }

    printf("%d %d %d\n", max, p + 1, q);

    return 0;
}