Pagini recente » Cod sursa (job #3154700) | Cod sursa (job #2183826) | Cod sursa (job #2148818) | Cod sursa (job #347078) | Cod sursa (job #796964)
Cod sursa(job #796964)
#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=1;
int stopMin=1;
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;
}
}
fout << finalRes <<" "<< startMin <<" "<< stopMin<<endl;
}