Pagini recente » Cod sursa (job #89338) | Cod sursa (job #2115213) | Cod sursa (job #862650) | Cod sursa (job #516407) | Cod sursa (job #1833485)
#include <fstream>
#include <queue>
#define lgmax 23
using namespace std;
typedef struct Nod * Arbore;
struct Nod
{
int h;
vector <int> poz;
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
poz.push_back(_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
poz.push_back(_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;
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 ((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 && i.second - i.first < b - 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->poz.size() != 0) {
for (int i(0); i < x->poz.size(); i++) {
for (int j(0); j < y->poz.size(); j++) {
if (x->poz[i] < y->poz[j])
v.push_back({ x->poz[i], y->poz[j] });
else
v.push_back({ y->poz[j], x->poz[i] });
}
}
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;
}