Cod sursa(job #2312379)

Utilizator stanescumalinStanescu Malin Octavian stanescumalin Data 4 ianuarie 2019 19:25:07
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <iostream>
#include <fstream>

using namespace std;

int n, k;

int binsearch(int* vec, int start, int end, int value)
{
    int medp;
    if(start > end) { medp = ((start+end+k)/2)%k; }
    else medp = (start+end)/2;

    if(value == vec[medp]) return medp;
    if(end-start < 2)
    {
        if(value < vec[medp]) return medp;
        else return medp+1;
    }
    if(value < vec[medp]) return binsearch(vec, start, medp, value);
    else return binsearch(vec, medp, end, value);
}

int main()
{
    ifstream fin("secventa.in");

    int qpos = 0;
    fin>>n>>k;
    int* datavec = new int[n];
    int* queue = new int[k];
    int* bpos = new int[k];
    int ringstart = 0;
    queue[qpos] = 50000;
    int maxbasis = -50000;
    int maxbasispost = -1;
    fin>>datavec[0];
    queue[qpos] = datavec[0];
    bpos[qpos] = 0;
    qpos++;
    for(int i=1;i<k;i++)
    {
        fin>>datavec[i];
        int pos;
        if(datavec[i]<queue[qpos])
            pos = binsearch(queue, 0, qpos, datavec[i]);
        else pos = qpos;
        qpos = pos;
        queue[qpos] = datavec[i];
        bpos[qpos] = i;
        qpos++;
    }

    for(int i=k;i<n;i++)
    {
        fin>>datavec[i];
        int pos;
        if(datavec[i]<queue[qpos-1])
            pos = binsearch(queue, ringstart%k, qpos, datavec[i]);
        else pos = qpos;
        qpos = pos;
        queue[qpos] = datavec[i];
        bpos[qpos] = i;
        qpos++;

        if(i-bpos[ringstart] >= k) { ringstart++; }
        if(queue[ringstart] > maxbasis) { maxbasis = queue[ringstart]; maxbasispost = bpos[ringstart]; }
    }
    int lowpoint;
    for(lowpoint=maxbasispost;lowpoint>=0&&datavec[lowpoint] > maxbasis;lowpoint--);
    int endpoint = lowpoint+k;

    ofstream fout("secventa.out");
    fout<<lowpoint+1<<" "<<endpoint<<" "<<maxbasis;
    return 0;
}