Cod sursa(job #459564)

Utilizator crawlerPuni Andrei Paul crawler Data 30 mai 2010 11:23:18
Problema Xor Max Scor 25
Compilator c Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <stdio.h>

int t[1<<22];
int a[100100], n;
int best, start, stop;

void read() {
  FILE *f = fopen("xormax.in", "r");
  
  fscanf(f, "%d", &n);
  
  int i;
  
  for (i = 1; i <= n; ++i)
    fscanf(f, "%d" , a+i);
  
  fclose(f);
}

void solve() {
  int i, j;
  
  for (i = 0; i < (1<<22); ++i)
    t[i] = -1;

  t[0] = 0;

  int xor_sum = 0;
    
  for (i = 1; i <= n; ++i) {
    xor_sum ^= a[i];
    //querry
    int tree_index = 0;
    for (j = 21; j >= 0; --j) {
      if (t[tree_index + ((xor_sum & (1<<j)) ^ (1<<j))] >= 0)
        tree_index += ((xor_sum & (1<<j)) ^ (1<<j));
      else
        tree_index += (xor_sum & (1<<j));
    }
    if (best < (tree_index ^ xor_sum)) {
      best = (tree_index ^ xor_sum);
      stop = i;
      start = t[tree_index] + 1;
    }
    //update
    tree_index = 0;
    for (j = 21; j >= 0; --j) {
      tree_index += xor_sum & (1<<j);
      t[tree_index] = i;
    }
  }
}

void write() {
  FILE *f = fopen("xormax.out", "w");
  
  fprintf(f, "%d %d %d\n", best, start, stop);
  
  fclose(f);
}

int main() {
  read();
  solve();
  write();
  return 0;
}