Cod sursa(job #214277)

Utilizator savimSerban Andrei Stan savim Data 13 octombrie 2008 18:36:12
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

#define maxl 100010

int n,m,i,j,k,last,p,q,rez,val,w,pas,x,y;
int a[maxl],v[maxl];
int fol [1 << 22];
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 > val) {
        val = rez;
        for (i = 0; i <= 20; i++)
            sol[i] = val & 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 (w = n; w >= 1; w--)
        fol[v[w]] = w;

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

    rez = 0; val = 0; pas = -1; x = 0; y = 0;
    dfs(0,0);

    x = 2147000000; y = x;
    for (i = 1; i <= n; i++) {
        k = val ^ v[i];
        if (fol[k] && fol[k] < i) {
           y = i;
           break;
        }
    }
    for (i = 1; i <= y; i++)
        if ((val ^ v[y]) == v[i]) x = i; 
    
    printf("%d %d %d\n", val, x + 1, y);

    return 0;
}