Pagini recente » Cod sursa (job #3154273) | Cod sursa (job #2576038) | Cod sursa (job #2469203) | Cod sursa (job #859900) | Cod sursa (job #469233)
Cod sursa(job #469233)
#include <iostream>
using namespace std;
#define maxn 100010
#define inf 99999999
#define transf(x) ~x
int N, A[maxn], S[maxn];
int nr, poz;
struct Trie {
int k;
Trie *fiu[2];
Trie() {
k = 0;
memset(fiu, 0, sizeof(fiu));
}
};
Trie *T = new Trie;
void add(Trie *q, int b) {
if(b == -1) {
q -> k = poz;
return;
}
int next = nr & (1 << b);
if(next) next = 1;
if(!q -> fiu[next]) {
q -> fiu[next] = new Trie;
}
add(q -> fiu[next], b-1);
}
int search(Trie *q, int b) {
if(b == -1) {
return q -> k;
}
int next = nr & (1 << b);
if(next) next = 1;
if(!q -> fiu[next]) {
if(!next) next = 1;
else next = 0;
}
if(!q -> fiu[next]) {
return 0;
}
return search(q -> fiu[next], b-1);
}
int main() {
FILE *f1=fopen("xormax.in", "r"), *f2=fopen("xormax.out", "w");
int i, p, q;
fscanf(f1, "%d\n", &N);
for(i=1; i<=N; i++) {
fscanf(f1, "%d", &A[i]);
S[i] = S[i-1] ^ A[i];
}
nr = 0, poz = 0;
add(T, 21);
int sol = -inf, start = 0, finish = 0;
for(i=1; i<=N; i++) {
nr = transf( S[i] );
p = search(T, 21);
if(sol < (S[i] ^ S[p])) {
sol = S[i] ^ S[p];
start = p + 1;
finish = i;
}
nr = S[i];
poz = i;
add(T, 21);
}
if(start!=finish)
fprintf(f2, "%d %d %d\n", sol, start, finish);
else
for(;;);
fclose(f1); fclose(f2);
return 0;
}