Cod sursa(job #2049832)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 27 octombrie 2017 18:09:15
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
#define DIM 30001
using namespace std;

ifstream fin ("schi.in");
ofstream fout ("schi.out");
int n,i,x,st,dr,mid,v[DIM],sol[DIM],a[DIM];
void update (int p,int x){
    for (;p<=n;p+=(p&-p))
        a[p]+=x;
}
int query (int p){
    int sol = 0;
    for (;p>=1;p-=(p&-p))
        sol += a[p];
    return sol;
}
int main (){

    fin>>n;
    for (i=1;i<=n;i++){
        fin>>v[i];
        /// facem update cu 1 de la poz x in colo
        update (i,1);
    }
    for (i=n;i>=1;i--){
        /// il cautam binar pe v[i]
        st = 1;
        dr = n;
        while (st <= dr){
            int mid = (st+dr)/2;
            if (query(mid) < v[i])
                st = mid+1;
            else
                dr = mid-1;
        }
        sol[st] = i;
        update (st,-1); // facem -1;
    }
    for (i=1;i<=n;i++)
        fout<<sol[i]<<"\n";




    return 0;
}