Cod sursa(job #2979419)

Utilizator DariusM17Murgoci Darius DariusM17 Data 15 februarie 2023 01:53:06
Problema Xor Max Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>
using namespace std ;
ifstream fin("xormax.in") ;
ofstream fout("xormax.out") ;
const int NM=1e5+5 ;
class Trie
{
private:
    int pos=0 ;
    Trie *next[2]={} ;
public:
    Trie()
    {
        next[0]=next[1]=nullptr ;
    }
    void insert(int pos,int val,int bit=21)
    {
        bool b=(1LL<<bit)&val ;
        if(bit==-1)
        {
            this->pos=pos;
            return ;
        }
        if(!next[b]) next[b]=new Trie() ;
        next[b]->insert(pos,val,bit-1);
    }
    int query(int val,int bit=21)
    {
        bool b=(1LL<<bit)&val ;
        if(bit==-1) return this->pos ;
        if(next[!b]) return next[!b]->query(val,bit-1) ;
        return next[b]->query(val,bit-1) ;
    }
};
int sp[NM] ;
int main()
{
    Trie a ;
    int n,x,sum=0,left,right,st,dr,mx=-1,xx ;
    fin>>n ;
    for(int i=1; i<=n; ++i)
    {
        fin>>x ;
        sp[i]=sp[i-1]^x ;
        if(sp[i]>mx) mx=sp[i],st,1,dr=i ;
    }
    a.insert(1,sp[1]) ;
    for(int i=2; i<=n; ++i)
    {
        left=a.query(sp[i]) ;
        xx=sp[i]^sp[left] ;
        if(xx>mx)
        {
            mx=xx ;
            st=left+1,dr=i ;
        }
        a.insert(i,sp[i]) ;
    }
    fout<<mx<<" "<<st<<" "<<dr ;
    return 0 ;
}