Pagini recente » Cod sursa (job #2573679) | Cod sursa (job #639468) | Cod sursa (job #2884740) | Cod sursa (job #127637) | Cod sursa (job #1995750)
#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;
bool trie[1<<22];
void insert(long long x) {
// cout << "insert number: " << x << endl;
long long i = 1LL << 20;
long long k = 0LL;
while(k < (1LL<<21) - 1LL) {
long long bit = x & i;
if(bit == i) {
k = (k << 1) + 2LL;
// cout << "RIGHT" << endl;
} else {
k = (k << 1) + 1LL;
}
// cout << "i: " << bitset<22>(i) << endl;
// cout << "x: " << bitset<22>(x) << endl;
// cout << "k: " << bitset<22>(k) << endl;
// cout << k << endl;
i >>= 1;
trie[k] = true;
}
// cout << "DONE" << endl;
}
long long path(long x) {
// cout << "path number: " << x << endl;
long long ans = 0LL;
long long i = 1LL << 20;
long long k = 0LL;
while(k < (1LL<<21) - 1LL) {
long long bit = x & i;
// cout << (bit == i) << " " ;
// if(x == 3LL) {
// cout << endl;
// cout << "i: " << bitset<22>(i) << endl;
// cout << "x: " << bitset<22>(x) << endl;
// cout << "k: " << bitset<22>(k) << endl;
// cout << "match? " << (bit) << endl;
// cout << k << endl;
// }
//true if x bit is 1
if(bit == i) {
if(trie[(k << 1) + 1LL]) {
// cout << "leftG ";
k = (k << 1) + 1LL;
} else {
ans += i;
k = (k << 1) + 2LL;
// cout << "rightF ";
}
} else {
if(trie[(k << 1) + 2LL]) {
ans += i;
k = (k << 1) + 2LL;
// cout << "rightG ";
} else {
// cout << "leftF ";
k = (k << 1) + 1LL;
}
}
i >>= 1;
}
// cout << k << endl;
return ans;
}
int main() {
ifstream fin("xormax.in");
constexpr int CONST_N = 10005;
int N;
fin >> N;
long long list[CONST_N];
for(int i = 0; i < N; i++) {
fin >> list[i];
}
trie[0] = true;
for(long long i = 1LL; i < (1<<22); i++) {
trie[i] = false;
}
insert(0L);
// for(long long i = 0LL; i < (1<<22); i++) {
// if(trie[i]) {
// cout << bitset<22>(i) << endl;
// cout << i << endl;
// }
// }
long long cur_max = 0;
long long cur_xor = 0;
for(int i = 0; i < N; i++) {
cur_xor ^= list[i];
insert(cur_xor);
long long best = path(cur_xor);
// cout << cur_xor << ", " << (best ^ cur_xor) << endl;
//cout << (path(cur_xor) ^ cur_xor) << endl;
cur_max = max(cur_max, best ^ cur_xor);
}
ofstream fout("xormax.out");
fout << cur_max;
return 0;
}