Cod sursa(job #3222259)

Utilizator alexdumitruAlexandru Dumitru alexdumitru Data 9 aprilie 2024 16:41:58
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <bits/stdc++.h>

using namespace std;

const int bsize=(1<<16);

class InParser {
private:
    char * buff;
    int sp;
    FILE * fin;
    char get_ch()
    {
        sp++;
        if(sp==bsize)
        {
            sp=0;
            fread(buff,1,bsize,fin);
        }
        return buff[sp];
    }
public:
    InParser(const char * nume)
    {
        fin = fopen(nume,"r");
        sp = bsize-1;
        buff = new char[bsize]();
    }
    InParser& operator >> (int &x)
    {
        x=0;
        char c;
        while(!isdigit(c=get_ch()));
        x=c-'0';
        while(isdigit(c=get_ch()))
            x=x*10+c-'0';
        return * this;
    }
} fin("xormax.in");

ofstream fout("xormax.out");

int n,i,j,vl;

struct trie{
    trie *st, *dr;
    int poz;
    trie()
    {
        st=dr=nullptr;
        poz=0;
    }
};
trie * root = new trie;

void ins(trie * nod, int x, int b, int p)
{
    if(b<0)
    {
        nod->poz=p;
        return;
    }
    if(x&(1<<b))
    {
        if(!nod->dr)
            nod->dr = new trie;
        ins(nod->dr,x,b-1,p);
        return;
    }
    if(!nod->st)
        nod->st = new trie;
    ins(nod->st,x,b-1,p);
}

pair<int,int> sau(int x, pair<int,int> a)
{
    return make_pair(a.first|x,a.second);
}

pair<int,int> query(trie * nod, int x, int b)
{
    if(b==-1)
        return make_pair(0,nod->poz);
    if(x&(1<<b))
    {
        if(nod->st)
            return query(nod->st,x,b-1);
        return sau((1<<b),query(nod->dr,x,b-1));
    }
    if(nod->dr)
        return sau((1<<b),query(nod->dr,x,b-1));
    return query(nod->st,x,b-1);
}

int max1,l,r;

signed main()
{
    fin>>n;
    ins(root,0,21,0);
    int xr=0;
    for(i=1;i<=n;i++)
    {
        fin>>vl;
        xr^=vl;
        pair<int,int> rez=query(root,xr,21);
        if((xr^rez.first)>max1)
        {
            max1=xr^rez.first;
            l=rez.second+1;
            r=i;
        }
        ins(root,xr,21,i);
    }
    fout<<max1<<' '<<l<<' '<<r<<'\n';
    return 0;
}