Cod sursa(job #990130)

Utilizator Corneliu10Dumitru Corneliu Corneliu10 Data 27 august 2013 15:41:22
Problema Xor Max Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.91 kb
#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);
}