Cod sursa(job #2788422)

Utilizator Iulia_DianaIulia Diana Iulia_Diana Data 25 octombrie 2021 17:45:01
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb

#include <fstream>
#include <algorithm>

using namespace std;

const int NMAX = 30005;

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

int v[NMAX],aib[NMAX],ans[NMAX],n;

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

long long query(int i)
{
    long long sum = 0;
    for(; i > 0; i -= i & (-i))
        sum += aib[i];
    return sum;

}
int bs(int val)
{
    int st=1,dr=n,sum;
    while(st<dr)
    {
        int mid = st + (dr - st) / 2;
        sum = query(mid);
        if(sum == val)
            dr = mid;
        else
            if(sum > val)
            {
                dr = mid - 1;
            }
            else
            {
                st = mid + 1;
            }
    }
    return st;
}

int main()
{
    fin>>n;
    for(int i = 1;i <= n;i++)
    {
        fin>>v[i];
        update(i,1);
    }
    for(int i = n;i >= 1;i--)
    {
        int sol = bs(v[i]);
        ans[sol] = i;
        update(sol, -1);
    }
    for(int i = 1;i <= n;i++)
    {
        fout<<ans[i]<<'\n';
    }
    return 0;
}