Cod sursa(job #2136528)

Utilizator GoogalAbabei Daniel Googal Data 19 februarie 2018 22:52:21
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <iostream>
#include <fstream>

using namespace std;

typedef long long ll;

ifstream in("farfurii.in");
ofstream out("farfurii.out");

const int NMAX = 1e5;

ll n, k;
ll aint[1 + 4 * NMAX];

void add(ll node, ll pos, ll le, ll ri) {
  ll mid = (le + ri) / 2;

  if(le == ri)
    aint[node] = 1;
  else {
    add(2 * node, pos, le, mid);
    add(2 * node + 1, pos, mid + 1, ri);
    aint[node] += aint[2 * node] + aint[2 * node + 1];
  }
}

void query(ll node, ll pos, ll le, ll ri) {
  ll mid = (le + ri) / 2;

  if(le == ri) {
    aint[node] = 0;
    out << le << ' ';
  } else {
    if(pos <= aint[2 * node])
      query(2 * node, pos, le, mid);
    else
      query(2 * node + 1, pos - aint[2 * node], mid + 1, ri);
    aint[node] = aint[2 * node] + aint[2 * node + 1];
  }
}

int main()
{
  in >> n >> k;
  add(1, 1, 1, n);

  for(ll i = n - 1; i >= 0; i--) {
    if(k <= i * (i - 1) / 2)
      query(1, 1, 1, n);
    else {
      query(1, k - i * (i - 1) / 2 + 1, 1, n);
      k = i * (i - 1) / 2;
    }
  }

  in.close();
  out.close();
  return 0;
}