Cod sursa(job #2886159)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 7 aprilie 2022 10:16:14
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 100005;

struct trie
{
    trie * f[2];
    int i;
    trie(int i=0)
    {
        f[0]=f[1]=nullptr;
        this->i=i;
    }
    void add(int nr,int ind,int poz=22)
    {
        i=ind;
        if(poz==-1)return;
        bool bit=nr&(1<<poz);
        if(f[bit]==nullptr)f[bit]=new trie();
        f[bit]->add(nr,ind,poz-1);
    }
    int query(int nr,int poz=22)
    {
        if(poz==-1)return i;
        bool bit=nr&(1<<poz);
        if(f[bit]!=nullptr)return f[bit]->query(nr,poz-1);
        return f[!bit]->query(nr,poz-1);
    }
} *root = new trie();

int sum[nmax];
int n;

int main()
{
    in>>n;
    root->add(0,0);
    int maxx=-1,start,stop;
    for(int i=1;i<=n;i++)
    {
        int nr;
        in>>nr;
        sum[i]=sum[i-1]^nr;
        int ind=root->query(~sum[i]);
        if(sum[i]^sum[ind]>maxx)
        {
            maxx=sum[i]^sum[ind];
            start=ind+1;
            stop=i;
        }
        root->add(sum[i],i);
    }
    out<<maxx<<' '<<start<<' '<<stop;
}