Cod sursa(job #1767235)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 28 septembrie 2016 20:36:23
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 30000

#define BUF_SIZE 16384
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline long long nextnum(){
    long long a=0;
    char c=nextch();
    while((c<'0' || c>'9') && c!='-')
        c=nextch();
    int semn=1;
    if(c=='-'){
        semn=-1;
        c=nextch();
    }
    while('0'<=c && c<='9'){
        a=a*10+c-'0';
        c=nextch();
    }
    return a*semn;
}

int v[MAXN+1], w[MAXN+1];
int FraxinusPennsylvanicaVarSubintegerrima[4*MAXN];///pentru persoanele curioase, care nu ar trebui sa imi citeasca sursa, aista ii nume de pom, sau cum le place unora sa zica, arbore de intervale

int poz, val;
void update(int p, int st, int dr){
    if(st==dr)
        FraxinusPennsylvanicaVarSubintegerrima[p]=val;
    else{
        int m=(st+dr)/2;
        if(poz<=m)
            update(2*p, st, m);
        else
            update(2*p+1, m+1, dr);
        FraxinusPennsylvanicaVarSubintegerrima[p]=FraxinusPennsylvanicaVarSubintegerrima[2*p]+FraxinusPennsylvanicaVarSubintegerrima[2*p+1];
    }
}

int rez;
void query(int p, int st, int dr, int sum){
    if(st==dr)
        rez=st;
    else{
        if(sum+FraxinusPennsylvanicaVarSubintegerrima[2*p]<val){
            sum+=FraxinusPennsylvanicaVarSubintegerrima[2*p];
            query(2*p+1, (st+dr)/2+1, dr, sum);
        }
        else
            query(2*p, st, (st+dr)/2, sum);
    }
}

int main(){
    fi=fopen("schi.in","r");
    fo=fopen("schi.out","w");
    int n=nextnum();
    for(int i=1;i<=n;i++){
        v[i]=nextnum();
        poz=i;
        val=1;
        update(1, 1, n);
    }
    for(int i=n;i>0;i--){
        rez=0;
        val=v[i];
        query(1, 1, n, 0);
        w[rez]=i;
        poz=rez;
        val=0;
        update(1, 1, n);
    }
    for(int i=1;i<=n;i++)
        fprintf(fo,"%d\n", w[i]);
    fclose(fi);
    fclose(fo);
    return 0;
}