Pagini recente » Cod sursa (job #2792753) | Cod sursa (job #2053828) | Cod sursa (job #91166) | Cod sursa (job #163760) | Cod sursa (job #75718)
Cod sursa(job #75718)
//---------------------------------------------------------------------------
//#pragma option -Od
#include <stdio.h>
//---------------------------------------------------------------------------
typedef struct node {
int pos;
struct node *son[2];
} *trie;
//---------------------------------------------------------------------------
typedef unsigned int uint;
#define MAX_N 100000
#define MAX_B 21
//---------------------------------------------------------------------------
node pool[MAX_N* MAX_B];
int pool_pos= 0;
uint X[MAX_N+ 1];
//---------------------------------------------------------------------------
#define xor_sum(L, R) ( X[(R)+ 1] ^ X[L] )
#define A(I) xor_sum(I, I)
//---------------------------------------------------------------------------
int maxim(int A, int B)
{
if (B> A)
return B;
return A;
}
//---------------------------------------------------------------------------
trie add(trie T, uint X, int bit_pos, int pos)
{ //returns the new root...
if (T== NULL) {
T= &pool[pool_pos++];
T->pos= pos;
T->son[0]= T->son[1]= NULL;
}
if (bit_pos< 0)
return T;
int K= (X>> bit_pos) & 1;
T->son[K]= add(T->son[K], X, bit_pos- 1, pos);
return T;
}
//---------------------------------------------------------------------------
int get_start_pos(trie T, uint X, int bit_pos, int pos)
{ //returns maximum start pos
if (T== NULL)
return pos; //returns best pos found so far...
int K= (X>> bit_pos) & 1;
trie S= T->son[K ^ 1];
if (/*K== 0 && */S!= NULL)
pos= S->pos; //in acest caz castigam un bit...
if (S== NULL)
S= T->son[K];
// if (S!= NULL)
// pos= maxim(pos, S->pos); //cautam pos cat mai mare...
return get_start_pos(S, X, bit_pos -1, pos);
}
//---------------------------------------------------------------------------
void xormax()
{
FILE *F= fopen("xormax.in", "rt");
int N;
fscanf(F, "%u", &N);
trie root= NULL;
uint max= 0;
int max_start= 0,
max_end= 0;
/*
La fiecare pas se cauta 'spos' cel mai mare a.i.
X[I+ 1] xor X[spos] sa fie maxim...
*/
X[0]= 0;
for (int I= 0; I< N; I++) {
uint K;
fscanf(F, "%u", &K);
X[I+ 1]= X[I] ^ K;
int spos= get_start_pos(root, X[I+ 1], MAX_B- 1, 0);
uint mx= xor_sum(spos, I);
if (mx> max) {
max= mx;
// max_start= spos;
max_end= I;
}
root= add(root, X[I+ 1], MAX_B- 1, I+ 1);
//asociaza X[I+ 1] cu pozitia 'I+ 1' pentru ca dupa
//cautare, in xor_sum, L sa fie egal cu spos...
}
fclose(F);
for (int I= max_end; --I>= 0; )
if (xor_sum(I, max_end)== max) {
max_start= I;
break;
}
FILE *G= fopen("xormax.out", "wt");
fprintf(G, "%u %u %u\n", max, max_start+ 1, max_end+ 1);
fclose(G);
}
//---------------------------------------------------------------------------
int vec_xor(int L, int R)
{ //este inlocuit de macro: xor_sum(L, R)
//X[L ]= 0..L-1
//X[R+1]= 0..L..R
//L..R= X[R+ 1] ^ X[L]
return X[R+ 1] ^ X[L];
}
//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
xormax();
return 0;
}
//---------------------------------------------------------------------------