Cod sursa(job #2649271)

Utilizator DavidLDavid Lauran DavidL Data 13 septembrie 2020 21:44:08
Problema Farfurii Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fi("farfurii.in");
ofstream fo("farfurii.out");

typedef long long ll;
const int NMAX = 1e5 + 5;

int n, k;
ll aib[NMAX];
bool luat[NMAX];

inline int lsb(int x) {
    return x & (-x);
}

void update(int poz, int val) {
    for (; poz <= n; poz += lsb(poz))
        aib[poz] += val;
}

ll query(int poz) {
    ll ret = 0;
    for (; poz; poz -= lsb(poz))
        ret += aib[poz];
    return ret;
}

int main()
{
    fi >> n >> k;

    for (int i = 1; i <= n; i++) {
        update(i, i - 1);
        update(i + 1, -(i - 1));
    }

    ll curr = 0;
    for (int i = 1; i <= n; i++) {
        // primul x a.i. maiMic(X) >= k-curr-(n-i-1)(n-i)/2
        ll ceva = k - curr - 1LL * (n - i - 1) * (n - i) / 2;

        int st = 1;
        for (int b = 16; b >= 0; b--) {
            if (st + (1 << b) <= n && query(st + (1 << b)) < ceva)
                st += (1 << b);
        }
        if (query(st) < ceva)
            st++;

        while (luat[st]) //eh...
            st++;

        update(st + 1, -1);

        fo << st << " ";
        curr += query(st);
        luat[st] = 1;
    }

    return 0;
}