Cod sursa(job #2233030)

Utilizator Daria09Florea Daria Daria09 Data 21 august 2018 22:01:28
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <bits/stdc++.h>
#define NMAX 30005
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int aib[NMAX],a[NMAX],sol[NMAX];
int n,bitMax;
void add(int k,int val)
{
    for(;k<=n;k+=(k&-k))
        aib[k]+=val;
}
void read()
{
    f>>n;
    for(int i=1;i<=n;i++)
    {
        f>>a[i];
        add(i,1);
    }
}
int sum(int val)
{
    int sol=0;
    for(;val>0;val-=(val&-val))
        sol+=aib[val];
    return sol;
}
int query(int val)
{
    int st=1,dr=n,sol,mij,x;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        x=sum(mij);
        if(x>=val)
        {
            dr=mij-1;
            sol=mij;
        }
        else
            st=mij+1;
    }
    return sol;
}
void solve()
{
    for(int i=n;i>=1;i--)
    {
        int pos=query(a[i]);
        sol[pos]=i;
        add(pos,-1);
    }
    for(int i=1;i<=n;i++)
        g<<sol[i]<<"\n";
}
int main()
{
    read();
    solve();
    return 0;
}