Cod sursa(job #1826026)

Utilizator gorneanu.andreiFMI Gorneanu Andrei gorneanu.andrei Data 9 decembrie 2016 23:04:11
Problema Schi Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <stdio.h>
#define MAX 30005
int arb[4 * MAX], cls[MAX], poz;

void apdeit(int nod,int st,int dr,int poz,int val){

    if(st == dr){
        arb[nod] = val;
        return;
    }
    int mid = (st + dr) / 2;

    if(poz <= mid)
        apdeit(2 * nod,st,mid,poz,val);
    else
        apdeit(2 * nod + 1,mid + 1,dr,poz,val);

    arb[nod] = arb[2 * nod] + arb[2 * nod + 1];
}

void cueri(int nod,int st,int dr,int val){

    if(st == dr){
        poz = dr;
        return;
    }

    int mid = (st + dr) / 2;

    if(val > arb[2 * nod])
        cueri(2 * nod + 1,mid + 1,dr,val - arb[2 * nod]);
    else
        cueri(2 * nod,st,mid,val);
}

int main(){

    int n, i, v[MAX];
    FILE *f, *g;
    f = fopen("schi.in","r");
    g = fopen("schi.out","w");

    fscanf(f,"%d",&n);

    for(i = 1;i <= n; ++i){
        fscanf(f,"%d",&v[i]);
        apdeit(1,1,n,i,1);
    }

    for(i = n;i >= 1; --i){
        cueri(1,1,n,v[i]);
        cls[poz] = i;
        apdeit(1,1,n,poz,0);
    }

    for(i = 1;i <= n; ++i){
        fprintf(g,"%d\n",cls[i]);
        }

    return 0;
}