Cod sursa(job #129433)

Utilizator mgntMarius B mgnt Data 29 ianuarie 2008 15:01:55
Problema Xor Max Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <cstdio>
using namespace std;

int const MAXN = 100000;
int const MAXM=21;

static int a[MAXN], b[MAXN], f[1<<MAXM], g[1<<MAXM];

int main() {
  int n, i;
  FILE * io;
  io=fopen("xormax.in", "r");
  setvbuf(io, NULL, _IOFBF, 1024 * 1024);
  fscanf(io,"%d", &n);
  for(i=0;i<n;i+=10) {
    fscanf(io, "%d %d %d %d %d %d %d %d %d %d",
       &a[0 + i], &a[1 + i], &a[2 + i], &a[3 + i], &a[4 + i],
       &a[5 + i], &a[6 + i], &a[7 + i], &a[8 + i], &a[9 + i]);
  }
  for( ;i<n;i++) {
    fscanf(io, "%d", &a[i]);
  }
  fclose(io);
  b[0]=a[0]; for(i=1;i<n;i++) b[i]=a[i] ^ b[i-1];
  int max=-1, start=-1, stop=-1, x, y, z, t;
  for(i=0;i<n;i++) {
    x=b[i];
    // cautare
    for(t=1<<(MAXM-1); 0 !=t; t>>=1) {
      if((0==(x&t)) && (0!=f[t])) break;
    }

    for(y=t;0!=t;t>>=1) {
      if((0!=(f[y]&t)) && ((0==(x&t)) || (0==(f[y]%t)))) y |= t;
    }
    
    // marire
    if(0!=y) {
      z=y | x;
       if(max<z) max=z, start=g[y], stop=i;
    } else {
      if(max<x) max=x, start=i, stop=i;
    }
   // memorare
    g[x]=1+i;
    if(0 != x) {
      for(t=1<<(MAXM-1);0==(x&t);t>>=1); // for

      for(y=t;0 != t;t>>=1)
        if(0 != (x&t)) f[y] |= t, y |= t; // for
    } // if
  }
  io=fopen("xormax.out", "w");
  fprintf(io,"%d %d %d\n", max, 1+start, 1+stop);
  fclose(io);
  return 0;
}