Pagini recente » Cod sursa (job #626041) | Cod sursa (job #1108526) | Cod sursa (job #951167) | Cod sursa (job #851719) | Cod sursa (job #3351746)
#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;
}