Cod sursa(job #2690750)

Utilizator popashtefan10Popa Stefan popashtefan10 Data 25 decembrie 2020 17:12:18
Problema Farfurii Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <iostream>
#include <cstdio>

using namespace std;

const int NMAX = 100000;

int n, k;
int aint[2 * NMAX + 5];

void update(int poz) {
  aint[poz += n - 1] = 1;
  for(poz >>= 1; poz; poz >>= 1)
    aint[poz] = aint[poz << 1] + aint[poz << 1 | 1];
}

int query(int poz) {
  int sum = 0;

  for(int st = n, dr = poz + n - 1; st <= dr; st >>= 1, dr >>= 1) {
    if(st & 1)
      sum += aint[st++];
    if(!(dr & 1))
      sum += aint[dr--];
  }

  return sum;
}

int get_poz(int i) {
  return max((long long)k - (long long)(n - i) * (n - i - 1) / 2 + 1, (long long)1);
}

int get_nr(int poz) {
  int st = 1, dr = n;

  while(st <= dr) {
    int mij = (st + dr) / 2, cpoz = mij - query(mij);

    if(cpoz < poz)
      st = mij + 1;
    else if(cpoz > poz || aint[mij + n - 1] == 1)
      dr = mij - 1;
    else
      return mij;
  }

  return -1;
}

int main() {
  freopen("farfurii.in", "r", stdin);
  freopen("farfurii.out", "w", stdout);

  scanf("%d %lld", &n, &k);
  for(int i = 1; i <= n; i++) {
    int p = get_poz(i), nr = get_nr(p);
    printf("%d ", nr);
    update(nr);
    k -= p - 1;
  }

  return 0;
}