Pagini recente » Cod sursa (job #2903240) | Cod sursa (job #56143) | Cod sursa (job #1474007) | Cod sursa (job #2612654) | Cod sursa (job #2305679)
#include <bits/stdc++.h>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
class Trie
{
private:
struct TrieNode
{
int index=0;
TrieNode *sons[2]={nullptr,nullptr};
};
TrieNode *root=new TrieNode;
public:
void _add(const deque <int> &dq,const int &idx)
{
TrieNode *current_node=root;
for(const auto &it:dq)
if(current_node->sons[it])
current_node=current_node->sons[it];
else
{
current_node->sons[it]=new TrieNode;
current_node=current_node->sons[it];
}
current_node->index=idx;
}
pair <int,int> _find(const deque <int> &dq)
{
int ans=0;
TrieNode *current_node=root;
for(const auto &it:dq)
if(current_node->sons[it^1])
{
current_node=current_node->sons[it^1];
ans=(ans<<1)+(it^1);
}
else
{
current_node=current_node->sons[it];
ans=(ans<<1)+it;
}
return make_pair(ans,current_node->index);
}
};
int main()
{
int best=-1,_begin,_end,i,n,x,xor_sum=0;
deque <int> dq;
Trie T;
for(i=1;i<=20;i++)
dq.push_back(0);
T._add(dq,0);
f>>n;
for(i=1;i<=n;i++)
{
f>>x;
xor_sum^=x;
dq.clear();
int _cpy=xor_sum;
while(_cpy)
{
dq.push_front(_cpy&1);
_cpy>>=1;
}
while(dq.size()<20)
dq.push_front(0);
pair <int,int> res=T._find(dq);
if(res.first^=xor_sum>best)
{
best=res.first^=xor_sum;
_begin=res.second+1;
_end=i;
}
T._add(dq,i);
}
g<<best<<' '<<_begin<<' '<<_end;
return 0;
}