Cod sursa(job #1887902)

Utilizator delta_wolfAndrei Stoica delta_wolf Data 21 februarie 2017 20:17:37
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <cstdio>
#include <vector>
using namespace std;
struct trie
{
    int ind,Next[2];
    trie(){
        ind=Next[1]=Next[0]=-1;
    }
} tr;
vector<trie> T;

int mx=-1,st,dr,i,l,B[35],n,c,act,sum,x,a;

int main(){
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d",&n);
    T.push_back( tr );
    act=0;
    for( i=0; i<31; ++i )
    {
        T.push_back( tr );
        T[ act ].Next[0]=T.size()-1;
        act=T.size()-1;
        T[ act ].ind = 0;
    }

    for( i=1; i<=n; ++i )
    {
        scanf("%d",&x);
        a ^= x;
        for( l=0; l<31; ++l )
            B[ l ]=0;
        c = a;
        l=0;
        while( c )
        {
            B[ l++ ] = c&1;
            c>>=1;
        }
        act=0;
        sum=0;
        for( l=30; l>=0; --l )
        {
            if( T[ act ].Next[ B[l]^1 ] != -1 )
            {
                sum ^= ( 1<<l );
                act = T[ act ].Next[ B[l]^1 ];
            }
            else
                act = T[ act ].Next[ B[l] ];
        }
        if( sum > mx )
        {
            mx = sum;
            st = T[ act ].ind+1;
            dr = i;
        }
        act=0;
        for( l=30; l>=0; --l )
        {
            if( T[ act ].Next[ B[l] ] == -1 )
            {
                T.push_back( tr );
                T[ act ].Next[ B[l] ] = T.size()-1;
            }
            act = T[ act ].Next[ B[l] ];
            T[act].ind = i;
        }
    }
    printf("%d %d %d\n",mx,st,dr);
    return 0;
}