Cod sursa(job #3362846)

Utilizator serbanbBrindescu Serban serbanb Data 12 august 2026 14:25:02
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>

using namespace std;

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

const int NMAX = 100000;
const int LOGMAX = 21;
const int NODEMAX = NMAX * (LOGMAX + 1);

int ps[NMAX + 5];
int trie[NODEMAX + 5][2];
int maxIdx[NODEMAX + 5];
int last = 0;

int n;

void add(int x, int idx)
{
    int j = 0;
    for(int i = LOGMAX - 1; i >= 0; --i){
        int b = (x >> i) & 1;
        if(trie[j][b] == 0){
            ++last;
            trie[j][b] = last;
            maxIdx[last] = -1;
        }
        j = trie[j][b];
        if(idx > maxIdx[j]){
            maxIdx[j] = idx;
        }
    }
}

int query(int x)
{
    int j = 0;
    for(int i = LOGMAX - 1; i >= 0; --i){
        int b = (x >> i) & 1;
        int b2 = b ^ 1;
        if(trie[j][b2] > 0){
            j = trie[j][b2];
        }
        else{
            j = trie[j][b];
        }
    }
    return maxIdx[j];
}

void read()
{
    fin >> n;
    ps[0] = 0;
    for(int i = 1; i <= n; ++i){
        int a;
        fin >> a;
        ps[i] = ps[i - 1] ^ a;
    }
}

void solve()
{
    add(ps[0], 0);

    int maxVal = -1, l = 0, r = 0;
    for(int i = 1; i <= n; ++i){
        int idx = query(ps[i]);
        int val = ps[i] ^ ps[idx];
        if(val > maxVal){
            maxVal = val;
            l = idx + 1;
            r = i;
        }
        add(ps[i], i);
    }
    fout << maxVal << ' ' << l << ' ' << r;
}

int main()
{
    read();
    solve();
    return 0;
}