Cod sursa(job #2307058)

Utilizator Lazar_LaurentiuLazar Laurentiu Lazar_Laurentiu Data 23 decembrie 2018 17:38:08
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MAX 100010
#define NRN (1<<21)
#define x first
#define y second

using namespace std;

int n,ans,ba,ndt,ansi,anss,ansd;
int a[MAX],sx[MAX],ind[NRN];
int nd[NRN][2];
void adauga(int nr,int inda){
  int nda,nrb;
  for(nda=0,nrb=(1<<20);nrb;nrb>>=1){
    ba=((nr|nrb)==nr);
    if(nd[nda][ba])
      nda=nd[nda][ba];
    else{
      ndt++;
      nd[nda][ba]=ndt;
      nda=ndt;
    }
  }
  ind[nda]=inda;
}
int xo(int nr){
  int nda,nrb;
  for(nda=0,nrb=(1<<20);nrb;nrb>>=1){
    ba=((nr|nrb)==nr);
    if(nd[nda][!ba])nda=nd[nda][!ba];
    else nda=nd[nda][ba];
  }
  return ind[nda];
}

int main()
{
    ifstream f ("xormax.in");
    ofstream g ("xormax.out");
    f>>n;
    for(int i=1;i<=n;i++){
      f>>a[i];
      sx[i]=sx[i-1]^a[i];
    }
    adauga(0,0);
    ans=-1;
    for(int i=1;i<=n;i++){
      ansi=xo(sx[i]);
      if((sx[i]^sx[ansi])>ans){
        ans=sx[i]^sx[ansi];
        anss=ansi+1;
        ansd=i;
      }
      adauga(sx[i],i);
    }
    g<<ans<<" "<<anss<<" "<<ansd<<'\n';
    f.close ();
    g.close ();
    return 0;
}