Pagini recente » Cod sursa (job #2355815) | Cod sursa (job #1320941) | Cod sursa (job #3351784) | Cod sursa (job #1046415) | Cod sursa (job #3351764)
#include <bits/stdc++.h>
using namespace std;
int N, pref = 0, a, mx = 0, L = -1, R = -1;
struct Node {
int p, e;
vector <int> next;
Node() {
p = 0;
e = 10000000;
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 = min (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) {
c = 1 - c;
}
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;
auto [ans, id] = trie.caut(mask);
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;
}