Cod sursa(job #3347427)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 16 martie 2026 17:57:44
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <bits/stdc++.h>
#define ll long long

using namespace std;

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

const int TMAX = 1e7;

int n, pref_xor, nodes = 1, max_xor;
pair<int, int> interval;
int trie[TMAX + 1][2];
int pos[TMAX + 1];

void insert_value(int x, int ind) {
    int node = 1;
    for(int i = 20; i >= 0; i--) {
        int bit = x >> i & 1;
        if(!trie[node][bit]) {
            trie[node][bit] = ++nodes;
        }
        node = trie[node][bit];
    }
    pos[node] = ind;
}

pair<int, int> get_max_xor(int x) {
    int node = 1;
    int best_xor = 0;
    for(int i = 20; i >= 0; i--) {
        bool bit = x >> i & 1;
        bool need_bit = !bit;
        if(trie[node][need_bit]) {
            best_xor |= (1 << i) * need_bit;
            node = trie[node][need_bit];
        }
        else {
            assert(trie[node][bit]);
            best_xor |= (1 << i) * bit;
            node = trie[node][bit];
        }
    }
    return {best_xor, pos[node]};
}

int main()
{
    fin >> n;
    insert_value(0, 0);
    for(int i = 1; i <= n; i++) {
        int x;
        fin >> x;
        pref_xor ^= x;
        auto [best_pairing_xor, start] = get_max_xor(pref_xor);
        int max_xor_here = best_pairing_xor ^ pref_xor;
        if(max_xor_here > max_xor) {
            max_xor = max_xor_here;
            interval = {start + 1, i};
        }
        insert_value(pref_xor, i);
    }
    fout << max_xor << ' ' << interval.first << ' ' << interval.second << '\n';
    return 0;
}