Cod sursa(job #1589569)

Utilizator gbibBacotiu Gabi gbib Data 4 februarie 2016 10:37:00
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");

struct Trie{
    Trie *sons[2];
    int best;
    Trie ()
    {
        best=-1;
        sons[0]=sons[1]=NULL;
    }
};

Trie *root=new Trie();
void add(Trie *node, bool v[] ,int i,int ind)
{
    if(i<0)
    {
        if(ind>node->best)
            node->best=ind;
        return;
    }
    if(!node->sons[v[i]])
        node->sons[v[i]]=new Trie;
    add(node->sons[v[i]],v,i-1,ind);
}
int qu(Trie *node, bool v[],int i)
{
    if(i<0)
    {
        return node->best;
    }
    if(node->sons[!v[i]])
    {
        return qu(node->sons[!v[i]],v,i-1);
    }
    else if(node->sons[v[i]])
        return qu(node->sons[v[i]],v,i-1);
    return -1;
}
int xorsum[100005];
bool vc[24];
int main()
{int n,mx=0,i,x,j,p,u;
in>>n;
add(root,vc,0,0);
for(i=1;i<=n;i++)
{
    in>>x;
    xorsum[i]=(xorsum[i-1] ^ x);
    for(j=0;j<=20;j++)
    {
        vc[j]=(xorsum[i]&(1<<j));
    }
    add(root,vc,20,i);
    int ind= qu(root,vc,20);
    if((xorsum[i]^xorsum[ind])>mx)
    {
        mx=(xorsum[i]^xorsum[ind]);
        p=ind+1;
        u=i;
    }


}

out<<mx<<" "<<p<<" "<<u<<'\n';
    return 0;
}