Pagini recente » Cod sursa (job #1405967) | Cod sursa (job #3210360) | Cod sursa (job #207385) | Cod sursa (job #1122797) | Cod sursa (job #1679072)
#include <fstream>
using namespace std;
const int MaxN = 100005, StartBitPow = 20, INF = 0x3f3f3f3f;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
int v[MaxN];
int n, st, ed, max_xor = -INF;
class TrieNode {
int pos;
TrieNode *Edg[2];
public:
TrieNode() {
Edg[0] = Edg[1] = nullptr;
}
void TrieAdd(int val, int val_pos, int bitpow = StartBitPow) {
if(bitpow < 0) {
pos = val_pos;
return;
}
int prs = (val & (1 << bitpow)) > 0;
if(Edg[prs] == nullptr) {
Edg[prs] = new TrieNode;
}
Edg[prs]->TrieAdd(val, val_pos, bitpow - 1);
}
int TrieQuery(int val, int bitpow = StartBitPow) {
if(bitpow < 0) {
return pos;
}
int ngt = (val & (1 << bitpow)) == 0;
if(Edg[ngt] == nullptr) {
return Edg[!ngt]->TrieQuery(val, bitpow - 1);
}
return Edg[ngt]->TrieQuery(val, bitpow - 1);
}
};
TrieNode *Rt = new TrieNode;
int main() {
cin >> n;
Rt->TrieAdd(0, 0);
for(int i = 1; i <= n; ++i) {
cin >> v[i];
v[i] ^= v[i - 1];
int best_pos = Rt->TrieQuery(v[i]);
int best_xor = v[best_pos];
if((best_xor ^ v[i]) > max_xor) {
max_xor = (best_xor ^ v[i]);
st = best_pos + 1;
ed = i;
}
Rt->TrieAdd(v[i], i);
}
cout << max_xor << ' ' << st << ' ' << ed << '\n';
return 0;
}