Pagini recente » Cod sursa (job #2127936) | Cod sursa (job #2680873) | Cod sursa (job #714348) | Cod sursa (job #2776389) | Cod sursa (job #2231058)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <set>
using namespace std;
string toBinaryString(int x) {
string binaryRepr = ""s;
while (x > 0) {
binaryRepr = char('0' + (x & 1)) + binaryRepr;
x >>= 1;
}
if (binaryRepr.empty()) binaryRepr = "0"s;
return string(22 - binaryRepr.size(), '0') + binaryRepr;
}
struct BestXorInfo {
int Value;
int Position;
};
class TrieNode {
BestXorInfo xorInfo;
TrieNode* children[2];
public:
void Insert(const char* insertedString, const BestXorInfo& insertedInfo) {
if (*insertedString == '\0') {
this->xorInfo.Value = insertedInfo.Value;
this->xorInfo.Position = max(this->xorInfo.Position, insertedInfo.Position);
return;
}
if (children[*insertedString - '0'] == nullptr) {
children[*insertedString - '0'] = new TrieNode();
}
children[*insertedString - '0']->Insert(insertedString + 1, insertedInfo);
}
BestXorInfo GetBestXor(const char* queriedString) {
if (*queriedString == '\0') {
return xorInfo;
}
if (children[1 - (*queriedString - '0')] != nullptr)
return children[1 - (*queriedString - '0')]->GetBestXor(queriedString + 1);
else if (children[*queriedString - '0'] != nullptr)
return children[*queriedString - '0']->GetBestXor(queriedString + 1);
}
};
class Trie {
TrieNode root;
public:
void Insert(string& insertedString, const BestXorInfo& insertedInfo) {
root.Insert(insertedString.c_str(), insertedInfo);
}
BestXorInfo GetBestXor(string& queriedString) {
return root.GetBestXor(queriedString.c_str());
}
};
int main() {
ios::sync_with_stdio(false);
ifstream cin("xormax.in");
ofstream cout("xormax.out");
int n;
cin >> n;
int currentXor = 0;
int bestXor = 0;
int bestLeft = -1;
int bestRight = -1;
Trie trie;
string zeroRepr = toBinaryString(0);
trie.Insert(zeroRepr, { 0, 0 });
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
currentXor ^= x;
string binaryRepr = toBinaryString(currentXor);
BestXorInfo bestXorInfo = trie.GetBestXor(binaryRepr);
trie.Insert(binaryRepr, { currentXor, i });
if ((currentXor ^ bestXorInfo.Value) > bestXor) {
bestXor = currentXor ^ bestXorInfo.Value;
bestLeft = bestXorInfo.Position + 1;
bestRight = i;
}
else if ((currentXor ^ bestXorInfo.Value) == bestXor && i - bestXorInfo.Position - 1 < bestRight - bestLeft) {
bestLeft = bestXorInfo.Position + 1;
bestRight = i;
}
}
cout << bestXor << " " << bestLeft << " " << bestRight;
//system("pause");
return 0;
}