Cod sursa(job #769611)

Utilizator test_666013Testez test_666013 Data 20 iulie 2012 10:51:38
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
#define MAX 100001

struct trie{
    struct trie *f[2];
    int idx; }*t;

int n,s[MAX];

void add(int x,int idx){
    trie *g = t;
    int urm;
    for(int i=20;i>=0;i--)
    {
        if(x & (1<<i))urm = 1; else urm = 0;
        if(g->f[urm] == 0)g->f[urm] = new trie;
        g=g->f[urm];
    }
        g->idx = idx;
}

int find(int x){
    trie *g = t;
    int urm;
    for(int i=20;i>=0;i--)
    {
        if(x & (1<<i))urm = 0; else urm = 1;
        if(g->f[urm] != 0)g = g->f[urm]; else g = g->f[(!urm)];
    }
        return g->idx;
}

int main(){
    int x,y, p,u,bst;
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    t = new trie;

        scanf("%d",&n);
        scanf("%d",&x);
        p = u = 1;
        bst = s[1] = x;
        add(x,1);

        for(int i=2;i<=n;i++)
        {
            scanf("%d",&x);
            s[i] = s[i-1] ^ x;
            y = find(s[i]);
            if( (s[i] ^ s[y]) > bst)
            {
                p = y+1;
                u = i;
                bst = s[i] ^ s[y];
            }
            add(s[i],i);
        }
 //       printf("\n"); for(int i=1;i<=n;i++)printf("%d ",s[i]); printf("\n");
    printf("%d %d %d\n",bst,p,u);
    return 0;
}