Cod sursa(job #1478101)

Utilizator andrei_r_97Radoi Andrei andrei_r_97 Data 27 august 2015 20:11:39
Problema Order Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <stdio.h>

#define TREE_SIZE 65536

int arb[TREE_SIZE + 1];

void update(int nod, int val, int left, int right)
{
  int mid;
  
  arb[nod] += 1;
  
  if (left != right) {
      
    mid = (left + right) / 2;
    
    if (mid >= val)
      update(2 * nod, val, left, mid);
    else
      update(2 * nod + 1, val, mid + 1, right);
  }
}

int extract(int nod, int val, int left, int right)
{
  int result = -1, mid;

  arb[nod]--;
  
  if (left == right) {
    result = left;
  }
  else {
    mid = (left + right) / 2;
    
    if (arb[2 * nod] >= val) {
      result = extract(2 * nod, val, left, mid);
    }
    else {
      val -= arb[2 * nod];
      result = extract(2 * nod + 1, val, mid + 1, right);
    }
  }
  
  return result;
}

int main()
{
  FILE *in, *out;
  int n, i, start = 1, eliminare;
  
  in = fopen("order.in", "r");
  fscanf(in, "%d", &n);
  fclose(in);
  
  for (i = 1; i <= n; i++) {
    update(1, i, 1, n);
  }
  
  out = fopen("order.out", "w");
  for (i = 1; i <= n; i++) {
    eliminare = start + i;
    if (eliminare % (n + 1 - i) == 0)
      eliminare = n - i + 1;
    else
      eliminare %= (n - i + 1);
    fprintf(out, "%d ", extract(1, eliminare, 1, n));
    start = eliminare > 1 ? (eliminare - 1) : (n - i);
  }
  
  fclose(out);
  
  return 0;
}