Pagini recente » Cod sursa (job #1120985) | Cod sursa (job #1863594) | Cod sursa (job #1451525) | Cod sursa (job #3331848) | Cod sursa (job #3309833)
#include <bits/stdc++.h>
#define int long long
#define cin ci
#define cout co
using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
const int Nmax = 1e5 + 1;
const int L = 21;
int n, x, v[Nmax];
struct Node
{
int fin = -1;
Node* sons[2];
Node() { sons[0] = sons[1] = nullptr; }
};
Node* trie = nullptr;
Node* add(Node* p, const char* w, int idx)
{
if(p == nullptr)
p = new Node;
if(w[0] == '\0')
p->fin = idx;
else
p->sons[w[0] - '0'] = add(p->sons[w[0] - '0'], w + 1, idx);
return p;
}
string t_string(int x)
{
string s(L, '0');
for (int i = L - 1; i >= 0; i--)
{
s[i] = (x & 1) ? '1' : '0';
x >>= 1;
}
return s;
}
string val;
int query(Node* p, int pos)
{
if(p == nullptr)
return -1;
if(pos < (int)val.size())
{
Node* bit1 = p->sons[1];
Node* bit0 = p->sons[0];
if(val[pos] == '0')
{
if(bit1 != nullptr)
return query(bit1, pos + 1);
else
return query(bit0, pos + 1);
}
else
{
if(bit0 != nullptr)
return query(bit0, pos + 1);
else
return query(bit1, pos + 1);
}
}
else
return p->fin;
}
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> n;
v[0] = 0;
int maxi = 0;
int start = 0, finish = 0;
for(int i = 0; i < L; i++)
s.push_back('0');
trie = add(trie , s.c_str(), 0);
for(int i=1; i<=n; i++)
{
cin >> x;
v[i] = v[i - 1] ^ x;
val = t_string(v[i]);
int j = query(trie, 0);
if(j != -1 && (v[i] ^ v[j]) > maxi)
{
maxi = v[i] ^ v[j];
finish = i;
start = j + 1;
}
trie = add(trie, val.c_str(), i);
}
cout << maxi << " " << start << " " << finish;
return 0;
}