Cod sursa(job #2049811)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 27 octombrie 2017 17:44:59
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <cstdio>

using namespace std;
int v[30001],sol[30001],w[30001],n;
void update (int p,int nr){
    for (;p<=n;p+=(p&-p))
        w[p]+=nr;
}
int query (int p){
    int s=0;
    for (;p;p-=(p&-p))
        s+=w[p];
    return s;
}
void cautapoz (int poz,int c){
    int st,dr,mid;
    st=1;
    dr=n;
    while (st<=dr){
        mid=(st+dr)/2;
        if (query (mid)<poz)
            st=mid+1;
        else dr=mid-1;
    }
    sol[st]=c;
    update (st,-1);
}
int main()
{
    FILE *fin=fopen ("schi.in","r");
    FILE *fout=fopen ("schi.out","w");
    int i;
    fscanf (fin,"%d",&n);
    for (i=1;i<=n;i++){
        fscanf (fin,"%d",&v[i]);
        update (i,1);
    }
    for (i=n;i>0;i--){
        cautapoz (v[i],i);
        //update ();
    }
    for (i=1;i<=n;i++)
        fprintf (fout,"%d\n",sol[i]);
    return 0;
}