Cod sursa(job #2054649)

Utilizator eudoarAlbertoAlberto Nikolas Bombardieru eudoarAlberto Data 2 noiembrie 2017 11:37:00
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<bits/stdc++.h>
using namespace std;
int best=-1,start,stop;
struct trie
{
    int cnt,pos;
    trie *sons[3];
    trie()
    {
        cnt=0;
        pos=0;
        for(int i=0;i<=2;i++)
            sons[i]=NULL;
    }
}*root=new trie();

inline void Query(trie *node,int x,int pos,int vl,int i)
{
    if(pos==-1)
    {
        if(vl>best)
        {
            best=vl;
            start=node->pos+1;
            stop=i;
        }
        return;
    }
    int y=x&(1<<pos);
    if(y) y=1;
        else y=0;
    int z=1-y;
    if(!node->sons[z])
    {
         Query(node->sons[y],x,pos-1,vl,i);
    }
        else
    Query(node->sons[z],x,pos-1,vl+(1<<pos),i);
}

inline void Insert(trie* node,int x,int pos,int i)
{
    if(pos==-1)
    {
        node->pos=i;
        return;
    }
    int y=x&(1<<pos);
    if(y) y=1;
        else y=0;
    if(node->sons[y]==NULL) node->sons[y]=new trie();
    node->sons[y]->pos=i;
    node->sons[y]->cnt++;
    Insert(node->sons[y],x,pos-1,i);
}
int n,val,x;
int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d",&n);
    Insert(root,0,21,0);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&val);
        x=x^val;
        Query(root,x,21,0,i);
        Insert(root,x,21,i);
    }
    printf("%d %d %d\n",best,start,stop);
    return 0;
}