Pagini recente » Cod sursa (job #1460270) | Cod sursa (job #602759) | Cod sursa (job #847709) | Cod sursa (job #215694) | Cod sursa (job #3120999)
///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[NMAX];
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& curr_pos,int bit=20)
{
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(w[0]=='1' && p->sons[0]!=nullptr)
return (1<<bit)+search_opp(p->sons[0],w+1,curr_pos,bit-1);
else if(w[0]=='1')
return search_opp(p->sons[1],w+1,curr_pos,bit-1);
if(w[0]=='0' && p->sons[1]!=nullptr)
return (1<<bit)+search_opp(p->sons[1],w+1,curr_pos,bit-1);
else if(w[0]=='0')
return search_opp(p->sons[0],w+1,curr_pos,bit-1);
return 0;
}
string makeString(int n)
{
string 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());
return ans;
}
int main()
{
f>>n;
start=stop=1;
string w=makeString(partialxor[0]);
trie=add(trie,w.c_str(),0);
for(int i=1; i<=n; i++)
{
f>>x;
partialxor[i]=partialxor[i-1]^x;
int curr_index=0,curr_ans;
w=makeString(partialxor[i]);
curr_ans=search_opp(trie,w.c_str(),curr_index);
if(curr_ans>maxx)
{
maxx=curr_ans;
start=curr_index+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;
}