Pagini recente » Cod sursa (job #2877603) | Cod sursa (job #1782268) | Cod sursa (job #1061914) | Cod sursa (job #3256683) | Cod sursa (job #2747155)
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
struct trie
{
int index;
trie* fiu[2];
trie()
{
index = -1;
fiu[0] = nullptr;
fiu[1] = nullptr;
}
};
trie *T = new trie;
int n;
int v[100100];
pair<int, pair<int, int>> ans = {-1, {-1, -1}};
void ins(trie *node, int bit, int val, int i)
{
if(bit == 0)
{
//cout << "debug\n";
node -> index = i;
return;
}
int x = val & (1 << bit);
//cout << bit << ' ' << x << '\n';
if(x == 0)
{
if(node -> fiu[0] == nullptr)
{
//cout << "new\n";
node -> fiu[0] = new trie;
//cout << "new finished\n";
}
//cout << "0 going down\n";
ins(node -> fiu[0], bit - 1, val, i);
}
else
{
if(node -> fiu[1] == nullptr)
node -> fiu[1] = new trie;
//cout << "1 going down\n";
ins(node -> fiu[1], bit - 1, val, i);
}
}
int query(trie *node, int bit, int val)
{
if(bit == 0)
return node -> index;
int x = val & (1 << bit);
if(x == 0)
{
if(node -> fiu[1] == nullptr)
return query(node -> fiu[0], bit - 1, val);
return query(node -> fiu[1], bit - 1, val);
}
else
{
if(node -> fiu[0] == nullptr)
return query(node -> fiu[1], bit - 1, val);
return query(node -> fiu[0], bit - 1, val);
}
}
int main()
{
in >> n;
for(int i = 1; i <= n; i++)
{
int x;
in >> x;
v[i] = v[i - 1] ^ x;
}
//cout << "warmup\n";
ins(T, 20, 0, 0);
//cout << "START\n";
for(int i = 1; i <= n; i++)
{
int x = query(T, 20, v[i]);
if((v[x] ^ v[i]) > ans.first)
{
ans.first = (v[x] ^ v[i]);
ans.second = make_pair(x + 1, i);
}
ins(T, 20, v[i], i);
}
out << ans.first << ' ' << ans.second.first << ' ' << ans.second.second << '\n';
return 0;
}