Cod sursa(job #3352515)

Utilizator andreidumitrache1709andreidumitrache andreidumitrache1709 Data 28 aprilie 2026 12:13:15
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000;
const int MAXB = 21; // 0..20 bits

struct Trie {
    struct Node {
        int nxt[2];
        int idx;
        Node() {
            nxt[0] = nxt[1] = 0;
            idx = -1;
        }
    } t[MAXN * MAXB + 5];

    int len = 1;

    void add(int x, int idx) {
        int u = 1;
        for(int i = MAXB - 1; i >= 0; i--) {
            int bit = (x >> i) & 1;
            if(!t[u].nxt[bit])
                t[u].nxt[bit] = ++len;
            u = t[u].nxt[bit];
        }
        t[u].idx = idx;
    }

    pair<int,int> findbest(int x) {
        int u = 1;
        int ans = 0;
        for(int i = MAXB - 1; i >= 0; i--) {
            int bit = (x >> i) & 1;
            if(t[u].nxt[1 - bit]) {
                ans |= (1 << i);
                u = t[u].nxt[1 - bit];
            } else {
                u = t[u].nxt[bit];
            }
        }
        return {ans, t[u].idx};
    }

} trie;

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

    int n;
    cin >> n;

    int x, xorr = 0;
    int ans = 0, l = 1, r = 1;

    // IMPORTANT: prefix XOR = 0 la poziția 0
    trie.add(0, 0);

    for(int i = 1; i <= n; i++) {
        cin >> x;
        xorr ^= x;

        auto best = trie.findbest(xorr);

        if(best.first > ans) {
            ans = best.first;
            l = best.second + 1;
            r = i;
        }

        trie.add(xorr, i);
    }

    cout << ans << " " << l << " " << r << "\n";
    return 0;
}