Pagini recente » Cod sursa (job #1547318) | Cod sursa (job #2405107) | Cod sursa (job #1615915) | Cod sursa (job #61021) | Cod sursa (job #2589180)
#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
int n, sum;
int v[100010];
struct trie
{
int poz;
trie *next[2];
trie()
{
poz = 0;
next[0] = nullptr;
next[1] = nullptr;
}
};
trie *T = new trie;
void ins(trie *node, int bit, int val, int i)
{
if(bit == 0)
{
node -> poz = i;
return;
}
bool x = val & (1 << bit);
if(x == false)
{
if(node -> next[0] == nullptr)
node -> next[0] = new trie;
ins(node -> next[0], bit - 1, val, i);
}
else
{
if(node -> next[1] == nullptr)
node -> next[1] = new trie;
ins(node -> next[1], bit - 1, val, i);
}
}
int query(trie *node, int bit, int val)
{
if(bit == 0)
{
//cout << val << ' ' << node -> poz << '\n';
return node -> poz;
//cout << '\n';
}
bool x = val & (1 << bit);
//cout << x << ' ';
if(x == 0)
{
if(node -> next[1] != nullptr)
return query(node -> next[1], bit - 1, val);
else
return query(node -> next[0], bit - 1, val);
}
else
{
if (node -> next[0] != nullptr)
return query(node -> next[0], bit - 1, val);
else
return query(node -> next[1], bit - 1, val);
}
}
int main()
{
in >> n;
for(int i = 1; i <= n; i++)
{
int x;
in >> x;
v[i] = x ^ v[i-1];
}
pair<int, pair<int, int>> rez;
rez.first = -1;
ins(T, 21, 0, 0);
for(int i = 1; i <= n; i++)
{
int aux = query(T, 21, v[i]);
//cout << i << ' ' << aux << ' ' << v[i] << ' ' << (aux ^ v[i]) << "\n";
if((v[i] ^ v[aux]) > rez.first)
{
rez.first = v[i] ^ v[aux];
rez.second.first = aux;
rez.second.second = i;
}
//cout << rez.first << "\n\n\n";
ins(T, 21, v[i], i);
}
out << rez.first << ' ' << rez.second.first + 1 << ' ' << rez.second.second << '\n';
return 0;
}