Pagini recente » Cod sursa (job #970905) | Cod sursa (job #343086) | Cod sursa (job #650222) | Cod sursa (job #971454) | Cod sursa (job #3308933)
#include <fstream>
#include <bitset>
struct TrieNode
{
int index;
TrieNode *nextTrieNode[2] = {};
};
void insertInTrie(TrieNode *root, int value, int currentIndex)
{
for (int position = 20; position >= 0; --position)
{
int bit = (value >> position) & 1;
if (root -> nextTrieNode[bit] == nullptr)
root -> nextTrieNode[bit] = new TrieNode;
root = root -> nextTrieNode[bit];
}
root -> index = currentIndex;
}
std::pair<int, int> getBestPrefix(TrieNode *root, int value)
{
std::pair<int, int> answer = {};
for (int position = 20; position >= 0; --position)
{
int bit = (value >> position) & 1;
int want = 1 ^ bit;
if (root -> nextTrieNode[want])
{
answer.first |= 1 << position;
root = root -> nextTrieNode[want];
}
else
{
root = root -> nextTrieNode[bit];
}
}
answer.second = root -> index;
return answer;
}
int main()
{
std::ifstream inFile;
inFile.open("xormax.in");
int n;
inFile >> n;
TrieNode *root = new TrieNode;
insertInTrie(root, 0, 0);
int currentXor = 0, answer = -1, left = 1, right = 1;
for (int i = 1; i <= n; ++i)
{
int value;
inFile >> value;
currentXor ^= value;
std::pair<int, int> result = getBestPrefix(root, currentXor);
if (result.first > answer)
{
answer = result.first;
left = result.second + 1;
right = i;
}
insertInTrie(root, currentXor, i);
}
inFile.close();
std::ofstream outFile;
outFile.open("xormax.out");
outFile << answer << ' ' << left << ' ' << right;
outFile.close();
return 0;
}