Cod sursa(job #3280768)

Utilizator ciusMocan Caius cius Data 27 februarie 2025 15:13:47
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
const int kMaxN=30005;
int v[kMaxN],aib[kMaxN],d[kMaxN],n,l,m,r;
void update(int val, int i)
{
    while(i<=kMaxN)
    {
        aib[i]+=val;
        i+=i&(-i);
    }
}
int sum(int i)
{
    int sum=0;
    while(i>0)
    {
        sum+=aib[i];
        i-=i&(-i);
    }
    return sum;
}
int b_search(int val)
{
    int l=1;
    int r=n;
    int poz=0;
    int mid;
    while(l<=r)
    {
        int m=(l+r)/2;
        mid=sum(m);
        if(mid==val)
        {
            r=m-1;
            poz=m;
        }
        if(mid<val)
            l=m+1;
        else
            r=m-1;
    }
    return poz;
}
int main()
{
    fin>>n;
    for(int i=1; i<=n; ++i)
    {
        fin>>v[i];
        update(1,i);
    }
    for(int i=n; i>0; --i)
    {
        int p=b_search(v[i]);
        d[p]=i;
        update(-1,p);
    }
    for(int i=1; i<=n; i++)
        fout<<d[i]<<"\n";
}