Pagini recente » Cod sursa (job #2543527) | Cod sursa (job #1775227) | Cod sursa (job #618988) | Cod sursa (job #43141) | Cod sursa (job #1703577)
#include <stdio.h>
#include <ctype.h>
#define MAX_BIT 20
#define Nadejde 100000 * (MAX_BIT + 1)
#define Dragoste 4096
#define NIL -1
typedef struct {
int son, pos;
} pair;
int N, ptr, curr, found;
pair trie[2][Nadejde + 1];
char buff[Dragoste];
int last = Dragoste;
char getChar(FILE *f) {
if (last == Dragoste) {
fread(buff, 1, Dragoste, f);
last = 0;
}
return buff[last++];
}
void fscanf(FILE *f, const char *arg, int *result) {
*result = 0;
char c;
do {
c = getChar(f);
} while (!isdigit(c));
do {
(*result) = (*result << 3) + (*result << 1) + c - '0';
c = getChar(f);
} while (isdigit(c));
}
/** Initializeaza trie-ul. **/
void init() {
ptr = 1;
trie[0][0].son = trie[1][0].son = NIL;
}
/** Parcurge trie-ul, alocand si zonele inca nealocate. **/
void insert(int x, int pos) {
int i, bit, nod = 0;
for (i = MAX_BIT; i >= 0; i--) {
bit = (x >> i) & 1;
if (trie[bit][nod].son == NIL) {
trie[0][ptr].son = trie[1][ptr].son = NIL;
trie[bit][nod].son = ptr;
ptr++;
}
nod = trie[bit][nod].son;
}
trie[nod & 1][nod].pos = pos;
}
/** Parcurge trie-ul, obtinand xor-ul maxim cu valoarea "x". **/
void query(int x) {
int i, bit, nod = 0;
curr = 0;
for (i = MAX_BIT; i >= 0; i--) {
bit = (x >> i) & 1;
if (trie[!bit][nod].son != NIL) {
nod = trie[!bit][nod].son;
curr |= (!bit) << i;
} else {
nod = trie[bit][nod].son;
curr |= bit << i;
}
}
curr ^= x;
found = trie[nod & 1][nod].pos;
}
int main(void) {
int i, val, sum = 0, start, stop, max = 0;
FILE *f = fopen("xormax.in", "r");
/* Initializarea datelor. */
init();
/* Citirea datelor. */
fscanf(f, "%d", &N);
insert(sum, 0);
for (i = 1; i <= N; i++) {
fscanf(f, "%d", &val);
sum ^= val;
query(sum);
if (curr > max) {
max = curr;
start = found;
stop = i;
}
insert(sum, i);
}
fclose(f);
/* Afisarea solutiei. */
freopen("xormax.out", "w", stdout);
fprintf(stdout, "%d %d %d\n", max, start + 1, stop);
fclose(stdout);
/// Multumim Doamne!
puts("Doamne ajuta!");
return 0;
}