Pagini recente » Cod sursa (job #1043309) | Cod sursa (job #2558665) | Cod sursa (job #2265102) | Cod sursa (job #624996) | Cod sursa (job #397982)
Cod sursa(job #397982)
#include <stdio.h>
#include <stdlib.h>
#define NMAX 100005
#define llong int
FILE *fin,*fout;
struct trie{
llong ind;
trie *z,*u;
};
trie * t;
llong a[NMAX], sum[NMAX];
llong start[NMAX],end[NMAX],max;
llong n;
void addTrie (trie * t, llong indice, llong n, llong biti)
{trie *p, *q;
llong i, l = 0;;
p = t;
for (i = 1; i <= biti; i++)
{
l = l << 1;
l = l ^ ( n & 1 );
n = n >> 1;
}
n = l;
for (i = 1; i <= biti; i++)
{
l = n & 1;
if ( l == 1 )
{
if ( i == biti && p -> u == NULL)
{
q = (trie *) malloc(sizeof(trie));
q -> z = q -> u = NULL;
q -> ind = indice;
p -> u = q;
}
else if (p -> u == NULL)
{
q = (trie *) malloc(sizeof(trie));
q -> z = q -> u = NULL;
q -> ind = 0;
p -> u = q;
}
p = p -> u;
}
else{
if ( i == biti && p -> z == NULL)
{
q = (trie *) malloc(sizeof(trie));
q -> z = q -> u = NULL;
q -> ind = indice;
p -> z = q;
}
else if (p -> z == NULL)
{
q = (trie *) malloc(sizeof(trie));
q -> z = q -> u = NULL;
q -> ind = 0;
p -> z = q;
}
p = p -> z;
}
n = n >> 1;
}
}
llong findTrie (trie * t, llong n, llong biti)
{trie *p;
llong i, l = 0;
p = t;
for (i = 1; i <= biti; i++)
{
l = l << 1;
l = l ^ ( n & 1 );
n = n >> 1;
}
n = l;
for (i = 1; i <= biti; i++)
{
l = n & 1;
if ( l == 0 )
{
if ( p -> u != NULL)
{
p = p -> u;
}
else p = p -> z;
}
else{
if ( p -> z != NULL)
{
p = p -> z;
}
else p = p -> u;
}
n = n >> 1;
}
return p -> ind;
}
int main()
{llong i, biti, indMax, j=0;
fin = fopen ("xormax.in","rt");
fout = fopen ("xormax.out","wt");
fscanf(fin,"%d",&n);
max = 1;
for (i = 1; i <= n; i++)
{
fscanf(fin,"%d",&a[i]);
sum[i] = sum[i-1] ^ a[i];
if (max < sum[i]) max = sum[i];
}
if ( n == 1)
{
fprintf(fout,"%d 1 1\n",sum[1]);
return 0;
}
i = 0;
while (max)
{
max = max >> 1;
i++;
}
biti = i;
max = -1;
t = (trie *) malloc(sizeof(trie));
t -> ind = 0;
t -> z = t -> u = NULL;
for (i = 1; i <= n; i++)
{
addTrie (t,i,sum[i],biti);
}
for (i = 1; i <= n; i++)
{
indMax = findTrie (t,sum[i],biti);
//fprllongf(fout,"%d %d %d\n\n",i,indMax,sum[i] ^ sum[indMax]);
if (indMax != i)
{
if ( (sum[i] ^ sum[indMax]) > max)
{
max = sum[i] ^ sum[indMax];
j = 0;
if ( i > indMax)
{
start[j] = indMax;
end[j] = i;
}
else{
start[j] = i;
end[j] = indMax;
}
j = 1;
}
else if ( (sum[i] ^ sum[indMax]) == max )
{
if ( i > indMax)
{
start[j] = indMax;
end[j] = i;
}
else
{
start[j] = i;
end[j] = indMax;
}
j++;
}
}
}
indMax = 0;
for (i = 0 ; i < j; i++)
{
if ( end[i] < end[indMax] ) indMax = i;
}
for (i = 0; i < j; i++)
{
if ( i != indMax && end[i] == end[indMax] && start[i] > start[indMax] ) indMax = i;
}
fprintf(fout,"%d %d %d\n",max,start[indMax]+1,end[indMax]);
fclose(fin);
fclose(fout);
return 0;
}