Cod sursa(job #2777991)

Utilizator cyg_dragos10Ivan Dragos cyg_dragos10 Data 27 septembrie 2021 07:55:48
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <algorithm>
using namespace std;
const int NMAX = 30005;
ifstream cin("schi.in");
ofstream cout("schi.out");
int n;
int v[NMAX], aib[NMAX], ans[NMAX];
void update(int poz, int value){
    for(int i = poz; i <= n; i += i & (-i))
        aib[i] += value;
}
int querry(int poz){
    long long sum = 0;
    for(int i = poz; i > 0; i -= i & (-i))
        sum += aib[i];
    return sum;
}
int CautareBinara (int val)
{
    int st=1,dr=n,mij,suma;
    mij=(st+dr)/2;
    while(st<dr)
    {
        mij = (st + dr) / 2;
        suma = querry(mij);
        if(suma == val)
        {
            dr = mij;
        }
        else if(suma > val)
        {
            dr = mij-1;
        }
        else
        {
            st = mij+1;
        }
    }
    return st;
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> v[i];
        update(i, 1);
    }
    for(int i = n; i >= 1; i --)
    {
        int sol = CautareBinara(v[i]);
        /*while(querry(sol) == v[i])
            sol--;
        sol++;*/
        ans[sol] = i;
        update(sol, -1);
    }
    for(int i = 1; i <= n; i ++)
    {
        cout << ans[i] << '\n';
    }
    return 0;
}