Cod sursa(job #1821455)

Utilizator andrei_diaconu11Andrei C. Diaconu andrei_diaconu11 Data 3 decembrie 2016 10:13:38
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <stdio.h>
#include <algorithm>
#define MAXN 30000
int arb[4*MAXN], schiori[MAXN+1], in[MAXN+1], pa[MAXN+1];

void build_arb(int nod, int st, int dr){
  arb[nod]=dr-st+1;
  if(st!=dr){
    int div=(st+dr)/2;
    build_arb(2*nod,st,div);
    build_arb(2*nod+1,div+1,dr);
  }
}

bool cmp(int a, int b){
  return schiori[a]<schiori[b];
}

int find_n_kill(int nod, int st, int dr, int nr){
  if(st==dr){
    arb[nod]=0;
    return 1;
  }
  int div=(st+dr)/2;
  arb[nod]--;
  if(arb[2*nod]>=nr)
    return find_n_kill(2*nod,st,div,nr);
  else
    return find_n_kill(2*nod+1,div+1,dr,nr-arb[2*nod])+(div-st+1);
}

int main()
{
  int n, i;
  FILE *fi=fopen("schi.in", "r"), *fo=fopen("schi.out", "w");
  fscanf(fi, "%d", &n);
  for(i=1;i<=n;i++)
    fscanf(fi, "%d", &in[i]),pa[i]=i;
  build_arb(1,1,n);
  for(i=n;i>0;i--)
    schiori[i]=find_n_kill(1,1,n,in[i]);
  std::sort(pa+1,pa+n+1,cmp);
  for(i=1;i<=n;i++)
    fprintf(fo, "%d\n", pa[i]);
  fclose(fi);
  fclose(fo);
  return 0;
}