Pagini recente » Cod sursa (job #2121925) | Cod sursa (job #1067428) | Cod sursa (job #2358063) | Cod sursa (job #2873591) | Cod sursa (job #2271915)
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct Trie {
int pos;
Trie *l, *r;
Trie() {
pos = -1;
l = r = NULL;
}
};
Trie *root = new Trie;
void Insert(Trie *node, int val, int lvl, int pos) {
node -> pos = max(node -> pos, pos);
if (lvl < 0) return;
if ((1 << lvl) & val) {
if (node -> r == NULL) node -> r = new Trie;
Insert(node -> r, val, lvl - 1, pos);
} else {
if (node -> l == NULL) node -> l = new Trie;
Insert(node -> l, val, lvl - 1, pos);
}
}
int sofar, pos;
void Search(Trie *node, int val, int lvl, int sol) {
if (lvl < 0) {
sofar = sol;
pos = node -> pos;
return;
}
int num = (((1 << lvl) & val) ? 1 : 0);
if (num == 0) {
if(node -> r != NULL) {
Search(node -> r, val, lvl - 1, sol + (1 << lvl));
} else {
Search(node -> l, val, lvl - 1, sol);
}
} else {
if(node -> l != NULL) {
Search(node -> l, val, lvl - 1, sol + (1 << lvl));
} else {
Search(node -> r, val, lvl - 1, sol);
}
}
}
int main() {
int n; fin >> n;
vector < int > v(n);
for (auto &x: v) fin >> x;
for (int i = 1; i < n; ++i) v[i] ^= v[i - 1];
int best = -1;
int ab, bb; ab = bb = -1;
Insert(root, 0, 21, -1);
if (v[0] == 0) {
best = 0;
ab = bb = 1;
}
for (int i = 0; i < n; ++i) {
Insert(root, v[i], 21, i);
Search(root, v[i], 21, 0);
if (sofar == best) {
if (bb - ab > i - pos) {
ab = pos + 2;
bb = i + 1;
}
}
if (sofar > best) {
best = sofar;
ab = pos + 2;
bb = i + 1;
}
}
fout << best << " " << ab << " " << bb;
return 0;
}