Pagini recente » Cod sursa (job #2274717) | Cod sursa (job #116042) | Cod sursa (job #2589730) | Cod sursa (job #3166121) | Cod sursa (job #3121005)
///Buzatu Giulian
#include <bits/stdc++.h>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
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;
void add(Node*& p,const char* w,int pos)
{
if(p==nullptr)
p=new Node;
if(w[0]=='\0')
p->index=pos;
else
add(p->sons[w[0]-'0'],w+1,pos);
}
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(char* ans,int n)
{
int index=20;
if(n==0)
ans[index--]='0';
while(n>0)
{
ans[index--]=(n%2)+'0';
n/=2;
}
while(index>=0) /// in case the number doesn't have 20 bits in his binary representation,
ans[index--]='0';/// we want to extend it, in order to make an accurate search on the trie
}
int main()
{
f>>n;
start=stop=1;
char w[25];
w[21]='\0';
makeString(w,partialxor);
add(trie,w,0);
for(int i=1; i<=n; i++)
{
f>>x;
partialxor^=x;
makeString(w,partialxor);
curr_ans=search_opp(trie,w);
if(curr_ans>maxx)
{
maxx=curr_ans;
start=curr_pos;///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;
}
add(trie,w,i);
}
g<<maxx<<' '<<start+1<<' '<<stop;
///delete trie;
return 0;
}