Cod sursa(job #182426)

Utilizator tm_raduToma Radu tm_radu Data 20 aprilie 2008 21:28:59
Problema Xor Max Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <stdio.h>
#define NM 100001

int n, a[NM], x[NM];
int d[23];
int i, j, k, b, xmax, imax, pow;
typedef struct trie {
	int niv;
	trie* c[2];
} TRIE, *PTRIE;
PTRIE root = new TRIE;

void Insert(trie* nod, int pos);    
void Query(trie* nod, int pos);

int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
	scanf("%d", &n);
	root->c[0] = root->c[1] = 0;
	for ( i = 1; i <= n; i++ )
	{
		scanf("%d", &a[i]), x[i] = x[i-1] ^ a[i];
		j = 0, pow = 1;
		while ( x[i] >= pow ) j++, pow *= 2;
		if ( x[i] == 0 ) j = 1;
		b = b > j ? b : j;
	}
	// Build trie
	j = b; k = x[i];
	while ( j ) d[j] = k % 2, k /= 2, j--;
	Insert(root, 1);
	xmax = a[1];
	// Solve
	for ( i = 2; i <= n; i++ )
	{
	    // Solve for i
	    xmax = xmax > a[i] ? xmax : x[i];
	    j = b; k = x[i];
		while ( j ) d[j] = k % 2, k /= 2, j--;
		Query(root, 1);
		for ( j = 1; j <= b; j++ )
		    k = k*2 + d[j];
        if ( xmax < (x[i]^k) ) xmax = x[i]^k, imax = i;
        // Insert i
        j = b; k = x[i];
		while ( j ) d[j] = k % 2, k /= 2, j--;
		Insert(root, 1);
    }
    
    for ( j = 1; j < imax; j++ )
        if ( (x[j] ^ x[imax]) == xmax ) break;
    
    printf("%d %d %d\n", xmax, j+1, imax);    
	return 0;
}

void Insert(trie* nod, int pos)
{
	if ( pos > b ) return;
	if ( nod->c[d[pos]] )
		Insert(nod->c[d[pos]], pos+1);
	else
	{
		trie* q = new trie;
		q->niv = pos;
        q->c[0] = q->c[1] = 0;
		nod->c[d[pos]] = q;
		Insert(q, pos+1);
	}
}

void Query(trie* nod, int pos)
{
    if ( pos > b ) return;
    int np = 1-d[pos];
    if ( nod->c[np] )
        d[pos] = np,
        Query(nod->c[np], pos+1);
    else
        Query(nod->c[1-np], pos+1);
}