Pagini recente » Cod sursa (job #2396021) | Cod sursa (job #1836409) | Cod sursa (job #1921808) | Cod sursa (job #2212446) | Cod sursa (job #2972207)
#include <fstream>
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
int partial[100005];
class TrieNode
{
private:
int idx;
TrieNode *edges[2];
public:
TrieNode()
{
idx=-1;
for(int i=0;i<2;i++)
{
edges[i]=nullptr;
}
}
void insert1(int val,int inidx,int poz)
{
if(poz==-1)
{
idx=inidx;
return;
}
int bit=((val>>poz)&1);
if(edges[bit]==nullptr)
{
edges[bit]=new TrieNode();
}
edges[bit]->insert1(val,inidx,poz-1);
}
int find_best_opposite(int val,int poz=21)
{
if(poz==-1)
return idx;
int bit=((val>>poz)&1);
if (edges[!bit]!=nullptr)
{
return edges[!bit]->find_best_opposite(val,poz-1);
}
return edges[bit]->find_best_opposite(val,poz-1);
}
};
int main()
{
int n;
in>>n;
for (int i=1;i<=n;i++)
{
int val;
in>>val;
partial[i]=partial[i-1]^val;
}
TrieNode root=TrieNode();
root.insert1(partial[1],1,21);
if(n==1)
{
out<<partial[1]<<' '<<1<<' '<<1<<'\n';
return 0;
}
int maxi=-1;
int stans,drans;
for (int i=2;i<=n;i++)
{
int st=root.find_best_opposite(partial[i]);
int possibleans=partial[st]^partial[i];
if (partial[i]>possibleans && partial[i]>maxi)
{
possibleans=partial[i];
stans=1;
drans=i;
}
else if(possibleans>maxi)
{
maxi=possibleans;
stans=st+1;
drans=i;
}
root.insert1(partial[i],i,21);
}
out<<maxi<<' '<<stans<<' '<<drans<<'\n';
return 0;
}