Cod sursa(job #2776915)

Utilizator Alex_DiaconuDiaconu Alexandru Alex_Diaconu Data 21 septembrie 2021 16:39:28
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>

using namespace std;

ifstream cin ("schi.in");
ofstream cout ("schi.out");

const int N=30005;
int a[N], v[N], p[N], n;

int sum(int k)
{
    int s=0;
    while(k>=1)
    {
        s+=a[k];
        k-=k&-k;
    }
    return s;
}

int bs(int val)
{
    int l=1,r=n,m;
    while(l<r)
    {
        m=(l+r)/2;
        int s=sum(m);
        if(s==val)
        {
            r=m;
        }
        else if(s>val)
        {

            r=m-1;
        }
        else
        {
            l=m+1;
        }
    }
    return l;
}

void add(int k,int x)
{
    while(k<=n)
    {
        a[k]+=x;
        k+=k&-k;
    }
}

int main()
{
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> v[i];
        add(i,1);
    }
    int e;
    for(int i=n; i>=1; i--)
    {
        e=bs(v[i]);
        p[e]=i;
        add(e,-1);
    }
    for(int i=1; i<=n; i++)
    {
        cout << p[i] << "\n";
    }
    return 0;
}