Cod sursa(job #3353737)

Utilizator Andreea3425Diaconu Andreea Andreea3425 Data 10 mai 2026 19:52:16
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;

#define N 100000

int v[N+1], s[N+1];

struct Nod{
    int en;
    Nod *next[2];

    Nod(){
        next[0]=next[1]=NULL;
    }
};

Nod *t=new Nod();

void ins(Nod *&i, int a, int x, int k){
    if (k==0)
        return;

    if (i->next[x>>(k-1)&1]==NULL)
        i->next[x>>(k-1)&1]=new Nod();

    i->next[x>>(k-1)&1]->en=a;

    ins(i->next[x>>(k-1)&1], a, x, k-1);
}

int query(Nod *i, int x, int k){
    if (k==0)
        return i->en;

    if (i->next[x>>(k-1)&1^1]!=NULL)
        return query(i->next[x>>(k-1)&1^1], x, k-1);

    return query(i->next[x>>(k-1)&1], x, k-1);
}

int main()
{
    ifstream cin ("xormax.in");
    ofstream cout ("xormax.out");

    int n,i,a,l,r;

    cin >> n;

    for (i=1; i<=n; i++)
        cin >> v[i];

    for (i=1; i<=n; i++)
        s[i]=s[i-1]^v[i];

    ins(t, 0, 0, 21);

    l=r=1;
    for (i=1; i<=n; i++){
        a=query(t, s[i], 21);

        if ((s[i]^s[a])>(s[r]^s[l-1])){
            l=a+1;
            r=i;
        }

        ins(t, i, s[i], 21);
    }

    cout << (s[r]^s[l-1]) << ' ' << l << ' ' << r << '\n';

    return 0;
}