Pagini recente » Cod sursa (job #2479323) | Cod sursa (job #2571462) | Cod sursa (job #908476) | Cod sursa (job #3124454) | Cod sursa (job #796957)
Cod sursa(job #796957)
#include <fstream>
#include <stdlib.h>
#include <iostream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
#define LOGMAX 22
typedef struct node
{
node* zeroNode;
node* oneNode;
int minim;
int maxim;
}node;
node* alocNode()
{
node* no = (node*)malloc(sizeof(node));
no->minim = 100001;
no->maxim = -1;
no->oneNode =0;
no->zeroNode =0;
}
void putVal(node* root,int level,int val,int poz)
{
if (val&(1<<level))
{
if (!root->oneNode)
root->oneNode = alocNode();
if (level!=0)
putVal(root->oneNode , level - 1,val,poz);
}
else
{
if (!root->zeroNode)
root->zeroNode = alocNode();
if (level!=0)
putVal(root->zeroNode , level - 1,val,poz);
}
root->minim = min(root->minim,poz);
root->maxim = max(root->maxim,poz);
}
int lastSeen[100001];
int main()
{
int n;
fin >> n;
node* root = alocNode();
int xorval=0;
int xorValues[100001];
for (int i=0;i<n;i++)
{
int a;
fin >> a;
xorval^=a;
putVal(root,LOGMAX,xorval,i);
xorValues[i] = xorval;
}
int finalRes=0;
for (int i=0;i<n;i++)
{
node* iter = root;
int res=0;
for (int j=LOGMAX;j>=0;j--)
{
if (xorValues[i]&(1<<j))
{
if (iter->zeroNode)
{
iter = iter->zeroNode;
res+=1<<j;
}
else
iter = iter->oneNode;
}
else
{
if (iter->oneNode)
{
iter = iter->oneNode;
res+=1<<j;
}
else
iter = iter->zeroNode;
}
}
finalRes = max(finalRes,res);
}
//cout << finalRes;
for (int i=0;i<100001;i++)
lastSeen[i]=-1;
int startMin=0;
int stopMin=100001;
for (int i=0;i<n;i++)
{
if (lastSeen[xorValues[i]]!=-1)
{
if ((i-lastSeen[xorValues[i]])<stopMin-startMin)
{
stopMin = i;
startMin = lastSeen[xorValues[i]];
}
}
lastSeen[xorValues[i]^ finalRes] = i;
}
fout << finalRes <<" "<< startMin+2 <<" "<< stopMin+1<<endl;
}