Cod sursa(job #792530)

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

#define MAXN 100000
#define DIGITS 22

int N;
int V[MAXN];
int X[MAXN + 1];

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);
}

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

  void add(int x, int bit_pos, int end_pos)
  {
    if(bit_pos == -1)
      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 solve()
{
  int a, b, 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++)
  {
    current_xor ^= V[i];
    X[i + 1] = current_xor;
    int best_pos = trie->get_best_ep(current_xor, DIGITS);
    actsol(current_xor ^ X[best_pos], best_pos + 1, i + 1, a, b, c);
    trie->add(current_xor, DIGITS, i + 1);
  }

  printf("%d %d %d\n", a, b, c);
}

int main()
{
  freopen("xormax.in", "r", stdin);
  freopen("xormax.out", "w", stdout);
  read();
  solve();
  return 0;
}