Cod sursa(job #2897933)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 5 mai 2022 14:17:15
Problema Xor Max Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 100005;
const int nrmax = (1<<21)+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=0)
{
    if(poz==-1)return;
    int bit=nr&(1<<poz);
    nod|=bit;
    trie[nod]=ind;
    add(nr,ind,poz-1,nod);
}

int query(int nr,int poz=20,int nod=0)
{
    //outputbin(nr);
    if(poz==-1)return trie[nod];
    int bit=nr&(1<<poz);
    if(trie[nod|bit]!=-1)
    {
        //outputbin(nod|bit,poz);
        return query(nr,poz-1,nod|bit);
    }
    else
    {
        bit=(~(nr&(1<<poz)))&(1<<poz);
        //outputbin(nod|bit,poz);
        return query(nr,poz-1,nod|bit);
    }
}

int sum[nmax];
int n;

int main()
{
    for(int i=0;i<(1<<21);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<=10000)
    {
        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;
}