Cod sursa(job #1834806)

Utilizator stanescumalinStanescu Malin Octavian stanescumalin Data 25 decembrie 2016 12:27:06
Problema Xor Max Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 kb
#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;
}