Pagini recente » Cod sursa (job #1034963) | Monitorul de evaluare | Cod sursa (job #2374207) | Cod sursa (job #310575) | Cod sursa (job #3351759)
#include <bits/stdc++.h>
using namespace std;
int N, pref = 0, a, mx = 0, L, R;
struct Node {
int p, e;
vector <int> next;
Node() {
p = 0;
e = 0;
next.assign(2, -1);
}
};
struct Trie {
vector <Node> t;
Trie() {
t.push_back(Node());
}
void add(int nr, int id) {
int u = 0;
t[u].p++;
for (int b = 20; b >= 0; b--) {
int c = (nr & (1 << b)) >> b;
if (t[u].next[c] == -1) {
t[u].next[c] = t.size();
t.push_back(Node());
}
u = t[u].next[c];
t[u].p++;
}
t[u].e = id;
}
pair <int, int> caut(int nr) {
int ans = 0, u = 0;
for (int b = 20; b >= 0; b--) {
int c = (nr & (1 << b)) >> b;
if (t[u].next[c] == -1) {
if (c == 1)
c = 0;
}
ans += (c ? (1 << b) : 0);
u = t[u].next[c];
}
return {ans, t[u].e};
}
};
Trie trie;
int main()
{
ifstream fin("xormax.in");
ofstream fout("xormax.out");
trie.add(0, 1);
fin >> N;
for (int i = 1; i <= N; i++) {
fin >> a;
pref ^= a;
int mask = (1 << 21) - 1;
mask ^= pref;
int ans = trie.caut(mask).first;
int id = trie.caut(mask).second;
if ((pref ^ ans) > mx) {
mx = pref ^ ans;
R = i;
L = id;
}
// fout << pref << ' ' << ans << '\n';
trie.add(pref, i + 1);
}
fout << mx << ' ' << L << ' ' << R;
return 0;
}