Pagini recente » Cod sursa (job #1250153) | Istoria paginii runda/prbd2 | Cod sursa (job #1288869) | Cod sursa (job #1035488) | Cod sursa (job #2990558)
#include <fstream>
#include <map>
using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
const int nmax = 1e5 + 5;
const int valmax = (1 << 21);
int v[nmax], f[valmax];
struct trie
{
trie *biti[2];
};
trie *getnode()
{
trie *newnode = new trie;
newnode->biti[0] = NULL;
newnode->biti[1] = NULL;
return newnode;
};
trie *root = getnode();
int trie_search(int x)
{
trie *curr = root;
int xormaxim = 0;
for(int i = 20; i >= 0; i--){
if(x & (1 << i)){
if(curr->biti[0] != NULL){
curr = curr->biti[0];
xormaxim += (1 << i);
}
else if(curr->biti[1] != NULL)
curr = curr->biti[1];
}
else{
if(curr->biti[1] != NULL){
curr = curr->biti[1];
xormaxim += (1 << i);
}
else if(curr->biti[0] != NULL)
curr = curr->biti[0];
}
}
return xormaxim;
}
void trie_insert(int x)
{
trie *curr = root;
for(int i = 20; i >= 0; i--){
if(x & (1 << i)){
if(curr->biti[1] == NULL)
curr->biti[1] = getnode();
curr = curr->biti[1];
}
else{
if(curr->biti[0] == NULL)
curr->biti[0] = getnode();
curr = curr->biti[0];
}
}
}
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> v[i];
int maxx = v[1], curr = v[1], stanga = 1, dreapta = 1;
f[v[1]] = 1;
trie_insert(v[1]);
for(int i = 2; i <= n; i++){
curr = curr ^ v[i];
int query = trie_search(curr);
if(query > maxx){
maxx = query;
stanga = f[curr ^ query] + 1;
dreapta = i;
}
if(v[i] > maxx){
maxx = v[i];
stanga = dreapta = i;
}
trie_insert(curr);
f[curr] = i;
}
cout << maxx << " " << stanga << " " << dreapta;
return 0;
}