Cod sursa(job #1222727)

Utilizator ZenusTudor Costin Razvan Zenus Data 24 august 2014 10:10:25
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define TMAX (1<<23)
#define depth 21
#define NMAX 100007

pair < int , bool > T[TMAX];
int f[NMAX];
int current,MAX,stop,start,i,N,X;

void Insert(int node,int step)
{
    T[node]=make_pair(i,true);

    if (step<0)
    return ;

    Insert(node*2+((f[i]&(1<<step))>=1),step-1);
}


int find(int node,int step)
{
    if (step<0) return T[node].first;

    int current=((f[i]&(1<<step))==0);

    current^=T[node*2+current].second^1;

    return find(node*2+current,step-1);
}

int main()
{
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);

scanf("%d",&N);
Insert(1,depth);

for (i=1;i<=N;++i)
{
    scanf("%d",&X);

    f[i]=f[i-1]^X;

    current=find(1,depth);

    if ((f[current]^f[i])>MAX)
    {
        MAX=f[current]^f[i];
        start=current+1;
        stop=i;
    }

    Insert(1,depth);
}

printf("%d %d %d\n",MAX,start,stop);

return 0;
}