Pagini recente » Istoria paginii utilizator/tamasgy | Cod sursa (job #2143645) | Istoria paginii utilizator/rawsteel | simci | Cod sursa (job #2783646)
/*
`-/oo+/- ``
.oyhhhhhhyo.`od
+hhhhyyoooos. h/
+hhyso++oosy- /s
.yoooossyyo:``-y`
..----.` ``.-/+:.`
`````..-::/.
`..```.-::///`
`-.....--::::/:
`.......--::////:
`...`....---:::://:
`......``..--:::::///:`
`---.......--:::::////+/`
----------::::::/::///++:
----:---:::::///////////:`
.----::::::////////////:-`
`----::::::::::/::::::::-
`.-----:::::::::::::::-
...----:::::::::/:-`
`.---::/+osss+:`
``.:://///-.
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << '\n'
#define debugsp(x) cerr << #x << " " << x << ' '
using namespace std;
ifstream in ("xormax.in");
ofstream out ("xormax.out");
const int INF = 2e9;
const int N = 1e5;
const int BITS = 20;
class Trie {
private:
struct Node {
int pos;
Node *fii[2];
Node () {
pos = INF;
fii[0] = fii[1] = nullptr;
}
~Node() {
pos = 0;
delete fii[0];
delete fii[1];
}
};
public:
Node* root;
Trie() {
root = new Node();
}
void Update(Node* node, int value, int bitnum, int pos) {
if (bitnum == 0) {
node -> pos = min(node -> pos, pos);
return;
}
bool msb = value & (1 << bitnum);
if (node -> fii[msb] == nullptr)
node -> fii[msb] = new Node();
Update(node -> fii[msb], (value >= (1 << bitnum)) ? (value - (1 << bitnum)) : value, bitnum - 1, pos);
}
int Query(Node* node, int value, int bitnum) {
if (bitnum == 0) return node -> pos;
bool msb = (value & (1 << bitnum)) ^ 1;
if (node -> fii[msb] != nullptr)
return Query(node -> fii[msb], (value >= (1 << bitnum)) ? (value - (1 << bitnum)) : value, bitnum - 1);
else return Query(node -> fii[msb ^ 1], (value >= (1 << bitnum)) ? (value - (1 << bitnum)) : value, bitnum - 1);
}
};
int xp[1 + N];
int main() {
int n, Max, l, r;
Trie trie;
in >> n;
if (n == 1) {
out << "0 1 1\n";
return 0;
}
trie.Update(trie.root, 0, BITS, 0);
Max = l = r = 0;
for (int i = 1; i <= n; i++) {
int x;
in >> x;
xp[i] = xp[i - 1] ^ x;
int ans = trie.Query(trie.root, xp[i], BITS);
if ((xp[i] ^ xp[ans]) > Max) {
Max = xp[i] ^ xp[ans];
l = ans; r = i;
}
trie.Update(trie.root, xp[i], BITS, i);
}
out << Max << ' ' << l + 1 << ' ' << r << '\n';
in.close();
out.close();
return 0;
}