Pagini recente » Cod sursa (job #1235539) | Cod sursa (job #2191164) | Cod sursa (job #44820) | Cod sursa (job #210858) | Cod sursa (job #2224633)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int xormax=0,xorstart=0,xorend=0,nrBits=0;
int bits[100];
int n,a[100002];
void countBits(int xmax)
{
while(xmax>0)
{
xmax/=2;
nrBits++;
}
}
struct node
{
int ending;
node* edge[2]={};
}* root=new node;
void toBinary(int x)
{
for(int i=0;i<nrBits;i++)
{
bits[i]=x%2;
x/=2;
}
}
void addTrie(int j)
{
node* crawl=root;
for(int i=nrBits-1;i>=0;i--)
{
// cout<<crawl->edge[bits[i]]<<" ";
if(crawl->edge[bits[i]]==NULL)
{
node* element=new node;
crawl->edge[bits[i]]=element;
}
crawl=crawl->edge[bits[i]];
}
crawl->ending=j;
}
void findMax(int j)
{
node* crawl=root;
for(int i=nrBits-1;i>=0;i--)
{
if(bits[i]==0&&crawl->edge[1]!=NULL)
crawl=crawl->edge[1];
else if(bits[i]==1&&crawl->edge[0]!=NULL)
crawl=crawl->edge[0];
else crawl=crawl->edge[bits[i]];
}
if(a[crawl->ending]^a[j]>xormax)
{
xormax=a[crawl->ending]^a[j];
xorstart=crawl->ending+2;
xorend=j+1;
}
}
int main()
{
int xsum=0,xmax=0;
fin>>n;
for(int i=0;i<n;i++)
{
int tmp;
fin>>tmp;
xsum^=tmp;
xmax=max(xsum,xmax);
a[i]=xsum;
}
countBits(xmax);
toBinary(a[0]);
// for(int i=nrBits-1;i>=0;i--)
// cout<<bits[i]<<" ";
addTrie(0);
if(a[0]>xormax)
{
xormax=a[0];
xorstart=1;
xorend=1;
}
for(int i=1;i<n;i++)
{
toBinary(a[i]);
findMax(i);
addTrie(i);
}
fout<<xormax<<" "<<xorstart<<" "<<xorend;
return 0;
}