Pagini recente » Cod sursa (job #3259401) | Cod sursa (job #1543988) | Cod sursa (job #747221) | Cod sursa (job #2173626) | Cod sursa (job #2070781)
#include<fstream>
#include<climits>
using namespace std;
#define MAX_SIZE 21
int max(int a, int b) {
return a < b ? b : a;
}
struct Trie
{
int value = 0;
int end_index = 0;
Trie *arr[2] = { 0 };
};
bool nth_bit(int x, int n) {
return x & (1 << n);
}
void insert(Trie *root, int pre_xor, int end_index)
{
Trie *temp = root;
for (int i = MAX_SIZE - 1; i >= 0; i--)
{
bool val = nth_bit(pre_xor, i);
if (nullptr == temp->arr[val])
temp->arr[val] = new Trie;
temp = temp->arr[val];
}
temp->end_index = end_index;
temp->value = pre_xor;
}
int query(Trie *root, int pre_xor, int& end_index)
{
Trie *temp = root;
for (int i = MAX_SIZE - 1; i >= 0; i--)
{
bool val = nth_bit(pre_xor, i);
if (nullptr != temp->arr[1 - val])
temp = temp->arr[1 - val];
else {
temp = temp->arr[val];
}
}
end_index = temp->end_index;
return pre_xor ^ (temp->value);
}
int main()
{
ifstream f("xormax.in");
ofstream g("xormax.out");
Trie *root = new Trie;
int n, x;
insert(root, 0, 0);
int result = INT_MIN, pre_xor = 0;
int start_index = 1, end_index = 1;
f >> n;
for (int i = 0; i<n; i++)
{
f >> x;
pre_xor = pre_xor^x;
insert(root, pre_xor, i + 1);
int start_i, end_i;
int tmpResult = query(root, pre_xor, end_i);
if (result < tmpResult) {
start_index = end_i + 1;
end_index = i + 1;
result = tmpResult;
}
}
g << result << " " << start_index << " " << end_index << "\n";
}