Cod sursa(job #129401)

Utilizator mgntMarius B mgnt Data 29 ianuarie 2008 12:11:42
Problema Xor Max Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 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]; y=0;
    for(y=0, t=1<<(-1+MAXM);t>0;t=t>>1) {
      if((0 == (x & t)) && (0!=f[y+t])) y += t;
    }
    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;
    }
    g[x]=1+i;
    for(t=1; 0 != x; t <<= 1)
      f[x]=1,
       x &= ~t;
  }
  io=fopen("xormax.out", "w");
  fprintf(io,"%d %d %d\n", max, 1+start, 1+stop);
  fclose(io);
  return 0;
}