Cod sursa(job #3347764)

Utilizator moloDaniMolodet Andrei Daniel moloDani Data 18 martie 2026 11:20:47
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>

using namespace std;

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

const int mxN = 100000 * 21 + 5;

int trie[mxN][2], nxt = 1, inx[mxN];

void add(long long a, int ind){
    int nod = 1;
    long long bit = 1 << 20;
    for(int i = 0; i < 21; i++){
        int v = (a & bit) ? 1 : 0;

        if(!trie[nod][v]) trie[nod][v] = ++nxt;

        nod = trie[nod][v];
        bit = bit >> 1;
    }
    inx[nod] = ind;
}

long long xOrMax(long long a, int &ind){
    int nod = 1;
    long long bit = 1 << 20, ans = 0;
    for(int i = 0; i < 21; i++){
        int v = (a & bit) ? 1 : 0;

        if(trie[nod][!v]) nod = trie[nod][!v], ans += bit;
        else nod = trie[nod][v];

        bit = bit >> 1;
    }

    ind = inx[nod];

    return ans;
}

int main(){
    int n, st, dr, indAux;
    long long max = 0, aux = 0, x;
    add(0, 0);
    fin >> n;
    for(int i = 1; i <= n; i++){
        fin >> x;
        aux = aux ^ x;
        long long val = xOrMax(aux, indAux);

        if(val >= max){
            max = val;
            st = indAux;
            dr = i;
        }
        add(aux, i);
    }

    fout << max << " " << st + 1 << " " << dr;
}