Cod sursa(job #2752411)

Utilizator PaduraruCristianPaduraru Cristian Daniel PaduraruCristian Data 17 mai 2021 21:54:57
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("schi.in");
ofstream g("schi.out");

int v[120004];
int poz[30001];
int clasamnet[30001];
int n, i;

void update(int index, int st, int dr, int place)
{

    ++v[index];

    if(st==dr && place==1)
    {
        clasamnet[st] = i;
        return;
    }

    int mij = (st+dr)/2;
    int poz_ocupate_la_st = v[2*index];
    int poz_neocupate_la_st = mij-st+1 - poz_ocupate_la_st;

    /// nr de poz din intervalul [st,mij] - nr poz ocupate din interval >= pozitia pe care vreau sa pun
    if(mij-st+1 - v[index*2] >= place && place>0)
        update(2*index, st, mij, place);
    else
        update(2*index+1, mij+1, dr, place - poz_neocupate_la_st);



}


int main()
{

    f>>n;
    for(i=1;i<=n;i++)
        f>>poz[i];

    for(i=n; i; --i)
    {
        /// i intra pe a poz[i]-a pozitie libera;
        update(1, 1,n, poz[i]);
    }
    for(i=1;i<=n;++i)
        g<<clasamnet[i]<<'\n';
    return 0;
}