Cod sursa(job #2116270)

Utilizator racheriunicolaechowchow racheriunicolae Data 27 ianuarie 2018 14:29:52
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#define MAX 30005
using namespace std;

int nr(int x)
{
    return (x&-x);
}
int n,arb[MAX],v[MAX],vec[MAX];
void update(int poz,int val)
{
    while(poz<=n)
    {
        arb[poz]+=val;
        poz+=nr(poz);
    }
}
int query(int poz)
{
    int ans=0;
    while(poz)
    {
        ans+=arb[poz];
        poz-=nr(poz);
    }
    return ans;
}
int bs(int val)
{
    int st,dr,m,k,ans;
    st=1;
    dr=n;
    while(st<=dr)
    {
        m=(st+dr)/2;
        k=query(m);
        if(k==val)
        {
            ans=m;
            dr=m-1;
        }
        else if(k<val)st=m+1;
        else dr=m-1;
    }
    return ans;
}
int i,poz;
int main()
{
    ifstream fin("schi.in");
    ofstream fout("schi.out");
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>v[i];
       update(i,1);
    }
    for(i=n;i>=1;i--)
    {
        poz=bs(v[i]);
        vec[poz]=i;
        update(poz,-1);
    }
    for(i=1;i<=n;i++)fout<<vec[i]<<"\n";
    return 0;
}