Pagini recente » Cod sursa (job #2944036) | Cod sursa (job #995495) | Cod sursa (job #2820680) | Cod sursa (job #1597517) | Cod sursa (job #1801482)
#include <iostream>
#include <fstream>
#define infile "xormax.in"
#define outfile "xormax.out"
using namespace std;
ifstream in(infile);
ofstream out(outfile);
struct trieNode{
trieNode* left;
trieNode* right;
int poz;
trieNode()
{
left = NULL;
right = NULL;
poz = 0;
}
};
int n, x;
int v[100005];
int nrMaxBiti, maxi;
trieNode* root = new trieNode;
int rightPos, leftPos, max_xor = -1;
void inserare(trieNode* node, int bit, int val, int ind)
{
if(bit == -1){
node->poz = ind;
return;
}
if((val>>bit) & 1){
if(node->right == NULL){
trieNode* n = new trieNode;
node->right = n;
}
inserare(node->right, bit-1, val, ind);
}else{
if(node->left == NULL){
trieNode* n = new trieNode;
node->left = n;
}
inserare(node->left, bit-1, val, ind);
}
}
int search(trieNode* node, int bit, int val)
{
if(bit == -1){
return node->poz;
}else{
/*if((val>>bit) & 1){
if(node->right != NULL){
search(node->right, bit-1, val);
}else{
search(node->left, bit-1, val);
}
}else{
if(node->left != NULL){
search(node->left, bit-1, val);
}else{
search(node->right, bit-1, val);
}
}*/
if(node->right != NULL){
search(node->right, bit-1, val);
}else{
search(node->left, bit-1, val);
}
}
}
int main()
{
in >> n;
for(int i=1; i<=n; i++){
in >> x;
v[i] = v[i-1] ^ x;
maxi = max(maxi, x);
}
for(;maxi; maxi/=2){
nrMaxBiti++;
}
inserare(root, nrMaxBiti, 0, 0);
for(int i=1; i<=n; i++){
int ind = search(root, nrMaxBiti, v[i]);
if((v[i]^v[ind]) > max_xor){
max_xor = (v[i]^v[ind]);
leftPos = ind + 1;
rightPos = i;
}
inserare(root, nrMaxBiti, v[i], i);
}
out << max_xor << ' ' << leftPos << ' ' << rightPos << '\n';
return 0;
}