Pagini recente » Cod sursa (job #2287762) | Cod sursa (job #2414905) | Cod sursa (job #319663) | Cod sursa (job #1495304) | Cod sursa (job #2772005)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("xormax.in");
ofstream fout ("xormax.out");
void numar_binar (int x, int sir[33])
{
int pozitie_sir=30;
while (x!=0)
{
sir[pozitie_sir] = x%2;
x = x/2;
pozitie_sir--;
}
}
struct nod_arbore
{
nod_arbore *pointer0;
nod_arbore *pointer1;
int valoare;
int indice;
};
void initializare_nod_arbore_nou (nod_arbore *oarecare)
{
oarecare->pointer0 = NULL;
oarecare->pointer1 = NULL;
oarecare->valoare = 0;
oarecare->indice = 0;
}
void inserare_arbore (nod_arbore *R, int sir[33])
{
nod_arbore *parcurgere = R;
for (int i=0; i<31; i++)
{
if (sir[i]==0)
{
if ((parcurgere->pointer0)==NULL)
{
parcurgere->pointer0 = new nod_arbore;
parcurgere = parcurgere->pointer0;
initializare_nod_arbore_nou(parcurgere);
}
else
parcurgere = parcurgere->pointer0;
}
else if (sir[i]==1)
{
if ((parcurgere->pointer1)==NULL)
{
parcurgere->pointer1 = new nod_arbore;
parcurgere = parcurgere->pointer1;
initializare_nod_arbore_nou(parcurgere);
}
else
parcurgere = parcurgere->pointer1;
}
}
parcurgere->valoare = sir[31];
parcurgere->indice = sir[32];
}
void cautare_maxim (nod_arbore *R, int sir[33], int partial, int &maximul, int &initialul, int &finalul)
{
nod_arbore *parcurgere = R;
for (int i=0; i<31; i++)
{
if (sir[i]==0)
{
if ((parcurgere->pointer1)!=NULL)
parcurgere = parcurgere->pointer1;
else if ((parcurgere->pointer0)!=NULL)
parcurgere = parcurgere->pointer0;
else
return;
}
else if (sir[i]==1)
{
if ((parcurgere->pointer0)!=NULL)
parcurgere = parcurgere->pointer0;
else if ((parcurgere->pointer1)!=NULL)
parcurgere = parcurgere->pointer1;
else
return;
}
}
if (((parcurgere->valoare)^partial)>=maximul)
{
maximul = ((parcurgere->valoare)^partial);
initialul = parcurgere->indice+1;
finalul = sir[32];
}
}
void rsd (nod_arbore *R)
{
if (R!=NULL)
{
cout << R->valoare << " ";
rsd(R->pointer0);
rsd(R->pointer1);
}
}
int main()
{
int n; int v[100005];
int partial=0,maximul=0,initialul=0,finalul=0;
nod_arbore *R = new nod_arbore;
initializare_nod_arbore_nou(R);
fin >> n;
for (int i=1; i<=n; i++)
{
fin >> v[i];
partial = partial^(v[i]);
int sir[33]={0};
sir[31] = partial;
sir[32] = i;
numar_binar(partial,sir);
inserare_arbore(R,sir);
cautare_maxim(R,sir,partial,maximul,initialul,finalul);
}
fout << maximul << " " << initialul << " " << finalul;
return 0;
}