Pagini recente » Cod sursa (job #2067106) | Cod sursa (job #1172058) | Cod sursa (job #1445838) | Cod sursa (job #2541639) | Cod sursa (job #3309812)
#include <bits/stdc++.h>
#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 = 31;
int n, x, v[Nmax];
struct Node
{
int apps = 0, fin = -1;
vector<Node*> sons;
Node(): sons(2){}
~Node()
{
for(int i=0; i<2; i++)
if(this->sons[i] != nullptr)
delete this->sons[i];
}
};
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;
while(x)
{
if(x & 1)
s.push_back('1');
else
s.push_back('0');
x /= 2;
}
for(int i = s.size(); i<L; i++)
s.push_back('0');
reverse(s.begin(), s.end());
return s;
}
string val;
int query(Node* p, int pos)
{
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 ? p->fin : -1;
}
int main()
{
string s;
cin >> n;
v[0] = 0;
int maxi = -1;
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;
}