Cod sursa(job #3356561)

Utilizator Teodor-CiprianNica Teodor-Ciprian Teodor-Ciprian Data 2 iunie 2026 12:39:22
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>

using namespace std;

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

const int BitiMax=20;
const int NoduriMax=2100000;

class Trie {
public:
    int copii[NoduriMax][2];
    int nrr[NoduriMax];
    int cnt;

    Trie() {
        cnt=1;
        copii[1][0]=copii[1][1]=0;
        nrr[1]=0;
    }
} t;

void insert(int val, int index)
{
    int nod=1;
    t.nrr[nod]=index;

    for (int bit=BitiMax;bit>=0;bit--)
    {
        int b=(val>>bit)&1;
        if (t.copii[nod][b]==0)
        {
            t.copii[nod][b]=++t.cnt;
            t.copii[t.cnt][0]=t.copii[t.cnt][1]=0;
        }
        nod=t.copii[nod][b];
        t.nrr[nod]=index;
    }
}

pair<int, int> gasestemax(int val)
{
    int nod=1;
    int ls=0;

    for (int bit=BitiMax;bit>=0;bit--)
    {
        int b=(val>>bit)&1;
        if (t.copii[nod][1-b])
        {
            ls+=(1<<bit);
            nod=t.copii[nod][1-b];
        }
        else
            nod=t.copii[nod][b];
    }

    return {ls,t.nrr[nod]};
}

int main()
{
    int n,sumcur=0,max=-1,ls=1,ld=1;
    fin>>n;
    insert(0,0);
    for (int j=1;j<=n;j++)
    {
        int x;
        fin>>x;
        sumcur^=x;

        pair<int, int> rez=gasestemax(sumcur);
        int maxcur=rez.first;
        int lsmax=rez.second;

        if (maxcur>max)
        {
            max=maxcur;
            ls=lsmax+1;
            ld=j;
        }
        insert(sumcur, j);
    }
    fout<<max<<" "<<ls<<" "<<ld;
    return 0;
}