Cod sursa(job #1718645)

Utilizator cubaLuceafarul cuba Data 18 iunie 2016 17:06:30
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
const int NMAX = 100003;
const int BITMAX = 22;
struct Trie{
    int poz;
    Trie *bt[3];
    Trie()
    {
        poz=0;
        bt[0]=bt[1]=0;
    }
};
Trie *T = new Trie;
int a[NMAX],n;
int sxor[NMAX];
inline void Add(Trie *nod,int x,int poz)
{
    bool bit;
    for(int i=BITMAX;i>=0;i--)
    {
        bit=(x&(1<<i));
        if(nod->bt[bit]==0)
            nod->bt[bit] = new Trie;
        nod=nod->bt[bit];
    }
    nod->poz=poz;
}
inline int Search(Trie *nod,int x)
{
    bool bit;
    for(int i=BITMAX;i>=0;i--)
    {
        bit=(x&(1<<i));
        if(nod->bt[!bit]!=0)
            nod=nod->bt[!bit];
        else
            nod=nod->bt[bit];
    }
    return nod->poz;
}
int main()
{
    int st,dr,sol=-1;
    f>>n;
    Add(T,0,0);
    for(int i=1;i<=n;i++)
    {
        f>>a[i];
        sxor[i]=sxor[i-1]^a[i];
        int j=Search(T,sxor[i]);
        if((sxor[i]^sxor[j])>sol)
        {
            dr=i;
            st=j+1;
            sol=sxor[i]^sxor[j];
        }
        Add(T,sxor[i],i);
    }
    g<<sol<<" "<<st<<" "<<dr<<"\n";
    return 0;
}