Cod sursa(job #70423)

Utilizator gigi_becaliGigi Becali gigi_becali Data 5 iulie 2007 22:05:00
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
using namespace std;
#include <cstdio>
#include <iostream>
#include <bitset>
#include <algorithm>
#define maxn 100001
struct nod {int p; nod *n[2];};
int n;
int x[maxn];
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==33)return;
  if(!T->n[val[i]])
    {
      T->n[val[i]]=new nod;
      memset(T->n[val[i]], 0, sizeof(T->n));
    }
  if(i==32){T->p=pi;} 
  insert(T->n[val[i]], i+1);
}

int find(nod*T, int i)
{
  if(i==32)
    {
      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];
  int smax=0, p1, p2;

  for(i=1;i<=n;++i)
    {
      pi=i;
      bitset<32>aa(A[i]);
      for(j=0;j<32;++j) val[j]=aa[j];
      reverse(val, val+32);
          insert(T, 0);
      memset(sol, 0, sizeof(sol));
      int pp1= find(T, 0);
    
       for(j=0;j<32;++j)sol[j]^=val[j];
       int s=0;
       for(j=31;j>=0;--j)s+=(1<<(31-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("%d %d %d\n", smax, p1, p2);

  return 0;
}