Pagini recente » Cod sursa (job #917456) | Cod sursa (job #3128030) | Cod sursa (job #3258135) | Cod sursa (job #1816074) | Cod sursa (job #1072188)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct Trie
{
Trie *son[2];
int p;
Trie()
{
memset(son, 0, sizeof(son));
}
};
Trie *T = new Trie;
int N, A, R = -1, S, F, Y;
int bits[24];
void take_bits(int A)
{
bits[0] = 0;
if (A == 0)
{
for (int i = 1; i <= 22; ++i)
bits[++bits[0]] = 0;
return ;
}
while (A)
{
bits[++bits[0]] = A % 2;
A = A / 2;
}
while (bits[0] < 22)
bits[++bits[0]] = 0;
reverse(bits + 1, bits + bits[0] + 1);
}
inline void insert(Trie *T, const int &i)
{
if (i > bits[0])
{
T->p = Y;
return ;
}
if (T->son[bits[i]] == 0)
T->son[bits[i]] = new Trie;
insert(T->son[bits[i]], i + 1);
}
inline int get_max(Trie *T, const int &i)
{
if (i > bits[0])
{
Y = T->p;
return 0;
}
if (T->son[!bits[i]])
return get_max(T->son[!bits[i]], i + 1) + (1 << (bits[0] - i));
if (T->son[bits[i]])
return get_max(T->son[bits[i]], i + 1);
return 0;
}
int main()
{
fin >> N;
insert(T, 1);
for (int i = 1; i <= N; ++i)
{
int X;
fin >> X;
A = A ^ X;
take_bits(A);
int V = get_max(T, 1);
if (R < V || (R == V && F - S > i - Y))
{
R = V;
S = Y;
F = i;
}
Y = i;
insert(T, 1);
}
fout << R << ' ' << S + 1 << ' ' << F << '\n';
fin.close();
fout.close();
}