Pagini recente » Cod sursa (job #663272) | Cod sursa (job #1985163) | Cod sursa (job #2355815) | Cod sursa (job #1320941) | Cod sursa (job #3351784)
#include <bits/stdc++.h>
using namespace std;
int N, pref = 0, a, mx = -12, L = -1, R = -1;
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 = 1 - ((nr >> b) & 1);
if (t[u].next[c] == -1) {
c = 1 - c;
}
if (c != ((nr >> b) & 1))
ans += (1 << b);
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;
auto [val, id] = trie.caut(pref);
if (val > mx) {
mx = val;
R = i;
L = id;
}
// fout << pref << ' ' << ans << '\n';
trie.add(pref, i + 1);
}
fout << mx << ' ' << L << ' ' << R;
return 0;
}