Pagini recente » Cod sursa (job #2968442) | Cod sursa (job #1381548) | Cod sursa (job #2847866) | Cod sursa (job #707972) | Cod sursa (job #3121006)
///Buzatu Giulian
#include <bits/stdc++.h>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
const int NMAX=100005;
int n,x,maxx,start,stop,partialxor,curr_pos,curr_ans;
struct Node
{
int index;///the index represents the end of the prefix
vector<Node*>sons;
Node():sons(2,nullptr) {}
~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 pos)
{
if(p==nullptr)
p=new Node;
if(w[0]=='\0')
p->index=pos;
else
p->sons[w[0]-'0']=add(p->sons[w[0]-'0'],w+1,pos);
return p;
}
int search_opp(Node* p,const char* w,int bit=20)///search opposite
{
if(w[0]=='\0')
{
curr_pos=p->index;
return 0;
}
///we want to take, when possible, the opposite bit to the one from w[0]
if(p->sons[1-(w[0]-'0')]!=nullptr)
return (1<<bit)+search_opp(p->sons[1-(w[0]-'0')],w+1,bit-1);
return search_opp(p->sons[w[0]-'0'],w+1,bit-1);
}
void makeString(string& ans,int n)
{
ans="";
if(n==0)
ans.push_back('0');
while(n>0)
{
ans.push_back((n%2)+'0');
n/=2;
}
while(ans.size()<21) /// in case the number doesn't have 20 bits in his binary representation,
ans.push_back('0');/// we want to extend it, in order to make an accurate search on the trie
reverse(ans.begin(),ans.end());
}
int main()
{
f>>n;
start=stop=1;
string w;
makeString(w,partialxor);
trie=add(trie,w.c_str(),0);
for(int i=1; i<=n; i++)
{
f>>x;
partialxor=partialxor^x;
makeString(w,partialxor);
curr_ans=search_opp(trie,w.c_str());
if(curr_ans>maxx)
{
maxx=curr_ans;
start=curr_pos+1;///because in order to calculate the xor fr [i...j] we use i-1 and that is the index returned by the function
stop=i;
}
trie=add(trie,w.c_str(),i);
}
g<<maxx<<' '<<start<<' '<<stop;
///delete trie;
return 0;
}