Cod sursa(job #1700651)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 10 mai 2016 22:25:46
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>
using namespace std;

const int NMAX = 30005;
const int   SM = 1<<20;

int n;
int val[NMAX],
    ans[NMAX],
    aib[NMAX];

inline int lsb(int arg) {
    return arg&(-arg);
}

inline void update(int poz, int val) {
    while(poz<=n) {
        aib[poz]+=val;
        poz+=lsb(poz);
    }
}

inline int query(int a) {
    int ans = 0;
    while(a) {
        ans+=aib[a];
        a-=lsb(a);
    }
    return ans;
}

inline int query(int a, int b) {
    return query(b)-query(a-1);
}

inline int cbin(int arg) {
    int m, ans = 0;
    for(m=SM; m; m>>=1)
        if((ans|m)<=n && query(ans|m)<arg)
            ans|=m;
    return ans + 1;
}

int main(void) {
    FILE *fi = fopen("schi.in","r");
    FILE *fo = fopen("schi.out","w");
    int i, j, p;

    fscanf(fi,"%d",&n);
    for(i=1; i<=n; ++i) {
        fscanf(fi,"%d",&val[i]);
        update(i, 1);
    }

    for(i=n; i>=1; --i) {
        p = cbin(val[i]);
        update(p, -1);
        ans[p] = i;
    }

    for(i=1; i<=n; ++i)
        fprintf(fo,"%d\n",ans[i]);

    fclose(fi);
    fclose(fo);
    return 0;
}