Cod sursa(job #1107918)

Utilizator assa98Andrei Stanciu assa98 Data 14 februarie 2014 22:46:31
Problema Schi Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N=30100;

int aib[MAX_N];
int v[MAX_N];
int poz[MAX_N];

void update(int poz,int val=-1) {
    while(poz<30000) {
        aib[poz]+=val;
        poz+=(poz&(-poz));
    }
}

int query(int val) {
    int poz=0;
    for(int p=3; p>=0;p--) {
        if(poz+(1<<p)>=MAX_N) {
            continue;
        }
        if(aib[poz+(1<<p)]<val) {
            val-=aib[poz+(1<<p)];
            poz+=(1<<p);
        }
    }
    return poz+1;
}

int main() {
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    
    int n;
    scanf("%d",&n);

    for(int i=1;i<=n;i++) {
        scanf("%d",&v[i]);
        update(i,1);
    }

    for(int i=n;i>=1;i--) {
        poz[i]=query(v[i]);
        update(poz[i]);
    }

    for(int i=1;i<=n;i++) {
        v[poz[i]]=i;
    }
    for(int i=1;i<=n;i++) {
        printf("%d\n",v[i]);
    }

    return 0;
}