Cod sursa(job #1834788)

Utilizator stanescumalinStanescu Malin Octavian stanescumalin Data 25 decembrie 2016 08:58:33
Problema Xor Max Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <iostream>
#include <fstream>

using namespace std;

struct ValueSet
{
    ValueSet* v0;
    ValueSet* v1;
    int ep;
};

ValueSet* vset;

void InsertVList(int value, int pos)
{
    int i, div = 1;
    ValueSet* vz0 = vset;
    ValueSet* vz1;
    for(i=0;i<20;i++) div *= 2;
    for(i=0;i<20;i++)
    {
        int vsl = (value%div) / (div/2);
        div /= 2;
        if(vsl == 0) vz1 = vz0->v0;
        if(vsl == 1) vz1 = vz0->v1;
        if(vz1 == 0){ vz1 = new ValueSet(); vz1->ep = 110000; }
        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;
    for(i=0;i<20;i++) div *= 2;
    int result = 0;
    for(i=0;i<20;i++)
    {
        int vsl = (value%div) / (div/2);
        div = div/2;
        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;
    }
    *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];
    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);
    }


    int mr, ms, me;
    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;
}