Pagini recente » Cod sursa (job #1518902) | Cod sursa (job #2033965) | Cod sursa (job #2709684) | Cod sursa (job #1229729) | Cod sursa (job #2531182)
#include <fstream>
using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
const int N = (int) 1e5 + 7;
int n;
int pref[N];
int sol = 0;
int id1;
int id2;
struct trie
{
trie *kid[2];
trie()
{
kid[0] = kid[1] = 0;
}
};
trie *root = new trie;
void ins(int x)
{
trie *cur = root;
for (int bit = 21; bit >= 0; bit--)
{
int go;
if (x & (1 << bit))
{
go = 1;
}
else
{
go = 0;
}
if (!cur->kid[go])
{
cur->kid[go] = new trie;
}
cur = cur->kid[go];
}
}
int get(int val)
{
int sol = 0;
trie *cur = root;
for (int bit = 21; bit >= 0; bit--)
{
if (!cur->kid[0] && !cur->kid[1])
{
break;
}
int go;
if (val & (1 << bit))
{
go = 0;
}
else
{
go = 1;
}
if (cur->kid[go])
{
sol += (1 << bit);
cur = cur->kid[go];
}
else
{
cur = cur->kid[1 ^ go];
}
}
return sol;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
pref[i] = pref[i - 1] ^ x;
int now = get(pref[i]);
if (now > sol)
{
sol = now;
id2 = i;
}
ins(pref[i]);
}
id1 = id2;
while (pref[id1 - 1] != (sol ^ pref[id2]))
{
id1--;
}
cout << sol << " " << id1 << " " << id2 << "\n";
}