Pagini recente » Cod sursa (job #779103) | Cod sursa (job #1662705) | Cod sursa (job #270462) | Cod sursa (job #796242) | Cod sursa (job #2231094)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <set>
using namespace std;
struct BestXorInfo {
uint32_t Value;
uint32_t Position;
};
struct TrieNode {
BestXorInfo xorInfo;
vector< TrieNode* > children;
TrieNode() {
children.resize(2, nullptr);
}
};
void Insert(TrieNode* node, const char* insertedString, const BestXorInfo& insertedInfo) {
if (*insertedString == '\0') {
node->xorInfo = move(insertedInfo);
return;
}
if (node->children[*insertedString - '0'] == nullptr) {
node->children[*insertedString - '0'] = new TrieNode();
}
Insert(node->children[*insertedString - '0'], insertedString + 1, insertedInfo);
}
BestXorInfo GetBestXor(TrieNode* node, const char* queriedString) {
if (*queriedString == '\0') {
return node->xorInfo;
}
if (node->children[1 - (*queriedString - '0')] != nullptr)
return GetBestXor(node->children[1 - (*queriedString - '0')], queriedString + 1);
else if (node->children[*queriedString - '0'] != nullptr)
return GetBestXor(node->children[*queriedString - '0'], queriedString + 1);
}
int main() {
ios::sync_with_stdio(false);
ifstream cin("xormax.in");
ofstream cout("xormax.out");
uint32_t n;
cin >> n;
uint32_t currentXor = 0;
uint32_t bestXor = 0;
uint32_t bestLeft = 0;
uint32_t bestRight = 0;
TrieNode* root = new TrieNode();
BestXorInfo currentInfo;
currentInfo.Value = 0;
currentInfo.Position = 0;
Insert(root, bitset<22>(0).to_string().c_str(), currentInfo);
for (uint32_t i = 1; i <= n; ++i) {
uint32_t x;
cin >> x;
currentXor ^= x;
bitset<22> bs(currentXor);
currentInfo.Value = currentXor;
currentInfo.Position = i;
Insert(root, bs.to_string().c_str(), currentInfo);
BestXorInfo bestXorInfo = GetBestXor(root, bs.to_string().c_str());
if ((currentXor ^ bestXorInfo.Value) > bestXor) {
bestXor = currentXor ^ bestXorInfo.Value;
bestLeft = bestXorInfo.Position + 1;
bestRight = i;
}
}
if (bestLeft == 0) bestLeft = bestRight = 1;
cout << bestXor << " " << bestLeft << " " << bestRight;
//system("pause");
return 0;
}