Cod sursa(job #1850522)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 18 ianuarie 2017 18:40:12
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");

int n,s[100005],trie[1<<22],sol=-1,st,en;
char c[21];

int main()
{
    int i,j,nod;
    fin >> n;
    for(i=2;i<1<<22;++i) trie[i]=-1;
    for(i=1;i<<22;++i) trie[1<<i]=0;
    for(i=1;i<=n;++i)
    {
        fin >> s[i];
        s[i]^s[i-1];
        for(j=0;j<21;++j)
            c[j]=(bool)(s[i]&(1<<(20-j)));
        nod=1;
        for(j=0;j<21;++j)
        {
            if(trie[(nod<<1)+!c[j]]>0) nod=(nod<<1)+!c[j];
            else nod=(nod<<1)+c[j];

        }
        j=trie[nod];
        if((s[i]^s[j])>sol)
        {
            sol=s[i]^s[j];
            st=j+1;
            en=i;
        }
        nod=1;
        for(j=0;j<21;++j) trie[nod=(nod<<1)+c[j]]=i;
    }
    fout << sol << ' ' << st << ' ' << en << endl;
    return 0;
}