Pagini recente » Cod sursa (job #2884035) | Cod sursa (job #521791) | Cod sursa (job #3338003) | Cod sursa (job #584529) | Cod sursa (job #3338744)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int MAXLOG = 22;
const int MAXN = 100002;
struct Trie {
int poz;
Trie* next[2];
};
int v[MAXN];
int start, finish, ans, N;
void insert(Trie* root, int value, int p) {
root->poz = p;
for (int i = MAXLOG - 1; i >= 0; --i) {
const int bit = (value & (1 << i)) ? 1 : 0;
if (root->next[bit] == nullptr) {
root->next[bit] = new Trie();
}
root->next[bit]->poz = p;
root = root->next[bit];
}
}
int search(Trie* root, int value) {
for (int i = MAXLOG - 1; i >= 0; --i) {
const int desired_bit = (value & (1 << i)) ? 0 : 1;
if (root->next[desired_bit]) {
root = root->next[desired_bit];
} else {
root = root->next[1 - desired_bit];
}
}
return root->poz;
}
int main()
{
Trie* root = new Trie();
insert(root, 0, 0);
fin >> N;
for (int i = 1; i <= N; ++i) {
fin >> v[i];
v[i] ^= v[i - 1];
int p = search(root, v[i]);
if (ans < (v[i] ^ v[p])) {
ans = v[i] ^ v[p];
start = p + 1;
finish = i;
}
insert(root, v[i], i);
}
fout << ans << ' ' << start << ' ' << finish;
return 0;
}