Pagini recente » Cod sursa (job #2448060) | Cod sursa (job #835348) | Cod sursa (job #2791470) | Cod sursa (job #333020) | Cod sursa (job #2774938)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct trie
{
trie()
{
poz = 0;
fiu[0] = fiu[1] = 0;
}
int poz = 0;
trie* fiu[2];
};
const int MAXN = 1e5 + 5;
int sir[MAXN];
trie* radacina = new trie;
void adaugaNr(trie* nod, int index, int nivel)
{
if (nivel < 0)
{
nod->poz = index;
return;
}
int indexFiu = (sir[index] >> nivel) & 1;
if (nod->fiu[indexFiu] == nullptr)
{
nod->fiu[indexFiu] = new trie;
}
adaugaNr(nod->fiu[indexFiu], index, nivel - 1);
}
// gaseste secventa pentru care : (secventa de la 1 la index - 1) XOR sir[index] = maxim
int getStartIndex(trie* nod, int index, int nivel)
{
if (nivel < 0)
{
return nod->poz;
}
int indexFiu = ((sir[index] >> nivel) & 1) ^ 1; // vreau opusul bit-ului la care suntem
if (nod->fiu[indexFiu] == nullptr) // daca nu avem opusul bit-ului la care suntem, il luam pe acelasi
{
indexFiu = indexFiu ^ 1;
}
return getStartIndex(nod->fiu[indexFiu], index, nivel - 1);
}
int main()
{
int n;
fin >> n;
for (int i = 1; i <= n; i++)
{
fin >> sir[i];
sir[i] = (sir[i - 1] ^ sir[i]);
}
adaugaNr(radacina, 0, 20);
int maxSecventa = -1, maxStart = 0, maxStop = 0;
for (int i = 1; i <= n; i++)
{
int stop = i;
int start = getStartIndex(radacina, i, 20) + 1;
int secventa = sir[stop] ^ sir[start - 1];
if (secventa > maxSecventa)
{
maxSecventa = secventa;
maxStart = start;
maxStop = stop;
}
adaugaNr(radacina, i, 20);
}
fout << maxSecventa << ' ' << maxStart << ' ' << maxStop;
}