Cod sursa(job #474010)

Utilizator daniel.dumitranDaniel Dumitran daniel.dumitran Data 2 august 2010 01:13:03
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 128000

int n;
int inv[MAXN];
int rt[4 * MAXN];
FILE *f;
long long k;

int get_and_mark(int node, int ord, int st, int en) {
  ++rt[node];

  if (st + 1 == en) return st;

  int mid = (st + en) / 2;
  int left_node = node * 2 + 1;
  int right_node = node * 2 + 2;
  int av_left = mid - st - rt[left_node];
  if (av_left > ord) {
    return get_and_mark(left_node, ord, st, mid);
  } else {
    return get_and_mark(right_node, ord - av_left, mid, en);
  }
}

int main() {
  f = fopen("farfurii.in", "rt");
  fscanf(f, "%d %lld", &n, &k);
  fclose(f);

  inv[n - 1] = 0;
  for (int i = n - 2; i >= 0; --i) {
    int max = n - i - 1;
    if (k < max) max = k;
    inv[i] = max;
    k -= max;
  }

  memset(rt, 0, sizeof(rt));

  f = fopen("farfurii.out", "wt");
  for (int i = 0; i < n; ++i) {
    inv[i] = get_and_mark(0, inv[i], 0, n);
    fprintf(f, "%d ", inv[i] + 1);
  }
  fprintf(f, "\n");
  fclose(f);

  return 0;
}