Cod sursa(job #1714428)

Utilizator SburlyAndrei Florin Sburly Data 8 iunie 2016 10:31:20
Problema Xor Max Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
/********************
    Created by Sburly
********************/
#include <fstream>
#include <iostream>

using namespace std;

#define _min -2147483647

struct ab{
    long int val = -1;
    long int length = 0;
};

ab ks(int i);

long int n;
long int a[100000];

ab b[100000];
int k = 0;

int main()
{
    ifstream f("xormax.in");
    ofstream g("xormax.out");

    f >> n;

    long int mx = _min;
    long int mxi = _min;
    long int mn = 0-_min;


    long int start, stop;

    for(long int i = 0; i < n; i++)
    {
        f >> a[i];

        if(a[i] > mxi)
        {
            mxi = a[i];
            k = 0;
            long int temp = mxi;
            while(temp!=0)
            {
                temp/=2;
                k++;
            }
            k=1<<k;
        }
        a[i] = a[i]%k;

        ab x = ks(i);
        long int temp = x.val;
        //cout << i << ' ' << temp << ' ' << x.length << endl;

        if(temp == mx)
        {
            if(x.length < mn)
            {
                mn = x.length;
                mx = temp;
                stop = i+1;
                start = stop-x.length+1;
            }
        }
        else
        if(temp > mx)
        {
            mx = temp;
            mn = x.length;
            stop = i+1;
            start = stop-x.length+1;
        }
    }

    g << mx << ' ' << start << ' ' << stop;

    return 0;
}

ab ks(int i)
{
    if(i == 0)
    {
        if(b[i].val == -1)
        {
            b[i].val = a[i];
            b[i].length = 1;
        }
        return b[i];
    }
    else
    {
        if(b[i].val == -1)
        {
            if(a[i] >= (b[i-1].val + a[i])%k)
            {
                b[i].val = a[i];
                b[i].length = 1;
            }
            else
            {
                b[i].val = (b[i-1].val + a[i])%k;
                b[i].length = b[i-1].length + 1;
            }
        }
        return b[i];
    }
}