Cod sursa(job #3350832)

Utilizator CarenaMironov Cezar Luca Carena Data 13 aprilie 2026 18:13:03
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
#include <vector>
#define fr first
#define sc second

using namespace std;

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

const int NMAX=1e5+5, NRB=20;
int n, poz[NMAX];
vector<pair<int, int>> tr;

void add_node(int i, int val)
{
    int u=0;
    for(int b=NRB;b>=0;b--)
        if((val&(1<<b))==0)
        {
            if(tr[u].fr==-1)
            {
                tr[u].fr=tr.size();
                tr.push_back({-1, -1});
            }
            u=tr[u].fr;
        }
        else
        {
            if(tr[u].sc==-1)
            {
                tr[u].sc=tr.size();
                tr.push_back({-1, -1});
            }
            u=tr[u].sc;
        }
    poz[u]=i;
}

pair<int, int> find_max(int val)
{
    int u=0, v, ans=0;
    for(int b=NRB;b>=0;b--)
    {
        v=u;
        if((val&(1<<b))==0)
            u=(tr[u].sc==-1)?tr[u].fr:tr[u].sc;
        else
            u=(tr[u].fr==-1)?tr[u].sc:tr[u].fr;
        if(u==tr[v].sc)
            ans^=(1<<b);
    }
    return {ans, poz[u]};
}

int main()
{
    tr.push_back({-1, -1});
    in>>n;
    int xr=0, v, ans=-1, ansi, ansj;
    for(int i=1;i<=n;i++)
    {
        add_node(i, xr);
        in>>v; xr^=v;
        auto pans=find_max(xr);
        if(pans.fr^xr>ans)
        {
            ans=pans.fr^xr;
            ansi=i;
            ansj=pans.sc;
        }
    }
    out<<ans<<" "<<ansj<<" "<<ansi;
    return 0;
}