Cod sursa(job #1919085)

Utilizator LucianTLucian Trepteanu LucianT Data 9 martie 2017 17:54:55
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>
#define maxN 100005
#define sigma 2
using namespace std;
struct trie
{
    int ind;
    trie *fiu[sigma];
    trie()
    {
        fiu[0]=fiu[1]=0;
        ind=0;
    }
}*root=new trie();
int s[maxN],v[maxN];
int n,i,j,x,sol=-1,st,dr,maxx,loga;
void _insert(trie *nod,int x,int ind,int lim=21)
{
    if(lim==-1){
        nod->ind=ind;
        return;
    }
    int val=(x>>lim)&1;
    if(nod->fiu[val]==NULL)
        nod->fiu[val]=new trie();
    _insert(nod->fiu[val],x,ind,lim-1);
}
int query(trie *nod,int x,int lim=21)
{
    if(lim==-1)
        return nod->ind;
    int val=(x>>lim)&1;
    if(nod->fiu[1-val]!=NULL)
        query(nod->fiu[1-val],x,lim-1);
    else query(nod->fiu[val],x,lim-1);
}
int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d",&n);
    _insert(root,0,0);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x);
        s[i]=s[i-1]^x;
        int pos=query(root,s[i]);
        _insert(root,s[i],i);
        if(sol<(s[i]^s[pos]))
        {
            sol=s[i]^s[pos];
            st=pos+1;
            dr=i;
        }
    }
    printf("%d %d %d",sol,st,dr);
    return 0;
}