Cod sursa(job #2881896)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 30 martie 2022 23:39:15
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>
#define nmax 1000001
#define bitmax 21
using namespace std;

ifstream f("xormax.in");
ofstream g("xormax.out");

struct tr{

    int nr=-1;
    tr *next[2]={nullptr,nullptr};

};
tr root;

int x,poz;
void ins(tr *nod, int l)
{
    if(l==-1) {nod->nr=poz;return;}
    bool dir=(x&(1<<l))>0;
    if(nod->next[dir]==nullptr) nod->next[dir]=new tr;
    ins(nod->next[dir],l-1);
}


int qer(tr *nod, int l)
{
    if(l==-1) {return nod->nr;}
    bool dir=((x&(1<<l))==0);
    if(nod->next[dir]==nullptr) return qer(nod->next[1-dir],l-1);
    return qer(nod->next[dir],l-1);
}

void debug(tr *nod, int l, int ans)
{
    if(l==-1)
    {
        g<<ans<<'\n';
    }
    if(nod->next[0]!=nullptr) debug(nod->next[0],l-1,(ans<<1));
    if(nod->next[1]!=nullptr) debug(nod->next[1],l-1,(ans<<1)+1);
}

int v[nmax];
int n;
int main()
{
    f>>n;
    x=0;poz=0;
    ins(&root,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;
        x=v[i];
        int opp=qer(&root,bitmax);
        //g<<i<<','<<opp<<'\n';
        if(ans<v[i]^v[opp])
        {
            ans=v[i]^v[opp];
            st=opp+1;
            dr=i;
        }
        x=v[i];poz=i;
        ins(&root,bitmax);
    }
    g<<ans<<' '<<st<<' '<<dr;
    return 0;
}