Cod sursa(job #1776286)

Utilizator AnaRaduAna-Maria Radu AnaRadu Data 11 octombrie 2016 09:24:52
Problema Schi Scor 100
Compilator cpp Status done
Runda cerculdeinfo-lectia2-arborideintervale Marime 1.04 kb
#include <stdio.h>
#include <algorithm>
#define lim 30003
using namespace std;
int aib[lim],v[lim],fr[lim],n;
void update(int poz,int val){
    while(poz<=n){
        aib[poz]+=val;
        poz=poz+(poz^(poz&(poz-1)));
    }
}
int query(int poz){
    int s=0;
    while(poz>=1){
        s+=aib[poz];
        poz=poz-(poz^(poz&(poz-1)));
    }
    return s;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("schi.in","r");
    fout=fopen("schi.out","w");
    int i,l1,l2,mij,poz,x;
    fscanf(fin,"%d",&n);
    for(i=1;i<=n;i++){
        fscanf(fin,"%d",&v[i]);
        update(i,1);
    }
    for(i=n;i>=1;i--){
        l1=1;
        l2=n;
        poz=1000000;
        while(l1<=l2){
            mij=(l1+l2)/2;
            x=query(mij);
            if(x>=v[i]){
                l2=mij-1;
                poz=mij;
            }
            else
                l1=mij+1;
        }
        fr[poz]=i;
        update(poz,-1);
    }
    for(i=1;i<=n;i++)
        fprintf(fout,"%d\n",fr[i]);
    fclose(fout);
return 0;
}