Pagini recente » Cod sursa (job #3282736) | Cod sursa (job #2068135) | Cod sursa (job #1252634) | Cod sursa (job #494497) | Cod sursa (job #990130)
Cod sursa(job #990130)
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
int32_t cnt[4194304];
/**
cnt[x] number of sequences of xorsum x
cnt[2097152+x/2] number of sequences of xorsum starting with first 20 bits of x
*/
int32_t v[100002];
int bases[21]=
{0, 2097152, 3145728, 3670016,
3932160, 4063232, 4128768, 4161536,
4177920, 4186112, 4190208, 4192256,
4193280, 4193792, 4194048, 4194176,
4194240, 4194272, 4194288, 4194296,
4194300};
int n;
void addcnt(int x, int q)
{
int base=0,i;
for (i=0; i<21; i++)
{
cnt[base+x]+=q;
x/=2;
base+=1<<(21-i);
}
}
int bestpos;
int best;
int crtbest;
int bestlast;
int findbest(x)
{
int base=x^0x1fffff;
int i;
for (i=20; i>=0; i--)
{
int bbit=1<<i;
int c0=cnt[bases[i]+(base>>i)];
int c1=cnt[bases[i]+((base^bbit)>>i)];
if (!c0)
{
base^=bbit;
}
}
return x^base;
}
int main(int argc, char *argv[])
{
int i,x;
FILE *fin=fopen("xormax.in","r");
fscanf(fin,"%d ",&n);
for (i=0; i<n; i++) fscanf(fin,"%d ",&v[n-1-i]);
memset(cnt,0,sizeof(cnt));
fclose(fin);
x=0;
bestpos=0;
best=0;
for (i=0; i<n; i++)
{
x=x^v[i];
addcnt(x,1);
}
x=0;
for (i=0; i<n; i++)
{
crtbest=findbest(x);
if (crtbest>=best)
{
best=crtbest;
bestpos=i;
}
x=x^v[i];
addcnt(x,-1);
}
bestlast=bestpos;
x=0;
crtbest=0;
for (i=bestpos; i<n; i++)
{
x=x^v[i];
if (x>crtbest)
{
crtbest=x;
bestlast=i;
}
}
FILE *fou=fopen("xormax.out","w");
fprintf(fou,"%d %d %d",crtbest,n-bestlast,n-bestpos);
fclose(fou);
}