Cod sursa(job #2876993)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 23 martie 2022 23:55:44
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>
using namespace std;

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

const int nmax = 3e4 + 3;
int n, v[nmax], sol[nmax], usu[nmax], x;

void update(int x, int val)
{
    while (x <= n)
    {
        usu[x] += val;
        x += (x&-x);
    }
}

int query(int x)
{
    int sol = 0;

    while(x)
    {
        sol += usu[x];
        x -= (x&-x);
    }

    return sol;
}

int bs_perm(int val)
{
    int st=1, dr=n, mij, sol, aux;

    while (st <= dr)
    {
        mij = (st + dr) / 2;
        aux = query(mij);

        if (aux == val)
        {
            sol = mij;
            dr = mij - 1;
        }
        else if(aux < val) st = mij + 1;
        else dr = mij - 1;
    }

    return sol;
}

int main()
{
    f >> n;
    for (int i = 1; i <= n; ++i)
    {
          f >> v[i];
          update(i, 1);
    }

    for (int i = n; i >= 1; --i)
    {
        x = bs_perm(v[i]);
        sol[x] = i;
        update(x, -1);
    }

    for (int i = 1; i <= n; ++i) g << sol[i] << '\n';

    return 0;
}