Cod sursa(job #2900555)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 11 mai 2022 10:12:12
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
	
#include <bits/stdc++.h>
#define nmax 100001
#define bitmax 22
using namespace std;
 
ifstream f("xormax.in");
ofstream g("xormax.out");
 
struct tr{
 
    int nr=-1;
    int next[2]={-1,-1};
};
tr t[nmax*(bitmax+2)];
int k=1;
 
void ins(const int x, const int poz,int nod, int l)
{
    if(l==-1) {t[nod].nr=poz;return;}
    bool dir=((x&(1<<l))>0);
    if(t[nod].next[dir]==-1) t[nod].next[dir]=++k;
    ins(x,poz,t[nod].next[dir],l-1);
}
 
 
int qer(const int x,int nod, int l)
{
    if(l==-1) {return t[nod].nr;}
    bool dir=((x&(1<<l))==0);
    //g<<dir;
    if(t[nod].next[dir]==-1) return qer(x,t[nod].next[1-dir],l-1);
    return qer(x,t[nod].next[dir],l-1);
}
 
int v[nmax];
int n;
int main()
{
    ios::sync_with_stdio(false);
    f.tie(NULL);
    f>>n;
    ins(0,0,1,bitmax);
    //debug(&root,bitmax,0);
    //g<<'\n';
    int ans=0,st=0,dr=0;
    for(int i=1;i<=n;i++)
    {
        int nr; f>>nr;
        v[i]=v[i-1]^nr;
        int opp=qer(v[i],1,bitmax);
        //g<<i<<','<<opp<<'\n';
        if(ans<(v[i]^v[opp]))
        {
            ans=(v[i]^v[opp]);
            st=opp+1;
            dr=i;
        }
        ins(v[i],i,1,bitmax);
    }
    g<<ans<<' '<<st<<' '<<dr;
    return 0;
}