Cod sursa(job #1545608)

Utilizator gbibBacotiu Gabi gbib Data 6 decembrie 2015 21:33:58
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>
#define step(x) (x&(-x))
using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
int a[30003],aib[30003],n,sol[30003];

void add(int x ,int val)
{
    int i;
    for(i=x;i<=n;i+=step(i))
    {
        aib[i]+=val;
    }
}

int query(int x)
{
    int s=0,i;
    for(i=x;i>0;i-=step(i))
    {
        s+=aib[i];
    }
    return s;
}
int bs(int val)
{
    int s,d,m;
    s=1;
    d=n;
    while(s<=d)
    {
        m=(s+d)/2;
        if(query(m)<val)
        {
            s=m+1;
        }
        else
        {
            d=m-1;
        }
    }
    return s;
}
int main()
{int i,p;
in>>n;
for(i=1;i<=n;i++)
    in>>a[i];
for(i=n;i>0;i--)
{
    add(i,1);
}
for(i=n;i>0;i--)
{
    p=bs(a[i]);
    add(p,-1);
    sol[p]=i;
}
for(i=1;i<=n;i++)
{
    out<<sol[i]<<'\n';
}
    return 0;
}