Pagini recente » Cod sursa (job #3330491) | Cod sursa (job #3327832) | Cod sursa (job #3311124) | Cod sursa (job #3306944) | Cod sursa (job #3353690)
#include <bits/stdc++.h>
using namespace std;
struct Nod
{
Nod *leg[2];
int idx;
Nod()
{
leg[0] = leg[1] = NULL;
idx = 0;
}
};
class Trie
{
public:
Nod *rad;
Trie()
{
rad = new Nod();
}
void Add(int val, int poz)
{
Nod *p = rad;
for (int i = 21; i >= 0; i--)
{
int bit = (val >> i) & 1;
if (p->leg[bit] == NULL) p->leg[bit] = new Nod();
p = p->leg[bit];
}
p->idx = poz;
}
pair<int, int> QueryMaxXor(int val)
{
Nod *p = rad;
int max_xor = 0;
for (int i = 21; i >= 0; i--)
{
int bit = (val >> i) & 1;
int bit_opus = 1 - bit;
if (p->leg[bit_opus] != NULL)
{
max_xor |= (1 << i);
p = p->leg[bit_opus];
}
else if (p->leg[bit] != NULL) p = p->leg[bit];
else break;
}
return {max_xor, p->idx};
}
};
int main()
{
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n;
fin >> n;
Trie A;
A.Add(0, 0);
int prefix_xor = 0;
int maxim = -1;
int start = -1;
int stop = -1;
for (int i = 1; i <= n; i++)
{
int x;
fin >> x;
prefix_xor ^= x;
pair<int, int> rez = A.QueryMaxXor(prefix_xor);
int p = rez.first;
int st = rez.second + 1;
if (p > maxim)
{
maxim = p;
start = st;
stop = i;
}
A.Add(prefix_xor, i);
}
fout << maxim << " " << start << " " << stop;
fin.close();
fout.close();
return 0;
}