Pagini recente » Cod sursa (job #2606249) | Cod sursa (job #1755553) | Cod sursa (job #3233864) | Cod sursa (job #2340832) | Cod sursa (job #2231104)
#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;
};
BestXorInfo insertedInfo;
char trieString[22];
int idx = -1;
class TrieNode {
BestXorInfo xorInfo;
vector< TrieNode* > children;
public:
TrieNode() {
children.resize(2, nullptr);
}
void Insert() {
if (++idx >= 22) {
xorInfo = move(insertedInfo);
return;
}
if (children[trieString[idx] - '0'] == nullptr) {
children[trieString[idx] - '0'] = new TrieNode();
}
children[trieString[idx] - '0']->Insert();
}
BestXorInfo GetBestXor() {
if (++idx >= 22) {
return xorInfo;
}
if (children[1 - (trieString[idx] - '0')] != nullptr)
return children[1 - (trieString[idx] - '0')]->GetBestXor();
else if (children[trieString[idx] - '0'] != nullptr)
return children[trieString[idx] - '0']->GetBestXor();
}
};
void convertToBinaryString(uint32_t x) {
int cnt = 21;
while (x > 0) {
trieString[cnt--] = '0' + (x & 1);
x >>= 1;
}
while (cnt >= 0)
trieString[cnt--] = '0';
}
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();
insertedInfo.Value = 0;
insertedInfo.Position = 0;
convertToBinaryString(0);
root->Insert();
idx = -1;
uint32_t x;
BestXorInfo bestXorInfo;
for (uint32_t i = 1; i <= n; ++i) {
cin >> x;
currentXor ^= x;
insertedInfo.Value = currentXor;
insertedInfo.Position = i;
convertToBinaryString(currentXor);
root->Insert();
idx = -1;
bestXorInfo = root->GetBestXor();
idx = -1;
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;
}