Pagini recente » Borderou de evaluare (job #2684987) | Cod sursa (job #3002163) | Cod sursa (job #2078965) | Cod sursa (job #1632559) | Cod sursa (job #3146523)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
const int BITS = 21;
struct TrieNode {
int count;
TrieNode *child[2];
TrieNode() : count(0), child{nullptr, nullptr} {}
};
class Trie {
public:
Trie() {
root = new TrieNode();
}
void insert(int num) {
TrieNode *node = root;
for (int i = BITS - 1; i >= 0; i--) {
int bit = (num >> i) & 1;
if (!node->child[bit])
node->child[bit] = new TrieNode();
node = node->child[bit];
node->count++;
}
}
int maxXOR(int num) {
TrieNode *node = root;
int result = 0;
for (int i = BITS - 1; i >= 0; i--) {
int bit = (num >> i) & 1;
if (node->child[1 - bit] && node->child[1 - bit]->count > 0) {
result |= (1 << i);
node = node->child[1 - bit];
} else {
node = node->child[bit];
}
}
return result;
}
private:
TrieNode *root;
};
int main() {
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int N;
fin >> N;
vector<int> a(N);
for (int i = 0; i < N; i++) {
fin >> a[i];
}
Trie trie;
int max_xor = 0, prefix_xor = 0;
int start = 0, stop = -1;
trie.insert(0);
for (int i = 0; i < N; i++) {
prefix_xor ^= a[i];
trie.insert(prefix_xor);
int current_xor = trie.maxXOR(prefix_xor);
if (current_xor > max_xor || (current_xor == max_xor && (stop - start < i))) {
max_xor = current_xor;
stop = i;
int tmp = i;
while (tmp >= 0 && (current_xor ^ a[tmp]) != prefix_xor) {
tmp--;
}
start = tmp;
}
}
fout << max_xor << " " << (start + 1) << " " << (stop + 1) << endl;
fin.close();
fout.close();
return 0;
}