Cod sursa(job #2925586)

Utilizator Diana_IonitaIonita Diana Diana_Ionita Data 15 octombrie 2022 19:04:21
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("schi.in");
ofstream fout ("schi.out");
int aib[100003], n, k;

int x[100003], sol[100003];
void update(int x, int val)
{
    int i;

    for(i=x; i<=n; i+=i&(-i))
    {
        aib[i]+=val;

    }
}
int inter(int x)
{
    int p;
    int suma = 0;
    for(p=x; p>0; p-=p&(-p))
    {
        suma += aib[p];
    }
    return suma;
}
int cauta(int k)
{
    int st, dr, mij, p, suma;
    st = 1;
    dr = n;
    p = n+1;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        suma = inter(mij);
        if (suma == k)
        {
            p = mij;
            dr = mij - 1;
        }
        else if (suma < k) st = mij + 1;
        else dr = mij - 1;
    }
    return p;
}
int main()
{
    fin>>n;
    int i;
    for(i=1; i<=n; i++)
    {
        fin>>x[i];
        update(i,1);
    }
    for(i=n; i>0; i--)
    {
        int poz=cauta(x[i]);
        sol[poz] = i;
        update(poz, -1);
    }
    for(i = 1; i <= n; i++)
    {
        fout << sol[i] << "\n";
    }
    return 0;
}