Pagini recente » Cod sursa (job #2449289) | Cod sursa (job #2924063) | Cod sursa (job #48010) | Cod sursa (job #2804096) | Cod sursa (job #2442604)
#include <bits/stdc++.h>
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'
// mi am adus aminte ca am 90 din cv motiv dubios
using namespace std;
struct Node {
Node *son[2];
Node() {
son[0] = son[1] = NULL;
}
void Insert(int x, int bit = 20) {
if (bit < 0) {
return;
}
int s = (x & (1 << bit)) != 0;
if (son[s] == NULL) {
son[s] = new Node();
}
son[s]->Insert(x, bit - 1);
}
int Query(int x, int bit = 20) {
if (bit < 0) {
return 0;
}
int s = 1 ^ ((x & (1 << bit)) != 0);
if (son[s] != NULL) {
return ((1 << bit) | son[s]->Query(x, bit - 1));
} else {
assert(son[1 ^ s] != NULL);
return son[1 ^ s]->Query(x, bit - 1);
}
}
};
int main() {
ifstream cin("xormax.in");
ofstream cout("xormax.out");
int n; cin >> n;
Node *root = new Node();
root->Insert(0);
vector<int> pref(n + 1);
int ans = 0, stop = 1;
for (int i = 1; i <= n; ++i) {
int x; cin >> x;
if (i == 1) ans = x;
pref[i] = pref[i - 1] ^ x;
int curr = root->Query(pref[i]);
if (curr > ans) {
ans = curr;
stop = i;
}
root->Insert(pref[i]);
}
assert(stop != -1);
for (int i = stop - 1; i >= 0; --i) {
if ((pref[i] ^ pref[stop]) == ans) {
cout << ans << ' ' << i + 1 << ' ' << stop << endl;
return 0;
}
}
assert(false);
}