Cod sursa(job #214253)

Utilizator savimSerban Andrei Stan savim Data 13 octombrie 2008 17:59:46
Problema Xor Max Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <stdio.h>
#define maxl 100010

int n,m,i,j,k,last,p,q,rez,max,e1,e2,w,pas,x,y;
int a[maxl],v[maxl];
int trie[50 * maxl][2];
int p2[20], sol[20];

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) {
     pas++;

     if (rez > max) {
        max = rez;
        e1 = x;
        e2 = y;
        int i;
        for (i = 0; i <= 20; i++)
            sol[i] = max & p2[i];
     }

     if (rez < sol[pas]) {
        pas--;
        return;
     }

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

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


     pas--;
}

int poz(int x) {
    for (i = 0; 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();
    }
    w = 0; tr();

    for (i=0; i<=20; i++)
        p2[i] = 1 << (20 - i);

    rez = 0; max = 0; pas = -1; x = 0; y = 0;
    dfs(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;
}