Cod sursa(job #1980088)

Utilizator refugiatBoni Daniel Stefan refugiat Data 12 mai 2017 11:26:41
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream si("xormax.in");
ofstream so("xormax.out");
struct trie
{
    int cont;
    trie* v[2];
    trie()
    {
        cont=0;
        memset(v,0,sizeof(v));
    }
};
trie* t=new trie;
void add(trie* nod,int s,int p2,int poz)
{
    if(p2==0)
    {
        nod->cont=poz;
        return;
    }
    int x=s&p2;
    if(x)
        x=1;
    else
        x=0;
    if(nod->v[x]==0)
    {
        nod->v[x]=new trie;
    }
    add(nod->v[x],s,p2/2,poz);
}
pair<int,int> query(trie* nod,int x,int p2)
{
    if(p2==0)
    {
        return make_pair(0,nod->cont);
    }
    int s=x&p2;
    if(s)
        s=1;
    else
        s=0;
    pair<int,int> val=make_pair(0,0);
    if(nod->v[1-s]!=0)
    {
        val=query(nod->v[1-s],x,p2/2);
        val.first+=(1-s)*p2;
    }
    else
    {
        val=query(nod->v[s],x,p2/2);
        val.first+=s*p2;
    }
    return val;
}
int main()
{
    int n;
    si>>n;
    int a,x=0;
    int sol=0,st=0,fn=1;
    pair<int,int> c;
    add(t,0,(1<<21),0);
    for(int i=1;i<=n;++i)
    {
        si>>a;
        x^=a;
        add(t,x,(1<<21),i);
        c=query(t,x,(1<<21));
        c.first=x^c.first;
        if(c.first>sol)
        {
            sol=c.first;
            st=c.second;
            fn=i;
        }
        //cout<<x<<' ';
    }
    so<<sol<<' '<<st+1<<' '<<fn<<'\n';
    return 0;
}