Cod sursa(job #3124608)

Utilizator Luca529Taschina Luca Luca529 Data 29 aprilie 2023 15:03:11
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int b[23], poz, y[100001];

struct nod{
    int p;
    nod * x[2];
};

void Update(nod * & R, int p, int i)
{if(R==NULL)
 {R=new nod;
  R->x[1]=R->x[0]=NULL;
  R->p=0;
 }

 if(i<22)Update(R->x[b[i+1]], p, i+1);
 else R->p=p;
}

void Query(nod *R, int i)
{if(i<22)
 {if(R->x[!b[i+1]]!=NULL)Query(R->x[!b[i+1]], i+1);
  else Query(R->x[b[i+1]], i+1);
 }
 else poz=R->p;
}

int main()
{   nod *R=NULL;
    int n, a, maxi=0, i1=1, i2=1, sum=0;
    fin>>n;

    Update(R, 0, 0);
    for(int i=1;i<=n;i++)
    {fin>>a;
     sum^=a;
     y[i]=sum;

     for(int j=1;j<=22;j++)
     b[j]=0;

     int ca=sum, k=23;
     while(ca!=0)
     {b[--k]=ca%2;
      ca/=2;
     }

     Query(R, 0);
     int v=sum^y[poz];

     if(v>maxi)maxi=v, i1=poz+1, i2=i;
     Update(R, i, 0);
    }
    fout<<maxi<<" "<<i1<<" "<<i2;
    return 0;
}