Cod sursa(job #70428)

Utilizator gigi_becaliGigi Becali gigi_becali Data 5 iulie 2007 22:11:13
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 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
ull x[maxn];
ull 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==43)return;
  if(!T->n[val[i]])
    {
      T->n[val[i]]=new nod;
      memset(T->n[val[i]], 0, sizeof(T->n));
    }
  if(i==42){T->p=pi;} 
  insert(T->n[val[i]], i+1);
}

int find(nod*T, int i)
{
  if(i==42)
    {
      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("%lld ", x+i);
  A[1]=x[1];
  int i,j;
  for(i=2;i<=n;++i) A[i]=A[i-1]^x[i];
  ull smax=0, p1, p2;

  for(i=1;i<=n;++i)
    {
      pi=i;
      bitset<42>aa(A[i]);
      for(j=0;j<42;++j) val[j]=aa[j];
      reverse(val, val+42);
          insert(T, 0);
      memset(sol, 0, sizeof(sol));
      int pp1= find(T, 0);
    
       for(j=0;j<42;++j)sol[j]^=val[j];
     ull s=0;
       for(j=41;j>=0;--j)s+=(1<<(41-j))*sol[j];
       //printf("%d\n", s);
       if(smax<s) 
	 {
	   smax=s;
	   p2=i;
	   p1=pp1+1;
	 }

	 
       //printf("\n");
    }

  
  // printf("%d\n", (-3)^(2));
  freopen("xormax.out","w",stdout);  
  printf("%lld %lld %lld\n", smax, p1, p2);

  return 0;
}