Pagini recente » Cod sursa (job #2461362) | Cod sursa (job #1871173) | Cod sursa (job #1643193) | Borderou de evaluare (job #2528305) | Cod sursa (job #1833803)
#include <fstream>
#include <queue>
#define lgmax 23
using namespace std;
typedef struct Nod * Arbore;
struct Nod
{
int h;
int poz_min = 1e9, poz_max = -1;
Arbore st = 0, dr = 0; /// st -> 0
Nod() { }
Nod(int x, int _h, int _poz)
{
h = _h;
if (h != 1) {
if ((x & 1))
dr = new Nod(x / 2, h - 1, _poz);
else
st = new Nod(x / 2, h - 1, _poz);
}
else {
if (_poz < poz_min)
poz_min = _poz;
if (_poz > poz_max)
poz_max = _poz;
}
}
void insert(int x, int _poz)
{
if (h != 1) {
if ((x & 1)) {
if (dr == 0)
dr = new Nod(x / 2, h - 1, _poz);
else
dr->insert(x / 2, _poz);
}
else {
if (st == 0)
st = new Nod(x / 2, h - 1, _poz);
else
st->insert(x / 2, _poz);
}
}
else {
if (_poz < poz_min)
poz_min = _poz;
if (_poz > poz_max)
poz_max = _poz;
}
}
};
int inv(int x);
void proc(vector <pair <int, int>> & v);
int nr[100010];
queue <pair <Arbore, Arbore>> q;
int main()
{
ifstream in("xormax.in");
int n;
in >> n;
Arbore k = new Nod;
k->h = lgmax + 1;
k->insert(0, 0);
for (int i(1); i <= n; i++) {
in >> nr[i];
nr[i] ^= nr[i - 1];
k->insert(inv(nr[i]), i);
}
q.push({ k, k });
vector <pair <int, int>> v;
proc(v);
int a, b, best(0);
for (auto & i : v) {
if (i.first > i.second)
swap(i.first, i.second);
}
for (auto i : v) {
if ((nr[i.first] ^ nr[i.second]) > best)
best = (nr[i.first] ^ nr[i.second]), a = i.first, b = i.second;
else if ((nr[i.first] ^ nr[i.second]) == best) {
if (i.second < b)
a = i.first, b = i.second;
else if (i.second == b && i.first > a)
a = i.first, b = i.second;
}
}
ofstream out("xormax.out");
out << best << ' ' << a + 1 << ' ' << b;
return 0;
}
void proc(vector <pair <int, int>> & v)
{
while (!q.empty()) {
Arbore x(q.front().first), y(q.front().second);
q.pop();
if (x->h == 1) {
if (x->poz_min != 1e9) {
if (y->poz_min != 1e9)
v.push_back({ x->poz_min, y->poz_min });
if (y->poz_max != -1)
v.push_back({ x->poz_min, y->poz_max });
}
if (x->poz_max != -1) {
if (y->poz_min != 1e9)
v.push_back({ x->poz_max, y->poz_min });
if (y->poz_max != -1)
v.push_back({ x->poz_max, y->poz_max });
}
continue;
}
if (x->st && x->dr && y->st && y->dr) {
q.push({ x->st, y->dr });
q.push({ x->dr, y->st });
}
else {
if (x->st && !x->dr) {
if (y->dr)
q.push({ x->st, y->dr });
else
q.push({ x->st, y->st });
}
else if (x->dr && !x->st) {
if (y->st)
q.push({ x->dr, y->st });
else
q.push({ x->dr, y->dr });
}
else {
if (y->st)
q.push({ x->dr, y->st });
else
q.push({ x->st, y->dr });
}
}
}
}
int inv(int x)
{
int r(0);
for (int i(0); i < lgmax; i++) {
r <<= 1;
r |= (x & 1);
x >>= 1;
}
return r;
}