Cod sursa(job #500745)

Utilizator FERI24Forrai Francisc FERI24 Data 12 noiembrie 2010 22:51:51
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <stdio.h>
#include <string>

#define FISIN  "xormax.in"
#define FISOUT "xormax.out"

#define MAXN  100001

int n;
int a[MAXN], pref[MAXN];

int best = -1, bstart, bend;

struct node {
  node() { child[0] = child[1] = NULL; }
  typedef node* pnode;
  int poz;
  pnode child[2];
} *root;

void insert(int poz, int num) {
  node* n = root;
  for (int i = 20; i >= 0; --i) {
    int bit = num & (1 << i) ? 1 : 0;
    if (!n->child[bit]) n->child[bit] = new node();
    n = n->child[bit];
  }
  n->poz = poz;
}

int find_best_match(int num) {
  node *n = root;
  for (int i = 20; i >= 0; --i) {
    int bit = num & (1 << i) ? 0 : 1;    
    n = n->child[bit] ? n->child[bit] : n->child[bit ^ 1];
  }
  return n->poz;
}

void print_tree(node *n, std::string pref) {
  if (!n->child[0] && !n->child[1]) {
    printf("%s -> %d\n", pref.c_str(), n->poz);
  }

  if (n->child[0]) print_tree(n->child[0], pref + "0");
  if (n->child[1]) print_tree(n->child[1], pref + "1");
}

int main() {
  root = new node();
  insert(0, 0);
  
  FILE *f = fopen(FISIN, "rt");
  fscanf(f, "%d", &n);
  pref[0] = 0;
  for (int i = 1; i <= n; ++i) {
    fscanf(f, "%d", a + i);
    pref[i] = pref[i - 1] ^ a[i];
    int poz = find_best_match(pref[i]);
    int now = pref[i] ^ pref[poz];
    if (now > best) {
      best = now;
      bstart = poz + 1;
      bend = i;
    }
    insert(i, pref[i]);
  }
  fclose(f);

  //  print_tree(root,  "");

  f = fopen(FISOUT, "wt");
  fprintf(f, "%d %d %d\n", best, bstart, bend);
  fclose(f);

  return 0;
}