Pagini recente » Cod sursa (job #2359861) | Cod sursa (job #3303178)
#include <cstdio>
#include <vector>
#define pb push_back
using namespace std;
const int NMAX = 100000;
int s[NMAX + 1]; // xor-uri partiale
// trie cu biti
struct TrieNode {
int sons[2];
int word_count;
int word_endings;
int position;
};
vector<TrieNode> trie;
TrieNode newNode() {
TrieNode x;
x.word_endings = 0;
x.word_count = 0;
x.sons[0] = x.sons[1] = -1;
x.position = 0;
return x;
}
void insert(int number, int index) {
int currentNodePosition = 0;
for (int i = 31; i >= 0; i--) {
int bit = (number >> i) & 1;
trie[currentNodePosition].word_count++;
if (trie[currentNodePosition].sons[bit] == -1) {
trie.pb(newNode());
trie[currentNodePosition].sons[bit] = trie.size() - 1;
}
currentNodePosition = trie[currentNodePosition].sons[bit];
}
trie[currentNodePosition].position = index;
trie[currentNodePosition].word_endings++;
}
int query(int number) {
int currentNodePosition = 0;
for (int i = 31; i >= 0; i--) {
int bit = (number >> i) & 1;
int flipped = bit ^ 1;
if (trie[currentNodePosition].sons[flipped] != -1) {
currentNodePosition = trie[currentNodePosition].sons[flipped];
} else {
currentNodePosition = trie[currentNodePosition].sons[bit];
}
}
if (trie[currentNodePosition].word_endings > 0) {
return trie[currentNodePosition].position;
}
return -1;
}
int main() {
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
trie.pb(newNode());
int n, i, prefix_xor, c, xor_max, st = 1, dr = 1;
scanf("%d", &n);
scanf("%d", &prefix_xor);
s[1] = prefix_xor;
insert(prefix_xor, 1);
xor_max = prefix_xor;
for (i = 2; i <= n; i++) {
scanf("%d", &c);
prefix_xor ^= c;
s[i] = prefix_xor;
insert(prefix_xor, i);
int j = query(prefix_xor);
if (j > 0) {
int val = s[i] ^ s[j - 1];
if (xor_max < val) {
xor_max = val;
st = j;
dr = i;
}
}
}
printf("%d %d %d\n", xor_max, st, dr);
return 0;
}