Pagini recente » Cod sursa (job #1701593) | Cod sursa (job #225451) | Cod sursa (job #208665) | Cod sursa (job #901922) | Cod sursa (job #3164199)
#include <fstream>
using namespace std;
ifstream cin ("xormax.in");
ofstream cout ("xormax.out");
class Trie {
private:
int indice = 0;
Trie *urmatorul[2] = { };
public:
void insert (const int valoare , const int _indice , const int bit = 20)
{
if (bit == -1)
{ indice = _indice; }
else
{
if (valoare & (1 << bit))
{
if (!urmatorul[1]) { urmatorul[1] = new Trie; }
urmatorul[1] -> insert(valoare , _indice , bit - 1);
}
else
{
if (!urmatorul[0]) { urmatorul[0] = new Trie; }
urmatorul[0] -> insert(valoare , _indice , bit - 1);
}
}
}
pair <int , int> find (const int valoare , const int bit = 20)
{
if (bit == -1)
{ return {0 , indice}; }
if (((valoare & (1 << bit)) && urmatorul[0]) || !urmatorul[1])
{ return urmatorul[0] -> find(valoare , bit - 1); }
if ((!(valoare & (1 << bit)) && urmatorul[1]) || !urmatorul[0])
{
pair <int , int> rezultat = urmatorul[1] -> find(valoare , bit - 1);
rezultat.first |= (1 << bit);
return rezultat;
}
pair <int , int> optiune_1 = urmatorul[0] -> find(valoare , bit - 1);
pair <int , int> optiune_2 = urmatorul[1] -> find(valoare , bit - 1);
optiune_2.first |= (1 << bit);
if ((valoare ^ optiune_1.first) > (valoare ^ optiune_2.first))
{ return optiune_1; }
return optiune_2;
}
} optiuni;
int main ()
{
int lungime;
cin >> lungime;
optiuni.insert(0 , 0);
int maxim = -1 , inceput = 1 , sfarsit = 0;
for (int dreapta = 1 , suma = 0 , valoare ; dreapta <= lungime ; dreapta++)
{
cin >> valoare;
suma ^= valoare;
pair <int , int> stanga = optiuni.find(suma);
if ((stanga.first ^ suma) > maxim)
{ maxim = (stanga.first ^ suma); inceput = stanga.second + 1; sfarsit = dreapta; }
optiuni.insert(suma , dreapta);
}
cout << maxim << ' ' << inceput << ' ' << sfarsit;
cout.close(); cin.close();
return 0;
}