Cod sursa(job #792526)

Utilizator andrei.sfrentSfrent Andrei andrei.sfrent Data 27 septembrie 2012 14:40:36
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.88 kb
#include <cstdio>
#include <cstdlib>
#include <cassert>

#define MAXN 100000

int N, V[MAXN];

void actsol(int max, int start, int stop,
            int& oldmax, int& oldstart, int& oldstop)
{
  if(max > oldmax ||
     (max == oldmax && stop < oldstop) ||
     (max == oldmax && stop == oldstop && start > oldstart))
  {
    oldmax = max;
    oldstart = start;
    oldstop = stop;
  }
}

void read()
{
  scanf("%d", &N);
  for(int i = 0; i < N; i++)
    scanf("%d", V + i);
}

void brut(int& a, int& b, int& c)
{
  a = -1;
  for(int i = 0; i < N; i++)
  {
    for(int j = i; j < N; j++)
    {
      int xor_val = 0;
      for(int k = i; k <= j; k++)
        xor_val ^= V[k];
      actsol(xor_val, i, j, a, b, c);
    }
  }
  b++, c++;
}

struct node
{
  ~node()
  {
    if(next[0] != NULL)
      delete(next[0]);
    if(next[1] != NULL)
      delete(next[1]);
  }

  explicit node()
  {
    next[0] = next[1] = NULL;
    ep = -1;
  }

  void add(int x, int bit_pos, int end_pos)
  {
    if(bit_pos == -1)
    // this is the node representing the number, do stuff
    {
      ep = end_pos;
    }
    else
    {
      int bit = (((1 << bit_pos) & x) != 0);
      if(next[bit] == NULL)
        next[bit] = new node();
      next[bit]->add(x, bit_pos - 1, end_pos);
    }
  }

  int get_best_ep(int current_xor, int bit_pos)
  {
    if(bit_pos == -1)
      return ep;
    else
    {
      int bit = (((1 << bit_pos) & current_xor) != 0);
      if(next[1 - bit] != NULL) // this is the best choice
        return next[1 - bit]->get_best_ep(current_xor, bit_pos - 1);
      else
        return next[bit]->get_best_ep(current_xor, bit_pos - 1);
    }
  }

  node* next[2];
  int ep;
};

void pbin(int x, int len)
{
  if(len == 0) return;
  else
  {
    pbin(x >> 1, len - 1);
    printf("%d", x & 1);
  }
}

#define DIGITS 22

void pbin(int x)
{
  pbin(x, DIGITS);
  printf("\n");
}

int X[MAXN + 1];

void fast(int& a, int& b, int& c)
{
  node *trie = new node();
  int current_xor = 0;
  a = -1;

  trie->add(current_xor, DIGITS, 0);
  X[0] = current_xor;

  for(int i = 0; i < N; i++)
  {
//    printf("Step %d:\n", i);
    current_xor ^= V[i];
//    printf("current_xor (X[%d]) = ", i + 1); pbin(current_xor);
    X[i + 1] = current_xor;
    int best_pos = trie->get_best_ep(current_xor, DIGITS);
//    printf("best_pos = %d\n", best_pos);
    actsol(current_xor ^ X[best_pos], best_pos + 1, i + 1, a, b, c);
    trie->add(current_xor, DIGITS, i + 1);
//    printf("\n");
  }
  delete trie;
}

void gen()
{
  N = 100;
  for(int i = 0; i < N; i++)
    V[i] = rand() % (1 << DIGITS);
}

void solve()
{
  int fa, fb, fc;
  fast(fa, fb, fc);

//  int ba, bb, bc;
//  brut(ba, bb, bc);
//  assert(fa == ba && fb == bb && fc == bc);

  printf("%d %d %d\n", fa, fb, fc);
}

int main()
{
  freopen("xormax.in", "r", stdin);
  freopen("xormax.out", "w", stdout);
  read();
//  for(int i = 0; i < 10000; i++)
//  {
//    gen();
  solve();
//  }
  return 0;
}