Pagini recente » Cod sursa (job #2133177) | Cod sursa (job #2157542) | Cod sursa (job #375694) | Cod sursa (job #660346) | Cod sursa (job #796963)
Cod sursa(job #796963)
#include <fstream>
#include <stdlib.h>
#include <iostream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
#define LOGMAX 21
typedef struct node
{
node* zeroNode;
node* oneNode;
int lastpoz;
}node;
node* alocNode()
{
node* no = (node*)malloc(sizeof(node));
no->lastpoz = 100001;
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();
root->oneNode->lastpoz = poz;
if (level!=0)
putVal(root->oneNode , level - 1,val,poz);
}
else
{
if (!root->zeroNode)
root->zeroNode = alocNode();
root->zeroNode->lastpoz = poz;
if (level!=0)
putVal(root->zeroNode , level - 1,val,poz);
}
root->lastpoz = poz;
}
int lastSeen[3000001];
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;
int startMin=0;
int stopMin=100001;
for (int i=0;i<n;i++)
{
int a;
fin >> a;
xorval^=a;
putVal(root,LOGMAX,xorval,i);
xorValues[i] = xorval;
node* iter = root;
int res=0;
int pos=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;
}
}
pos = iter->lastpoz;
if (finalRes< res)
{
finalRes = res;
startMin = pos+2;
stopMin = i+1;
}
if (finalRes< xorValues[i])
{
finalRes=xorValues[i];
startMin = 1;
stopMin = i+1;
}
//finalRes = max(finalRes,res);
}
//for (int i=0;i<n;i++)
//finalRes = max(finalRes , xorValues[i]);
//cout << finalRes;
/*
for (int i=0;i<3000001;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 <<" "<< stopMin<<endl;
}