Cod sursa(job #1425359)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 27 aprilie 2015 12:58:18
Problema Schi Scor 100
Compilator cpp Status done
Runda pregatire-lot-aib Marime 0.89 kb
#include<fstream>
using namespace std;
int n, i, x;
int v[30003], sol[30003], w[30003];
ifstream fin("schi.in");
ofstream fout("schi.out");
void update(int x, int val){
    for(; x <= n; x += (x & -x)){
        v[x] += val;
    }
}
int query(int x){
    int sum = 0;
    for(; x >= 1; x -= (x & -x)){
        sum += v[x];
    }
    return sum;
}
int binar(int x){
    int p, u, mid;
    p = 1;
    u = n;
    while(p <= u){
        mid = (p + u) / 2;
        if(query(mid) >= x){
            u = mid - 1;
        }
        else{
            p = mid + 1;
        }
    }
    return p;
}
int main(){
   fin>> n;
   for(i = 1; i <= n; i++){
        fin>> w[i];
        v[i] = (i & -i);
   }
   for(i = n; i >= 1; i--){
        x = binar(w[i]);
        sol[x] = i;
        update(x, -1);
   }
   for(i = 1; i <= n; i++){
    fout<< sol[i] <<"\n";
   }
   return 0;
}