Pagini recente » Cod sursa (job #3253204) | Cod sursa (job #3191623) | Cod sursa (job #1338973) | Cod sursa (job #181558) | Cod sursa (job #1834806)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
struct ValueSet
{
ValueSet* v0;
ValueSet* v1;
vector<int>* eps;
};
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->eps = new vector<int>(); vz1->v0 = 0; vz1->v1 = 0; }
if(vsl == 0) vz0->v0 = vz1;
if(vsl == 1) vz0->v1 = vz1;
vz0 = vz1;
}
vz1->eps->push_back(pos);
}
int maxResult(int value, int* startpos, 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; }}
}
int p0 = -1;
for(i=0;i<vz1->eps->size();i++)
{
if(vz1->eps->at(i) < *startpos) p0 = vz1->eps->at(i);
else { if(p0 == -1) p0 = vz1->eps->at(i); break;}
}
if(p0 < *startpos) { *endpos = *startpos; *startpos = p0; }
else { *endpos = p0; }
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++)
{
s = i;
r = maxResult(numbers[i], &s, &e);
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;
}