Pagini recente » Cod sursa (job #1405778) | Cod sursa (job #1370055) | Cod sursa (job #1438910) | Cod sursa (job #1438915) | Cod sursa (job #2818386)
// This program was written on 15.12.2021
// for problem xormax
// by Mircea Rebengiuc
#include <stdio.h>
#include <ctype.h>
#define MAXN 100000
#define MAXL 21
#define MAXVAL (1 << MAXL)
#define MAXT (MAXN * MAXL)
#define NIL -1
struct Trie {
int adj[2];
int frecv;
int p2;
} trie[MAXT];
int nt;
int binary[MAXL + 1];
int last[MAXVAL];
static inline void toBinary( int x ){
int i = MAXL;
for( ; i-- ; ){
binary[i] = (x & 1);
x >>= 1;
}
binary[MAXL] = NIL;
}
static inline int newNode(){
trie[nt].frecv = 0;
trie[nt].adj[0] = NIL;
trie[nt].adj[1] = NIL;
return nt++;
}
int TRIEinsert( int root, int *str ){
if( *str == NIL ){
trie[root].frecv++;
return root;
}
if( trie[root].adj[*str] == NIL ){
trie[root].adj[*str] = newNode();
trie[trie[root].adj[*str]].p2 = (trie[root].p2 >> 1);
}
return TRIEinsert(trie[root].adj[*str], str + 1);
}
int TRIEquery( int root, int *str ){
int newbit = 1 ^ (*str);
if( *str == NIL )
return 0;
if( trie[root].adj[newbit] == NIL )
newbit ^= 1;
return ((*str) ^ newbit) * trie[root].p2 + TRIEquery(trie[root].adj[newbit], str + 1);
}
void TRIEprint( int root, int indent ){
int i;
if( root == NIL )
return;
TRIEprint(trie[root].adj[0], indent + 1);
for( i = 0 ; i < indent ; i++ )
fputs(" ", stdout);
printf("%d\n", trie[root].frecv);
TRIEprint(trie[root].adj[1], indent + 1);
}
FILE *fin, *fout;
static inline int fgetint(){
int n = 0, ch, semn = 1;
while( isspace(ch = fgetc(fin)) );
if( ch == '-' ){
semn = -1;
ch = fgetc(fin);
}
do
n = n * 10 + ch - '0';
while( isdigit(ch = fgetc(fin)) );
return n * semn;
}
int main(){
fin = fopen("xormax.in", "r");
fout = fopen("xormax.out", "w");
int n, i, xor_part;
int cand, max, maxl, maxr;
nt = 0;
newNode();
trie[0].p2 = (1 << (MAXL - 1));
n = fgetint();
xor_part = 0;
last[0] = 0;
max = maxl = maxr = 0;
for( i = 0 ; i < n ; i++ ){
toBinary(xor_part);
TRIEinsert(0, binary);
last[xor_part] = i;
xor_part ^= fgetint();
toBinary(xor_part);
cand = TRIEquery(0, binary);
if( cand > max ){
max = cand;
maxr = i;
maxl = last[cand ^ xor_part];
}
}
fprintf(fout, "%d %d %d\n", max, maxl + 1, maxr + 1);
fclose(fin);
fclose(fout);
return 0;
}