Cod sursa(job #469651)

Utilizator APOCALYPTODragos APOCALYPTO Data 8 iulie 2010 15:56:38
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
using namespace std;
#include <cstdio>
#include <iostream>
#include <bitset>
#include <algorithm>
#define maxn 100001
struct nod {int p; nod *n[2];};
int n;
#define un unsigned
#define ull long long
un int x[maxn];
un int A[maxn];
nod *T;
bool val[64];
bool sol[64];
int pi;

void init()
{
  T=new nod;
  memset(T->n, 0, sizeof(T));
}

void insert(nod *T, int i)
{

  if(i==25)return;
  if(!T->n[val[i]])
    {
      T->n[val[i]]=new nod;
      memset(T->n[val[i]], 0, sizeof(T->n));
    }
  if(i==24){T->p=pi;}
  insert(T->n[val[i]], i+1);
}

int find(nod*T, int i)
{
  if(i==24)
    {
      if(T->n[1-val[i]]){sol[i]=1-val[i]; return T->p;}
      else if(T->n[val[i]]) {sol[i]=val[i];return T->p;}
      else return 0;
    }

  if(T->n[1-val[i]]){sol[i]=1-val[i];  return find(T->n[1-val[i]],i+1);}
  else if(T->n[val[i]]) {sol[i]=val[i]; return find(T->n[val[i]],i+1);}
  return 0;
}

int main()
{
  init();
  freopen("xormax.in","r",stdin);

  scanf("%d\n", &n);
  for(int i=1;i<=n;++i) scanf("%d ", x+i);
  A[1]=x[1];
  int i,j;
  for(i=2;i<=n;++i) A[i]=A[i-1]^x[i];
  un int smax=0, p1, p2;

  for(i=1;i<=n;++i)
    {
      pi=i;
      bitset<24>aa(A[i]);
      for(j=0;j<24;++j) val[j]=aa[j];
      reverse(val, val+24);
          insert(T, 0);
      memset(sol, 0, sizeof(sol));
      int pp1= find(T, 0);

       for(j=0;j<24;++j)sol[j]^=val[j];
     un int s=0;
       for(j=23;j>=0;--j)s+=(1<<(23-j))*sol[j];
       //printf("%d\n", s);
       if(smax<s)
	 {
	   smax=s;
	   p2=i;
	   p1=pp1+1;
	 }


       //printf("\n");
    }


  // printf("%d\n", (-3)^(2));
  int ok=1;
  for(i=1;i<=n;++i) if(x[i]) ok=0;


  freopen("xormax.out","w",stdout);
  if(ok) printf("0 %d %d\n", 1, 1);
  else
  printf("%d %d %d\n", smax, p1, p2);

  return 0;
}