Pagini recente » Cod sursa (job #320604) | Cod sursa (job #2920704) | Cod sursa (job #522131) | Cod sursa (job #3172007) | Cod sursa (job #796959)
Cod sursa(job #796959)
#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[5000001];
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);
}
for (int i=0;i<n;i++)
finalRes = max(finalRes , xorValues[i]);
//cout << finalRes;
for (int i=0;i<5000001;i++)
lastSeen[i]=-2;
lastSeen[0]=-1;
int startMin=0;
int stopMin=100001;
for (int i=0;i<n;i++)
{
if (lastSeen[xorValues[i]^finalRes]!=-2)
{
if ((i-lastSeen[xorValues[i]^finalRes])<stopMin-startMin)
{
stopMin = i;
startMin = lastSeen[xorValues[i]^finalRes];
}
}
lastSeen[xorValues[i]] = i;
}
fout << finalRes <<" "<< startMin+2 <<" "<< stopMin+1<<endl;
}