Pagini recente » Cod sursa (job #2473846) | Autentificare | Cod sursa (job #1941753) | Cod sursa (job #388972) | Cod sursa (job #3041453)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int ALPHABET_LENGTH = 2;
const int NMAX = 100000;
class TrieNode {
public:
int index;
TrieNode *children[ALPHABET_LENGTH];
TrieNode() {
index = 0;
for (auto & i : children) {
i = nullptr;
}
}
};
TrieNode *insert(TrieNode *root, int x, int index) {
if (root == nullptr) {
root = new TrieNode();
}
TrieNode *currentNode = root;
for (int i = 31; i >= 0; --i) {
int bit = (x >> i) & 1;
if (currentNode->children[bit] == nullptr) {
currentNode->children[bit] = new TrieNode();
}
currentNode = currentNode->children[bit];
}
currentNode->index = index;
return root;
}
int getMaxXorIndex(TrieNode *root, int x) {
TrieNode *currentNode = root;
int maxXor = 0;
for (int i = 31; i >= 0; --i) {
int bit = (x >> i) & 1;
if (!currentNode) {
return -1;
}
if (currentNode->children[1 - bit] != nullptr) {
currentNode = currentNode->children[1 - bit];
} else {
currentNode = currentNode->children[bit];
}
}
return currentNode->index;
}
int n, x;
int xors[NMAX];
int main() {
fin >> n;
fin >> xors[0];
for (int i = 1; i < n; ++i) {
fin >> x;
xors[i] = xors[i - 1] ^ x;
}
TrieNode *root = nullptr;
root = insert(root, 0, 0);
int maxXor = -1, leftIndex = -1, rightIndex = -1;
for (int i = 0; i < n; ++i) {
insert(root, xors[i], i);
int index = getMaxXorIndex(root, xors[i]);
if (index == -1) {
continue;
}
int xorValue = xors[i] ^ xors[index];
if (xorValue > maxXor) {
maxXor = xorValue;
leftIndex = index + 2;
rightIndex = i + 1;
}
}
fout << maxXor << " " << leftIndex << " " << rightIndex << '\n';
fin.close();
fout.close();
return 0;
}