Pagini recente » Cod sursa (job #2145830) | Cod sursa (job #2336756) | Cod sursa (job #2111104) | Cod sursa (job #1198913) | Cod sursa (job #182426)
Cod sursa(job #182426)
#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);
}