Cod sursa(job #1222730)

Utilizator ZenusTudor Costin Razvan Zenus Data 24 august 2014 10:15:30
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <cstdio>
#include <algorithm>
#include <climits>

using namespace std;

#define TMAX ((1<<22)+7)
#define NMAX 100007

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

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);

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

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

while (MAX)
MAX>>=1,++depth;

Insert(1,depth);

for (i=1,MAX=-INT_MAX;i<=N;++i)
{
    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;
}