Cod sursa(job #2966810)

Utilizator Vincent47David Malutan Vincent47 Data 18 ianuarie 2023 15:03:48
Problema Farfurii Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <cmath>

using namespace std;
    ifstream cin("datorii.in");
    ofstream cout("datorii.out");

    typedef long long ll;

    const int dim = 100001;
    ll arb[4 * dim];

    void build(ll nod, ll l, ll r)
    {
        if (l == r)
            arb[nod] = 1;
        else
        {
            ll mid = (l + r) >> 1;
            build(nod << 1, l, mid);
            build(nod << 1 | 1, mid + 1, r);
            arb[nod] = arb[nod<<1|1] + arb[nod<<1];
        }
    }

    void update(ll nod, ll l, ll r, ll poz)
    {
        if (l == r)
        {
            arb[nod] = 0;
            cout << l << ' ';
        }
        else
        {
            ll mid = (l + r) >> 1;
            if (poz <= arb[nod * 2])
            update(nod * 2, l, mid, poz);

            else
            update(nod * 2 + 1, mid + 1, r, poz - arb[nod * 2]);
            arb[nod] = arb[nod<<1|1] + arb[nod<<1];
        }
    }


int main()
{
    ll n, i, k;
    cin >> n >> k;
    build(1, 1, n);
    for (i = 1; i <= n; ++i) {
        if (k <= (n - i) * (n - i - 1) / 2)
            update(1, 1, n, 1);
        else
        {
            update(1, 1, n, 1 + k - (n - i) * (n - i - 1) / 2);
            k = (n - i) * (n - i - 1) / 2;
        }

    }
    return 0;
}