Pagini recente » Cod sursa (job #519171) | Cod sursa (job #2930667) | Cod sursa (job #2698440) | Cod sursa (job #2759282) | Cod sursa (job #3127673)
#include <fstream>
#include <vector>
using namespace std;
const int MAX_SIZE = 21 * 100000 + 5;
struct node {
int chd[2] = { -1, -1 };
int id = -1;
};
vector <node> trie(1);
void CreateNode(int nod, bool type) {
if (trie[nod].chd[type] == -1) {
trie[nod].chd[type] = trie.size();
trie.emplace_back();
}
}
void Add(int nod, int num, int bit, int id) {
if (bit < 0) {
trie[nod].id = id;
return;
}
int val = 0;
if ( num & ( 1 << bit ) ) {
val = 1;
}
CreateNode( nod, val );
Add(trie[nod].chd[val], num, bit - 1, id);
}
std::pair <int, int> FindOpp(int nod, int num, int bit) {
if (bit < 0) {
return { trie[nod].id, 0 };
}
int val = 0;
if ( num & ( 1 << bit ) ) {
val = 1;
}
if (trie[nod].chd[val ^ 1] != -1) {
std::pair <int, int> sol;
sol = FindOpp(trie[nod].chd[val ^ 1], num, bit - 1);
sol.second |= 1 << bit;
return sol;
}
else {
std::pair <int, int> sol;
sol = FindOpp(trie[nod].chd[val], num, bit - 1);
return sol;
}
}
int main() {
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n, i, x, val = 0;
int pos1, pos2, max_sol = -1;
std::pair <int, int> new_sol;
fin >> n;
Add ( 0, 0, 20, 0 );
for ( i = 1; i <= n; i++ ) {
fin >> x;
val = val ^ x;
new_sol = FindOpp ( 0, val, 20 );
if ( new_sol.second > max_sol ) {
max_sol = new_sol.second;
pos1 = new_sol.first + 1;
pos2 = i;
}
Add ( 0, val, 20, i );
}
fout << max_sol << " " << pos1 << " " << pos2;
}