Pagini recente » Cod sursa (job #1401669) | Cod sursa (job #3244534) | Cod sursa (job #1663342) | Cod sursa (job #1855042) | Cod sursa (job #1995899)
#include <iostream>
#include <fstream>
#include <utility>
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(i > 0) {
long long bit = x & i;
if(bit == i) {
k = (k << 1) + 2LL;
} else {
k = (k << 1) + 1LL;
}
i >>= 1;
trie[k] = 1;
}
trie[k] = z;
z++;
}
pair<long long, int> path(long long x) {
long long ans = 0LL;
long long i = 1LL << 20;
long long k = 0LL;
while(i > 0) {
long long bit = x & i;
//true if x bit is 1
if(bit == i) {
if(trie[(k << 1) + 1LL] >= 0) {
k = (k << 1) + 1LL;
} else {
ans += i;
k = (k << 1) + 2LL;
}
} else {
if(trie[(k << 1) + 2LL] >= 0) {
ans += i;
k = (k << 1) + 2LL;
} else {
k = (k << 1) + 1LL;
}
}
i >>= 1;
}
return make_pair(ans, trie[k]);
}
int main() {
constexpr int CONST_N = 100005;
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 < (1LL<<22); i++) {
trie[i] = -1;
}
insert(0LL);
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);
//pick shortest soln
/*
if((res.first ^ cur_xor) == cur_max && (i - res.second) < (curr_max_end - curr_max_start)) {
curr_max_start = res.second;
curr_max_end = i;
}
*/
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;
}