Pagini recente » Monitorul de evaluare | Cod sursa (job #439933) | Cod sursa (job #640349) | Cod sursa (job #2263288) | Cod sursa (job #3347428)
#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] = max(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;
}