Cod sursa(job #1292889)

Utilizator hrazvanHarsan Razvan hrazvan Data 14 decembrie 2014 22:05:53
Problema Schi Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <stdio.h>
#define MAXN 30000
#define MAXNOD 65536
int arb[MAXNOD + 1], v[MAXN], point[MAXN];

void qs(int st, int dr){
  int i = st, j = dr, piv = v[(st + dr) / 2], aux;
  while(i <= j){
    while(v[i] < piv)
      i++;
    while(piv < v[j])
      j--;
    if(i <= j){
      aux = v[i];
      v[i] = v[j];
      v[j] = aux;

      aux = point[i];
      point[i] = point[j];
      point[j] = aux;

      i++;
      j--;
    }
  }
  if(st < j)
    qs(st, j);
  if(i < dr)
    qs(i, dr);
}

void init(int p, int st, int dr){
  arb[p] = dr - st + 1;
  if(st != dr){
    int m = (st + dr) / 2;
    init(2 * p, st, m);
    init(2 * p + 1, m + 1, dr);
  }
}
int caut(int p, int st, int dr, int x){
  arb[p]--;
  if(st != dr){
    int m = (st + dr) / 2;
    if(arb[2 * p] < x)
      caut(2 * p + 1, m + 1, dr, x - arb[2 * p]);
    else
      caut(2 * p, st, m, x);
  }
  else
    return st;
}

int main(){
  FILE *in = fopen("schi.in", "r");
  int n, i;
  fscanf(in, "%d", &n);
  for(i = 0; i < n; i++){
    fscanf(in, "%d", &v[i]);
  }
  fclose(in);
  init(1, 1, n);
  for(i = n - 1; i >= 0; i--){
    point[i] = i + 1;
    v[i] = caut(1, 1, n, v[i]);
  }
  qs(0, n - 1);
  FILE *out = fopen("schi.out", "w");
  for(i = 0; i < n; i++){
    fprintf(out, "%d\n", point[i]);
  }
  fclose(out);
  return 0;
}