Pagini recente » Cod sursa (job #1319175) | Cod sursa (job #1896343) | Cod sursa (job #1095185) | Cod sursa (job #1288288) | Cod sursa (job #3309759)
#include <bits/stdc++.h>
#define cin ci
#define cout co
using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
const int L = 31;
const int Nmax = 1e5 + 1;
int n, st, dr, x, v[Nmax];
struct Node
{
int fin = -1;
vector<Node*> sons;
Node(): sons(2, nullptr) {}
~Node() {
for (auto child : sons)
if (child) delete child;
}
};
Node* add(Node* p, const char* w, int idx)
{
if (p == nullptr) p = new Node;
if (w[0] == '\0')
p->fin = idx;
else
{
int bit = w[0] - '0';
p->sons[bit] = add(p->sons[bit], w + 1, idx);
}
return p;
}
string s;
int query(Node* p, int pos)
{
if (pos < (int)s.size() && p != nullptr)
{
Node* bit1 = p->sons[1];
Node* bit0 = p->sons[0];
if (s[pos] == '0')
{
if (bit1)
return query(bit1, pos + 1);
else
return query(bit0, pos + 1);
}
else
{
if (bit0)
return query(bit0, pos + 1);
else
return query(bit1, pos + 1);
}
}
return p ? p->fin : 0;
}
static inline string make_key_from_number(int val)
{
string p;
for (int j = 0; j < L; j++)
p.push_back((val & (1 << (L - 1 - j))) ? '1' : '0');
return p;
}
int main()
{
cin >> n;
v[0] = 0;
int maxi = -1;
int start = 0, stop = 0;
Node* trie = nullptr;
s = make_key_from_number(0);
trie = add(trie, s.c_str(), 0);
for (int i = 1; i <= n; i++)
{
cin >> x;
v[i] = v[i - 1] ^ x;
s = make_key_from_number(v[i]);
int j = query(trie, 0);
if ((v[i] ^ v[j]) > maxi)
{
maxi = v[i] ^ v[j];
start = j;
stop = i;
}
trie = add(trie, s.c_str(), i);
}
cout << maxi << " " << start + 1 << " " << stop;
return 0;
}