Pagini recente » Cod sursa (job #1011207) | Cod sursa (job #1445742) | Cod sursa (job #388605) | Cod sursa (job #1107368) | Cod sursa (job #2533119)
#include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n,i,x,nrbit,s[100005];
struct trie{
int poz;
trie *f[3];
trie()
{
poz = 0;
f[0] = f[1] = 0;
}
};
trie *root = new trie;
void adauga(trie *r, int val, int bit, int pozitie)
{
if (bit < 0)
r->poz = pozitie;
else
{
int fiu = ((val>>bit)&1);
if (r->f[fiu] == NULL)
r->f[fiu] = new trie();
adauga(r->f[fiu], val, bit-1, pozitie);
}
}
int query(trie *r, int val, int bit)
{
if (bit < 0)
return r->poz;
else
{
int fiu = ((val>>bit)&1);
if (r->f[1-fiu] == NULL)
query(r->f[fiu], val, bit-1);
else
query(r->f[1-fiu], val, bit-1);
}
}
int main()
{
fin >> n; int maxim = 0;
for (i=1; i<=n; i++)
{
fin >> x;
s[i] = (s[i-1]^x);
maxim = max(maxim, s[i]);
}
while (maxim > 0)
{
nrbit++;
maxim /= 2;
}
adauga(root, 0, nrbit, 0); maxim = 0; int st = 0; int dr = 0;
for (i=1; i<=n; i++)
{
int bestpoz = query(root, s[i], nrbit);
if ((s[bestpoz]^s[i]) > maxim)
{
maxim = (s[bestpoz]^s[i]);
st = bestpoz+1; dr = i;
}
adauga(root, s[i], nrbit, i);
}
fout << maxim << " " << st << " " << dr;
return 0;
}