Cod sursa(job #3346233)

Utilizator robertcosacCosac Robert-Mihai robertcosac Data 12 martie 2026 21:31:25
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
struct trie
{
    int st;
    int fv[2];
};
vector <trie> a;
int p[25];
int sol=0;
int k=0;
int xr=0, i, l=1, r=1, temp_l;
void add (int nod, int idx)
{
    if (idx==-1)
        return;
    if (idx==0)
        a[nod].st=i;
    int bit=((xr&p[idx])!=0);
    //cout <<bit<<'\n';
    if (a[nod].fv[bit]==0)
    {
        a[nod].fv[bit]=++k;
        a.push_back({0,0,0});
    }
    add (a[nod].fv[bit], idx-1);
}
void query (int nod, int idx)
{
    if (idx==-1)
        return;
    if (idx==0)
    {
        temp_l=a[nod].st;
    }
    int bit=((xr&p[idx])!=0);
    bit=1-bit;
    if (a[nod].fv[bit]!=0)
    {
        sol+=p[idx];
        query (a[nod].fv[bit], idx-1);
    }
    else
        query (a[nod].fv[1-bit], idx-1);
}

signed main ()
{
    p[0]=1;
    for (int i=1; i<=23; i++)
        p[i]=2*p[i-1];
    a.push_back({0,0,0});
    int n, ans=0;
    f >> n;
    for (i=1; i<=n; i++)
    {
        int x;
        f >> x;
        xr=(xr^x);
        sol=0;
        temp_l=0;
        query (0, 23);
        //ans=max (ans, sol);
        if (sol>ans)
        {
            ans=sol;
            r=i;
            l=temp_l+1;
        }
        add(0, 23);
    }
    g<<ans << ' '<< l << ' ' << r << '\n';
}