Pagini recente » Cod sursa (job #382654) | Cod sursa (job #2917232) | Cod sursa (job #609913) | Cod sursa (job #1747265) | Cod sursa (job #2969821)
#include <fstream>
#include <map>
#include <algorithm>
#include <climits>
#define ll long long
using namespace std;
const int NMAX = 1e5;
struct trie
{
int poz;
trie *vecini[2];
trie()
{
poz = -1;
for (int i = 0; i <= 1; i++)
vecini[i] = nullptr;
}
};
int i;
void adauga(trie *nod, int val, int pwr)
{
if (pwr > -1)
{
bool bit = bool(val & (1 << pwr));
if (nod->vecini[bit] == nullptr)
{
nod->vecini[bit] = new trie;
}
adauga(nod->vecini[bit], val, pwr - 1);
}
else
{
nod->poz = i;
return ;
}
}
int v[NMAX + 1];
int cauta(trie *nod, int val, int pwr)
{
if (pwr == -1)
{
return nod->poz;
}
bool bit = (val & (1 << pwr));
if (nod->vecini[!bit] != nullptr)
{
return cauta(nod->vecini[!bit], val, pwr - 1);
}
return cauta(nod->vecini[bit], val, pwr - 1);
}
int main()
{
ifstream cin("xormax.in");
ofstream cout("xormax.out");
trie *root = new trie;
int n;
cin >> n;
adauga(root, 0, 20);
int ans = 0;
int st, dr;
for (i = 1; i <= n; i++)
{
cin >> v[i];
v[i] ^= v[i - 1];
int cine = cauta(root, v[i], 20);
if (ans < (v[i] ^ v[cine]))
{
ans = (v[i] ^ v[cine]);
st = cine + 1;
dr = i;
}
adauga(root, v[i], 20);
}
cout << ans << " " << st << " " << dr;
}