Cod sursa(job #12299)

Utilizator goguGogu Marian gogu Data 3 februarie 2007 14:34:28
Problema Xor Max Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <stdio.h>
#define Max ((1<<21)-1)
#define Dim 4000
#define pow(x) ((unsigned)1<<(x))
#define am(x) (ok[(x)/32] & pow((x)&31))
#define set(x) ok[x/32] |= pow(x&31)
#define cit(x) x=0; while (lin[poz]>='0'){x=10*x+lin[poz++]-'0';   \
        if (poz==Dim) fread(lin, 1, Dim, stdin), poz=0; }             \
        poz++; if (poz==Dim) fread(lin, 1, Dim, stdin), poz=0; 

int n, a[100100];
unsigned ok[1<<16];

int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    scanf("%d\n", &n); n++;
    char lin[Dim+10];
    fread(lin, 1, Dim, stdin);
    int i, j, poz=0, pow=1;
    ok[0]=1;
    for (i=1; i<n; set(a[i]), ++i){
        cit(j); a[i]=a[i-1]^j;
        if (a[i]>pow) pow=a[i];
        if (am(Max-a[i]))
           for (j=i-1; j>=0; j--)
               if ((a[j]^a[i])==Max){
                  printf("%d %d %d\n", Max, j+1, i);
                  return 0;
               }
    }
    for (i=0; i<n; i++) ok[a[i]/32]=0;
    ok[0]=1;
    while (pow & (pow+1)) pow++;
    for (i=0; i<n; ok[a[i]]=1, ++i)
        if (am(pow-a[i]))
           for (j=i-1; j>=0; j--)
               if ((a[j]^a[i])==pow){
                  printf("%d %d %d\n", pow, j+1, i);
                  return 0;
               }
    int best=-1, p=0, u=0;
    for (i=1; i<n; i++)
        for (j=i-1; j>=0; j--)
            if ((a[j]^a[i]) > best) best=(a[j]^a[i]), p=j, u=i;
    printf("%d %d %d\n", best, p+1, u);
    return 0;
}