Pagini recente » Cod sursa (job #2054322) | Cod sursa (job #1324781) | Cod sursa (job #1247423) | Cod sursa (job #2957928) | Cod sursa (job #3144732)
#include <fstream>
using namespace std;
ifstream cin ("xormax.in");
ofstream cout ("xormax.out");
class Trie {
private:
int indice = -1; Trie *urmatorul[2] = {};
public:
void insert (const int valoare , const int _indice , const int bit) {
if (bit == -1) { indice = _indice; return; }
switch (valoare >> bit & 1)
{
case 0:
{
if (!urmatorul[0]) urmatorul[0] = new Trie;
urmatorul[0] -> insert(valoare , _indice , bit - 1);
}
break;
case 1:
{
if (!urmatorul[1]) urmatorul[1] = new Trie;
urmatorul[1] -> insert(valoare , _indice , bit - 1);
}
break;
}
}
pair <int , int> find (const int valoare , const int bit) {
if (bit == -1) return make_pair(0 , indice);
if (valoare >> bit & 1)
{
pair <int , int> rezultat = (urmatorul[0] ? urmatorul[0] -> find(valoare , bit - 1) : urmatorul[1] -> find(valoare , bit - 1));
if (urmatorul[0]) rezultat.first |= (1 << bit);
return rezultat;
}
pair <int , int> rezultat = (urmatorul[1] ? urmatorul[1] -> find(valoare , bit - 1) : urmatorul[0] -> find(valoare , bit - 1));
if (urmatorul[1]) rezultat.first |= (1 << bit);
return rezultat;
}
} aparitii;
int main ()
{
int lungime;
cin >> lungime;
aparitii.insert(0 , 0 , 20);
int valoare_maxima = 0 , inceput = 0 , sfarsit = 0;
for (int indice = 1 , valoare , valoare_actuala = 0 ; indice <= lungime ; indice++)
{
cin >> valoare;
valoare_actuala ^= valoare;
pair <int , int> valoare_gasita = aparitii.find(valoare_actuala , 20);
if (valoare_gasita.first > valoare_maxima || (valoare_gasita.first == valoare_maxima && indice - valoare_gasita.second < sfarsit - inceput + 1))
{ valoare_maxima = valoare_gasita.first; inceput = valoare_gasita.second + 1; sfarsit = indice; }
aparitii.insert(valoare_actuala , indice , 20);
}
cout << valoare_maxima << ' ' << inceput << ' ' << sfarsit;
cout.close(); cin.close();
return 0;
}