Pagini recente » Istoria paginii runda/oji10_2019 | Cod sursa (job #2990906) | Cod sursa (job #3164069) | Cod sursa (job #143789) | Cod sursa (job #2626940)
#include <bits/stdc++.h>
std::ifstream fin ("xormax.in");
std::ofstream fout ("xormax.out");
std::string toString (int nr){
std::string s;
for (int i=0; i<22; i++){
s.push_back ('0' + nr%2);
nr /= 2;
}
std::reverse (s.begin(), s.end());
return s;
}
class Trie{
struct Node{
char val;
int next[2] = {};
};
std::vector <Node> trie;
int size;
public:
Trie (){
size = 1;
trie.clear();
struct Node node;
node.val = '#';
trie.push_back (node);
}
void add (std::string s){
int node = 0, i;
for (i=0; i<s.size(); i++){
if (trie[node].next[s[i]-'0'] == 0){
struct Node newNode;
newNode.val = s[i] - '0';
trie.push_back (newNode);
trie[node].next[s[i]-'0'] = size;
size ++;
}
node = trie[node].next[s[i]-'0'];
}
}
int query (std::string s){
int node = 0;
int ans = 0, i, p2=1;
for (i=0; i<s.size(); i++){
ans *= 2;
if (trie[node].next['1'-s[i]] != 0){
ans ++;
node = trie[node].next['1'-s[i]];
}
else if (trie[node].next[s[i] - '0']){
node = trie[node].next[s[i]-'0'];
}
p2 *= 2;
}
return ans;
}
void print (){
for (int i=0; i<trie.size(); i++){
struct Node node = trie[i];
fout << trie[i].val << ' ' << trie[i].next[0] << ' ' << trie[i].next[1] << '\n';
}
}
};
int main()
{
int n, i, number, max=0, stop, newVal;
fin >> n;
int x[n], Xor[n] = {};
Trie trie;
//trie.print();
trie.add ("0000000000000000000000");
//trie.print();
for (i=0; i<n; i++){
fin >> x[i];
if (i == 0)
Xor[i] = x[i];
else
Xor[i] = Xor[i-1] ^ x[i];
newVal = trie.query (toString (Xor[i]));
if (max < newVal){
max = newVal;
stop = i;
}
trie.add (toString (Xor[i]));
}
//trie.print();
int start;
for (i=stop-1; i>=0; i--){
if ((Xor[stop] ^ Xor[i]) == max){
start = i;
break;
}
}
fout << max << ' ' << start +2<< ' ' << stop+1;
return 0;
}