Cod sursa(job #1292628)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 14 decembrie 2014 15:56:39
Problema Schi Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>
#define MAXN 30000
#define LOGN 15
#define MAXP (1<<(LOGN+1))
int t[MAXP], v[MAXN], ans[MAXN];
int poz, val;
void update(int p, int st, int dr){
    int m=(st+dr)/2;
    if(st==dr){
        poz=st;
        t[p]--;
        return ;
    }
    if(val>t[2*p+1]){
        val-=t[2*p+1];
        update(2*p+2, m+1, dr);
    }else{
        update(2*p+1, st, m);
    }
    t[p]=t[2*p+1]+t[2*p+2];
}
void dfs(int p, int st, int dr){
    int m=(st+dr)/2;
    t[p]=dr-st+1;
    if(st<dr){
        dfs(2*p+1, st, m);
        dfs(2*p+2, m+1, dr);
    }
}
int main(){
    int n, i;
    FILE *fin, *fout;
    fin=fopen("schi.in", "r");
    fout=fopen("schi.out", "w");
    fscanf(fin, "%d", &n);
    for(i=0; i<n; i++){
        fscanf(fin, "%d", &v[i]);
    }
    dfs(0, 0, n-1);
    for(i=n-1; i>=0; i--){
        val=v[i];
        update(0, 0, n-1);
        ans[poz]=i;
    }
    for(i=0; i<n; i++){
        fprintf(fout, "%d\n", ans[i]+1);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}