Cod sursa(job #528851)
#include <cstring>
#include <fstream>
using namespace std;
struct Trie
{
Trie* son[2];
int who;
Trie()
{
who = 0;
memset(son, 0, sizeof(son));
}
};
Trie* T = new Trie;
int infor;
void Tinsert(Trie* now, int number, int K)
{
if (K == -1)
{
now->who = infor;
return;
}
int aux = ((number & (1 << K)) != 0 ? 1 : 0);
if (now->son[aux] == 0)
{
Trie* noda = new Trie;
now->son[aux] = noda;
}
Tinsert(now->son[aux], number, K - 1);
}
int N, V[100002];
int result = -1, beg, end;
int main()
{
ifstream fin("xormax.in");
ofstream fout("xormax.out");
fin >> N;
for (int i = 1; i <= N; ++i)
{
fin >> V[i];
V[i] ^= V[i - 1];
}
Tinsert(T, 0, 21);
for (int i = 1; i <= N; ++i)
{
Trie* now = T;
int resnow = 0;
for (int j = 21; j >= 0; --j)
{
int aux = !(((V[i] & (1 << j)) != 0 ? 1 : 0));
if (now->son[aux] != 0)
{
resnow |= (1 << j);
now = now->son[aux];
}
else now = now->son[!aux];
}
if (resnow > result)
{
result = resnow;
beg = now->who + 1;
end = i;
}
++infor;
Tinsert(T, V[i], 21);
}
fout << result << ' ' << beg << ' ' << end;
fin.close();
fout.close();
}