Pagini recente » Cod sursa (job #145237) | Cod sursa (job #1595370) | Cod sursa (job #149142) | Cod sursa (job #1588216) | Cod sursa (job #2954709)
#ifdef EZ
#include "./ez/ez.h"
#else
#include <bits/stdc++.h>
#endif
#define mp make_pair
#define mt make_tuple
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const string FILE_NAME = "xormax";
ifstream fin (FILE_NAME + ".in");
ofstream fout (FILE_NAME + ".out");
const int nMAX = 100e3;
int n;
int v[nMAX + 1];
int sp[nMAX + 1];
class Trie {
public:
Trie *fii[2] = {nullptr, nullptr};
int pos = -1; // pozitia in vectorul sp
void add(Trie *nod, int i, int posbit = 20)
{
if (posbit == -1)
{
nod->pos = i;
return;
}
bool bit = (sp[i] & (1<<posbit));
if (!nod->fii[bit])
nod->fii[bit] = new Trie;
add(nod->fii[bit], i, posbit-1);
}
int getBestPos(Trie *nod, int i, int posbit = 20)
{
if (posbit == -1)
return nod->pos;
bool bit = (sp[i] & (1<<posbit));
if (nod->fii[!bit])
return getBestPos(nod->fii[!bit], i, posbit-1);
else
return getBestPos(nod->fii[bit], i, posbit-1);
}
} *root = new Trie;
int main()
{
fin >> n;
for (int i = 1; i <= n; ++i)
{
fin >> v[i];
sp[i] = (sp[i-1] ^ v[i]);
}
int max = -1, start, stop;
root->add(root, 0); // 20 e pozitia bitului maxim
for (int i = 1; i <= n; ++i)
{
int bestpos = root->getBestPos(root, i);
int val = (sp[i] ^ sp[bestpos]);
if (val > max)
{
max = val;
start = bestpos+1;
stop = i;
}
else if (val == max)
{
start = bestpos+1;
stop = i;
}
root->add(root, i);
}
fout << max << ' ' << start << ' ' << stop;
}