Cod sursa(job #3351746)

Utilizator vladneaguVladneagu vladneagu Data 21 aprilie 2026 11:18:42
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")

const int MAXN = 100000;
const int MAXBITS = 22;

struct Node {
    int endd;
    int next[2];
} t[MAXN * MAXBITS];

int sz = 1;

void insert_trie(int nr, int idd) {
    int u = 0;
    for (int i = MAXBITS - 1; i >= 0; i--) {
        int val = (nr >> i) & 1;
        if (t[u].next[val] == -1) {
            t[u].next[val] = sz;
            t[sz].next[0] = t[sz].next[1] = -1;
            sz++;
        }
        u = t[u].next[val];
    }
    t[u].endd = idd;
}

pair<int,int> calc(int nr) {
    int u = 0, x = 0;
    for (int i = MAXBITS - 1; i >= 0; i--) {
        int val = ((nr >> i) & 1) ^ 1;
        if (t[u].next[val] != -1) {
            x |= (val << i);
            u = t[u].next[val];
        } else {
            val ^= 1;
            x |= (val << i);
            u = t[u].next[val];
        }
    }
    return {x, t[u].endd};
}

int prefxor[MAXN + 5];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 0; i < MAXN * MAXBITS; i++)
        t[i].next[0] = t[i].next[1] = -1;

    int n;
    cin >> n;

    int maxi = -1, l = 1, r = 1;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        prefxor[i] = prefxor[i-1] ^ x;

        if (prefxor[i] > maxi) {
            maxi = prefxor[i];
            l = 1;
            r = i;
        }
    }

    for (int i = n; i >= 1; i--) {
        insert_trie(prefxor[i], i);

        auto [best, idd] = calc(prefxor[i]);
        int val = best ^ prefxor[i];

        if (val > maxi ||
           (val == maxi && idd < r) ||
           (val == maxi && idd == r && (r - l + 1) > (idd - i))) {
            l = i + 1;
            r = idd;
            maxi = val;
        }
    }

    cout << maxi << " " << l << " " << r;
}