Pagini recente » Cod sursa (job #139433) | Cod sursa (job #1242778) | Cod sursa (job #521138) | Cod sursa (job #175192) | Cod sursa (job #1834799)
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
struct ValueSet
{
ValueSet* v0;
ValueSet* v1;
int ep;
};
ValueSet* vset;
ValueSet* vsZ;
int vsC;
int mr, ms, me;
void InsertVList(int value, int pos)
{
int i, div = 1;
ValueSet* vz0 = vset;
ValueSet* vz1;
div = (1<<20);
for(i=0;i<20;i++)
{
int vsl = (value%div);
div /= 2;
vsl /= div;
if(vsl == 0) vz1 = vz0->v0;
if(vsl == 1) vz1 = vz0->v1;
if(vz1 == 0){ vz1 = &vsZ[vsC]; vsC++; vz1->ep = 110000; vz1->v0 = 0; vz1->v1 = 0; }
if(vsl == 0) vz0->v0 = vz1;
if(vsl == 1) vz0->v1 = vz1;
vz0 = vz1;
}
if(pos < vz1->ep) vz1->ep = pos;
}
int maxResult(int value, int* endpos)
{
int i, div = 1;
ValueSet* vz0 = vset;
ValueSet* vz1;
div = (1<<20);
int result = 0;
for(i=0;i<20;i++)
{
int vsl = (value%div);
div = div/2;
vsl /= div;
result += div;
if(vsl == 0) vz1 = vz0->v1;
if(vsl == 1) vz1 = vz0->v0;
if(vz1 == 0)
{
result -= div;
if(vsl == 0) vz1 = vz0->v0;
if(vsl == 1) vz1 = vz0->v1;
}
vz0 = vz1;
if(2*div<mr) {if(result + div < mr) { return 0; }}
}
*endpos = vz1->ep;
return result;
}
int main()
{
int n, i;
int* numbers;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
fin>>n;
numbers = new int[n];
vsZ = new ValueSet[n*24];
vsC = 0;
vset = new ValueSet();
vset->v0 = 0;
vset->v1 = 0;
fin>>numbers[0];
InsertVList(numbers[0], 0);
for(i=1; i<n; i++)
{
fin>>numbers[i];
numbers[i] = numbers[i] ^ numbers[i-1];
InsertVList(numbers[i], i);
}
mr = 0, ms = 0, me = 0;
int r, s, e;
for(i=0; i<n; i++)
{
r = maxResult(numbers[i], &e);
if(e<i) { s = e; e = i; }
else s = i;
if(r == mr)
{
if(me == e) { if(ms<s) ms = s; }
if(me > e) { me = e; ms = s; }
}
if(r > mr){ mr = r; ms = s; me = e; }
}
fout<<mr<<" "<<ms+2<<" "<<me+1<<endl;
return 0;
}