Cod sursa(job #2489491)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 8 noiembrie 2019 20:29:31
Problema Schi Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#include <stack>
#define NMAX 30005

using namespace std;

stack < int > st;

int aib[NMAX], clas[NMAX], n, a;

void update(int p)
{
    for (int i = p; i <= n; i += i & -i)
        aib[i]++;
}

int query(int p)
{
    int suma = 0;
    for (int i = p; i >= 1; i -= i & -i)
        suma += aib[i];
    return p - suma;
}

int bsearch(int p, int s)
{
    int st, dr, pos, mij;
    int suma;
    st = 1;
    dr = p;
    pos = -1;
    while (st <= dr)
    {
        mij =(st + dr) / 2;
        suma = query(mij);
        if (suma == s)
        {
            pos = mij;
            dr = mij - 1;
        }
        else if (suma > s) dr = mij - 1;
        else st = mij + 1;
    }
    return pos;
}

int main()
{
    ifstream fin("schi.in");
    ofstream fout("schi.out");

    fin >> n;

    for (int i = 1; i <= n; ++i)
    {
        fin >> a;
        st.push(a);
    }

    for (int i = n; i >= 1; --i)
    {
        a = st.top();
        st.pop();
        int p = bsearch(n, a);
        clas[p] = i;
        update(p);
    }

    for (int i = 1; i <= n; ++i)
        fout << clas[i] << "\n";

    return 0;
}