Cod sursa(job #2566617)

Utilizator LazarRazvanLazar Razvan LazarRazvan Data 2 martie 2020 22:23:46
Problema Secventa Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <iostream>
#include <fstream>
#include <queue>

#define INF 999999
#define MINF -999999

using namespace std;

typedef struct sequence
{
    int n = 0;
    deque < int > numbers;
    int base = INF;
}seq;

typedef struct result
{
    int start = 0;
    int finish = 0;
    int base = MINF;
}res;

ifstream fin;
ofstream fout;

int n, k;

seq readFirstSequence()
{
    seq sequence;

    sequence.n = k;

    for (int i = 1; i <= k; i++)
    {
        int nr;
        fin >> nr;

        sequence.numbers.push_back(nr);

        if (nr < sequence.base)
            sequence.base = nr;
    }

    return sequence;
}

void insertNrInSeq(int number, seq &seq)
{
    seq.numbers.push_back(number);

    if (number < seq.base)
        seq.base = number;
}

void writeSeq(seq seq)
{
    while(seq.n > 0)
    {
        seq.n--;
        cout << seq.numbers.front() << " ";
        seq.numbers.pop_front();
    }

    cout << '\n';
}

int findBase(seq seq)
{
    int base = INF;

    while(seq.n > 0)
    {
        seq.n--;

        if (seq.numbers.front() < base)
            base = seq.numbers.front();

        seq.numbers.pop_front();
    }

    return base;
}

void updateResult(res &res, seq seq, int start, int finish)
{
    if (seq.base > res.base)
    {
        res.base = seq.base;
        res.start = start;
        res.finish = finish;
    }
}


int main() {

    fin.open("secventa.in");
    fout.open("secventa.out");

    fin >> n >> k;

    seq seq = readFirstSequence();
    res res;

    //writeSeq(seq);

    for (int i = k+1; i <= n; i++)
    {
        int number;
        fin >> number;

        seq.numbers.push_back(number);

        if (number <= seq.base) {

            seq.base = number;
            seq.numbers.pop_front();


        } else {
            if (seq.base == seq.numbers.front()) {
                seq.numbers.pop_front();
                seq.base = findBase(seq);
            } else
                seq.numbers.pop_front();

        }


        //writeSeq(seq);

        updateResult(res, seq, i-k+1, i);
        //cout << seq.base << '\n';

    }

    fout << res.start << " " << res.finish << " " << res.base;

    fin.close();
    fout.close();

    return 0;
}