Cod sursa(job #1292532)

Utilizator hrazvanHarsan Razvan hrazvan Data 14 decembrie 2014 14:09:37
Problema Farfurii Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>
#define MAXN 100000

int aib[MAXN + 1];

int ultb(int x){
  return x & (-x);
}

int suma(int poz){
  if(poz > 0){
    return aib[poz] + suma(poz - ultb(poz));
  }
  return 0;
}

int caut(int x, int n){
  int i = 0, pas = 1 << 16;
  while(pas > 0){
    if(i + pas < n && suma(i + pas) < x)
      i += pas;
    pas >>= 1;
  }
  return i + 1;
}

void update(int poz, int x, int n){
  if(poz <= n){
    aib[poz] += x;
    poz += ultb(poz);
    update(poz, x, n);
  }
}

int main(){
  FILE *in = fopen("farfurii.in", "r");
  int n;
  long long  m;
  fscanf(in, "%d%lld", &n, &m);
  fclose(in);
  int i;
  for(i = 1; i <= n; i++){
    update(i, 1, n);
  }
  FILE *out = fopen("farfurii.out", "w");
  int x;
  long long y;
  for(i = 1; i <= n; i++){
    y = 1LL * (n - i) * (n - i - 1) / 2 - m;
    if(y >= 0)
      x = caut(1, n);
    else{
      x = caut(-y + 1, n);
      m += y;
    }
    fprintf(out, "%d ", x);
    update(x, -1, n);
  }
  fclose(out);
  return 0;
}