Pagini recente » Cod sursa (job #2068945) | Cod sursa (job #1508056) | Cod sursa (job #1682994) | Cod sursa (job #1168919) | Cod sursa (job #1716189)
/********************
Created by Sburly
********************/
#include <fstream>
using namespace std;
#define long_size 31
struct pos{
long int val = -1;
long int p;
};
struct trie{
trie* nx[2] = {NULL, NULL};
pos v;
};
void ins(trie* root, long int val, long int i)
{
int bit;
trie* temp = root;
for(int i = long_size; i >= 0; i--)
{
bit = (val >> i) & 1;
if((*temp).nx[bit] == NULL)
{
trie *t = new trie;
(*temp).nx[bit] = t;
temp = t;
}
else
{
temp = (*temp).nx[bit];
}
}
(*temp).v.val = val;
(*temp).v.p = i;
}
trie* xmx(trie *root, long int a)
{
int bit;
trie* temp = root;
for(int i = long_size; i >= 0; i--)
{
bit = (a >> i) & 1;
if((*temp).nx[1-bit] != NULL)
{
temp = (*temp).nx[1-bit];
}
else
if((*temp).nx[bit] != NULL)
{
temp = (*temp).nx[bit];
}
}
return temp;
}
int main()
{
ifstream f("xormax.in");
ofstream g("xormax.out");
long int n;
long int start = 1;
long int stop = 1;
f >> n;
long int sol = 0;
long int prex = 0;
trie *root = new trie;
ins(root,0,0);
for(long int i = 1; i <= n; i++)
{
long int x;
f >> x;
prex ^= x;
ins(root, prex,i);
trie* temp = xmx(root, prex);
long int vl = (*temp).v.val ^ prex;
if(vl > sol)
{
sol = vl;
start = (*temp).v.p+1;
stop = i;
}
else
if(vl == sol)
{
if(i-(*temp).v.p+1 < stop-start)
{
start = (*temp).v.p+1;
stop = i;
}
}
}
g << sol << ' ' << start << ' ' << stop;
return 0;
}