Cod sursa(job #2811492)

Utilizator puica2018Puica Andrei puica2018 Data 2 decembrie 2021 13:04:54
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

int n;
int a[100005];

struct Trie
{
    int cnt,pos;
    Trie *leg[2];
    Trie(int _cnt,int _pos)
    {
        cnt=_cnt;
        pos=_pos;
        leg[0]=NULL;
        leg[1]=NULL;
    }
};

Trie *T;

void Add(int x,int i)
{
    Trie *p=T;
    for(int bit=20; bit>=0; bit--)
    {
        int b=(x>>bit)&1;
        if(p->leg[b]==NULL)
            p->leg[b]=new Trie(1,i);
        else
            p->leg[b]->cnt++;
        p=p->leg[b];
    }
}

pair <int,int> f(int x)
{
    Trie *p=T;
    int nr=0;
    for(int bit=20; bit>=0; bit--)
    {
        int b=(x>>bit)&1;
        if(p->leg[b^1])
        {
            p=p->leg[b^1];
            nr+=(b^1)*(1<<bit);
        }
        else
        {
            p=p->leg[b];
            nr+=b*(1<<bit);
        }
    }
    return make_pair(nr,p->pos);
}

int main()
{
    fin>>n;
    int i;
    for(i=1; i<=n; i++)
        fin>>a[i];
    T=new Trie(0,0);
    Add(0,0);
    int ans=0,l,r,sum=0;
    for(i=1; i<=n; i++)
    {
        sum^=a[i];
        pair <int,int> aux=f(sum);
        if(sum^aux.first>ans)
        {
            ans=sum^aux.first;
            l=aux.second+1;
            r=i;
        }
        Add(sum,i);
    }
    fout<<ans<<" "<<l<<" "<<r<<"\n";
    return 0;
}