Cod sursa(job #2898128)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 6 mai 2022 08:31:58
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 100005;
const int nrmax = (1<<22)+5;

/*
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();
*/

void outputbin(int n,int poz=-1)
{
    bitset<32> nr(n);
    cout<<nr<<endl;
    string s;
    if(poz!=-1)
    {
        for(int i=31;i>=0;i--)
        {
            if(i!=poz)s.push_back(' ');
            else s.push_back('|');
        }
        cout<<s<<endl;
    }
}

int trie[nrmax];

void add(int nr,int ind,int poz=20,int nod=1)
{
    if(poz==-1)return;
    bool bit=nr&(1<<poz);
    if(bit)nod=nod*2+1;
    else nod=nod*2;
    trie[nod]=ind;
    add(nr,ind,poz-1,nod);
}

int query(int nr,int poz=20,int nod=1)
{
    //outputbin(nr);
    if(poz==-1)return trie[nod];
    bool bit=nr&(1<<poz);
    if(bit)
    {
        if(trie[nod*2+1]!=-1)
        {
            nod=nod*2+1;
        }
        else
        {
            nod=nod*2;
        }
    }
    else
    {
        if(trie[nod*2]!=-1)
        {
            nod=nod*2;
        }
        else
        {
            nod=nod*2+1;
        }
    }
    return query(nr,poz-1,nod);
}

int sum[nmax];
int n;

int main()
{
    for(int i=0;i<(1<<22);i++)trie[i]=-1;
    in>>n;
    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;
        //outputbin(sum[i]);
        //outputbin(~sum[i]);
        int ind=query(~sum[i]);
        //cout<<ind<<' '<<i<<'\n';
        if((sum[i]^sum[ind])>maxx)
        {
            maxx=sum[i]^sum[ind];
            start=ind+1;
            stop=i;
        }
        add(sum[i],i);
    }
    if(n<=50000)
    {
        for(int i=0;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                if((sum[i]^sum[j])>maxx)
                {
                    maxx=(sum[i]^sum[j]);
                    start=i+1;
                    stop=j;
                }
            }
        }
    }
    out<<maxx<<' '<<start<<' '<<stop;
}