Pagini recente » Cod sursa (job #2190525) | Cod sursa (job #1550226) | Cod sursa (job #2028521) | Cod sursa (job #862235) | Cod sursa (job #2231040)
#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 = "";
while (x > 0) {
binaryRepr += char('0' + (x & 1));
x >>= 1;
}
if (binaryRepr.empty()) binaryRepr = "0";
return binaryRepr + string(22 - binaryRepr.size(), '0');
}
struct BestXorInfo {
int Value;
int Position;
};
class TrieNode {
BestXorInfo xorInfo;
vector< TrieNode* > children;
public:
TrieNode() {
children.resize(2);
}
void Insert(string& insertedString, const BestXorInfo& insertedInfo) {
if (insertedString.empty()) {
this->xorInfo.Value = insertedInfo.Value;
this->xorInfo.Position = max(this->xorInfo.Position, insertedInfo.Position);
return;
}
char lastChar = insertedString.back();
insertedString.pop_back();
if (children[lastChar - '0'] == nullptr) {
children[lastChar - '0'] = new TrieNode();
}
children[lastChar - '0']->Insert(insertedString, insertedInfo);
}
BestXorInfo GetBestXor(string& queriedString) {
if (queriedString.empty()) {
return xorInfo;
}
char lastChar = queriedString.back();
queriedString.pop_back();
if (children[1 - (lastChar - '0')] != nullptr)
return children[1 - (lastChar - '0')]->GetBestXor(queriedString);
else if (children[lastChar - '0'] != nullptr)
return children[lastChar - '0']->GetBestXor(queriedString);
}
};
class Trie {
TrieNode root;
public:
void Insert(string& insertedString, const BestXorInfo& insertedInfo) {
root.Insert(insertedString, insertedInfo);
}
BestXorInfo GetBestXor(string& queriedString) {
return root.GetBestXor(queriedString);
}
};
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;
trie.Insert(toBinaryString(0), { 0, 0 });
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
currentXor ^= x;
string binaryRepr = toBinaryString(currentXor);
BestXorInfo bestXorInfo = trie.GetBestXor(string(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;
}