Pagini recente » Cod sursa (job #997953) | Cod sursa (job #1120689) | Cod sursa (job #278858) | Cod sursa (job #48084) | Cod sursa (job #1995755)
#include <iostream>
#include <fstream>
#include <utility>
#include <bitset>
using namespace std;
int trie[1<<<23];
int z = 0;;
void insert(long long x) {
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;
}
i >>= 1;
trie[k] = 1;
}
trie[k] = z;
z++;
}
pair<long long, int> 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;
//true if x bit is 1
if(bit == i) {
if(trie[(k << 1) + 1LL] >= 0) {
// cout << "leftG ";
k = (k << 1) + 1LL;
} else {
ans += i;
k = (k << 1) + 2LL;
// cout << "rightF ";
}
} else {
if(trie[(k << 1) + 2LL] >= 0) {
ans += i;
k = (k << 1) + 2LL;
} else {
k = (k << 1) + 1LL;
}
}
i >>= 1;
}
// cout << k << endl;
return make_pair(ans, trie[k]);
}
int main() {
constexpr int CONST_N = 10005;
int N;
ifstream fin("xormax.in");
fin >> N;
long long list[CONST_N];
for(int i = 0; i < N; i++) {
fin >> list[i];
}
trie[0] = 1;
for(long long i = 1LL; i < (1<<22); i++) {
trie[i] = -1;
}
insert(0L);
long long cur_max = 0;
long long cur_xor = 0;
int curr_max_start = 0;
int curr_max_end = 0;
for(int i = 0; i < N; i++) {
cur_xor ^= list[i];
insert(cur_xor);
pair<long long, int> res = path(cur_xor);
if((res.first ^ cur_xor) > cur_max) {
cur_max = res.first ^ cur_xor;
curr_max_start = res.second;
curr_max_end = i;
}
}
ofstream fout("xormax.out");
fout << cur_max << " " << (curr_max_start+1) << " " << (curr_max_end+1);
return 0;
}