Pagini recente » Cod sursa (job #178234) | Cod sursa (job #2403807) | Cod sursa (job #2764726) | Cod sursa (job #2515) | Cod sursa (job #429882)
Cod sursa(job #429882)
// Catalin Balan
// Tue Mar 30 15:08:49 EEST 2010
// Infoarena - Xor Max
#include <cstdio>
#include <cstdlib>
using namespace std;
#define NMAX 100005
#define max(a,b) (a>b?a:b)
#define FIN "xormax.in"
#define FOUT "xormax.out"
// PARSARE
#define CHUNK 8192
char g_buf[CHUNK];
int g_p=CHUNK-1;
inline int get()
{
int x = 0;
while (g_buf[g_p] < '0' || g_buf[g_p] > '9')
if (++g_p == CHUNK) fread(g_buf,1,CHUNK,stdin), g_p=0;
while (g_buf[g_p] >= '0' && g_buf[g_p] <= '9')
{
x = x*10 + g_buf[g_p]-'0';
if (++g_p == CHUNK) fread(g_buf,1,CHUNK,stdin), g_p=0;
}
return x;
}
// END PARSARE
struct tNod {
int cine;
tNod *kid[2];
};
tNod *root;
int n, nbiti;
int a[NMAX];
void addToTrie( int x, int j )
{
tNod *p = root, *q;
for ( int i = nbiti; i > 0; i>>=1)
{
int bit = ( (x&i) != 0);
if ( !p->kid[bit] )
{
q = new tNod;
q->cine = NULL;
q->kid[0] = q->kid[1] = NULL;
p->kid[bit] = q;
}
p = p->kid[bit];
}
p->cine = j;
}
int cauta( int x )
{
tNod *p = root;
for (int i = nbiti; i > 0; i>>=1)
{
int bit = ( (x&i) == 0 );
if ( p->kid[bit] ) p = p->kid[bit];
else p = p->kid[1-bit];
}
return p->cine;
}
int main(int argv, char ** argc)
{
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
n = get();
a[0] = 0;
int maxim = 0;
for (int i = 1; i <= n; ++i)
{
int aux = get();
a[i] = a[i-1]^aux;
maxim = max(maxim, a[i]);
}
for (nbiti = 1; nbiti <= maxim; nbiti<<=1);
nbiti>>=1;
root = new tNod;
root->cine = NULL;
root->kid[0] = root->kid[1] = NULL;
addToTrie(0,0);
maxim = -1;
int p1 = 0, p2 = 0;
for (int i = 1; i <= n; ++i)
{
int care = cauta( a[i] );
fprintf( stderr, "%d %d - %d %d = %d\n", i, a[i], care, a[care], a[i]^a[care] );
if ( (a[i]^a[care]) > maxim )
{
maxim = a[i]^a[care];
p1 = care+1;
p2 = i;
}
addToTrie(a[i], i);
}
printf("%d %d %d\n", maxim, p1, p2);
return EXIT_SUCCESS;
}