Cod sursa(job #3308494)

Utilizator iordacheMatei Iordache iordache Data 25 august 2025 15:51:09
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int N=1e5+5;
struct Node
{
    Node *g[2];
    int last;
    Node() {g[0]=g[1]=NULL;}
};
Node *root=new Node();
void add(Node *&node, int ind, int x, int dep)
{
    if(dep==0) return;
    if(node->g[x>>(dep-1)&1]==NULL) node->g[x>>(dep-1)&1]=new Node();
    node->g[x>>(dep-1)&1]->last=ind;
    add(node->g[x>>(dep-1)&1],ind,x,dep-1);
}
int query(Node *node, int x, int dep)
{
    if(dep==0) return node->last;
    if(node->g[x>>(dep-1)&1^1]!=NULL) return query(node->g[x>>(dep-1)&1^1],x,dep-1);
    return query(node->g[x>>(dep-1)&1],x,dep-1);
}
int v[N],pref[N];
signed main()
{
    ifstream cin("xormax.in");ofstream cout("xormax.out");
    int n;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>v[i];
    for(int i=1;i<=n;++i) pref[i]=(pref[i-1]^v[i]);
    int l=1,r=1;
    for(int i=1;i<=n;++i)
    {
        if(i>1)
        {
            int x=query(root,pref[i],21);
            if((pref[i]^pref[x])>(pref[r]^pref[l-1])) l=x+1,r=i;
        }
        if(pref[i]>(pref[r]^pref[l-1])) l=1,r=i;
        add(root,i,pref[i],21);
    }
    cout<<(pref[r]^pref[l-1])<<" "<<l<<" "<<r;
}