Pagini recente » Cod sursa (job #937328) | Cod sursa (job #1200176) | Cod sursa (job #107361) | Cod sursa (job #2680761) | Cod sursa (job #3353177)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_BITS = 20;
const int MAX_NODES = 2500005;
int trie[MAX_NODES][2];
int leaf_index[MAX_NODES];
int nodes_count = 0;
void insert(int value, int original_index)
{
int node = 0;
for(int i = MAX_BITS;i>=0;i--)
{
int bit = (value >> i) & 1;
if(trie[node][bit]==0)
{
trie[node][bit] = ++nodes_count;
}
node = trie[node][bit];
}
leaf_index[node] = original_index;
}
int query(int value)
{
int node = 0;
for(int i = MAX_BITS;i>=0;i--)
{
int bit = (value>>i) & 1;
int opposite_bit = 1 - bit;
if(trie[node][opposite_bit] != 0)
{
node = trie[node][opposite_bit];
}
else
{
node = trie[node][bit];
}
}
return leaf_index[node];
}
int P[100005];
int main()
{
ifstream cin("xormax.in");
ofstream cout("xormax.out");
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
int max_xor = -1;
int best_start = 0, best_stop = 0;
int curent_prefix_xor = 0;
insert(0,0);
P[0] = 0;
for(int i{1};i<=n;i++)
{
int val;
cin>>val;
P[i] = P[i - 1] ^ val;
int best_k = query(P[i]);
int candidate_xor = P[i] ^ P[best_k];
if(candidate_xor>max_xor)
{
max_xor = candidate_xor;
best_start = best_k + 1;
best_stop = i;
}
insert(P[i], i);
}
cout<<max_xor<< " "<<best_start<< ' '<<best_stop;
return 0;
}
/*
Solution:
We put the partial sums XOR in binary form in a Trie.
We choose the best number by comparing the bits and choosing
the one with the inversed bits.
*/