Cod sursa(job #3358023)

Utilizator puica2018Puica Andrei puica2018 Data 13 iunie 2026 23:05:00
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

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

int n;
int a[100005];
int sxor[100005];

struct Trie
{
    int cnt{};

    Trie *leg[2]{};
};

Trie *T=new Trie();

void Insert(int val)
{
    Trie *aux=T;
    aux->cnt++;

    for(int bit=20; bit>=0; bit--)
    {
        int b=((val>>bit)&1);
        if((aux->leg[b])==NULL)
            aux->leg[b]=new Trie();
        aux=aux->leg[b];

        aux->cnt++;
    }
}

int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
        fin>>a[i];

    Insert(0);

    int ans=0,l=0,r=0;
    for(int i=1; i<=n; i++)
    {
        sxor[i]=(sxor[i-1]^a[i]);
        Insert(sxor[i]);

        Trie *aux=T;
        int v=0;
        for(int bit=20; bit>=0; bit--)
        {
            int b=((sxor[i]>>bit)&1);

            if(aux->leg[1-b])
            {
                v+=(1<<bit);
                aux=aux->leg[1-b];
            }
            else
            {
                aux=aux->leg[b];
            }
        }

        if(v>ans)
        {
            ans=v;
            r=i;
        }
    }

    for(int i=0; i<r; i++)
    {
        if((sxor[i]^sxor[r])==ans)
            l=i+1;
    }

    fout<<ans<<" "<<l<<" "<<r<<"\n";

    return 0;
}