Cod sursa(job #3158817)

Utilizator biancalautaruBianca Lautaru biancalautaru Data 19 octombrie 2023 21:02:02
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#define DIM 30001
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
int n,poz,v[DIM],aib[DIM],sol[DIM];

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

int query(int k) {
    int s=0;
    for (int i=k;i>=1;i-=(i&-i))
        s+=aib[i];
    return s;
}

int cautbin(int x) {
    int st=1;
    int dr=n;
    while (st<=dr) {
        int mid=(st+dr)/2;
        if (x>query(mid))
            st=mid+1;
        else
            dr=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--) {
        poz=cautbin(v[i]);
        sol[poz]=i;
        update(poz,-1);
    }
    for (int i=1;i<=n;i++)
        fout<<sol[i]<<"\n";
    return 0;
}