P11277 世界沉睡童话

我们猜测数据范围内一定有解。

若 k \ge n-1，则我们可以在开头放一个 1，令 k \gets k-(n-1)，n \gets n-1，然后最终归约到 k<n-1 的子问题。

我们大胆猜测 k<n-1 时答案一定可以形如若干值域 \in [n,2n-1] 的连续段，每个连续段的值互不相同，它们的贡献即是每个连续段长度 \binom{\text{len}}{2} 求和。

接下来我们直接贪心地填这些连续段，每次选择一个长度 \text{len} \le n \land \binom{\text{len}}{2} \le k 的最大的 \text{len} 填上一个长度为 \text{len} 的连续段。感性上这是很优的，交一发发现过了。其实证明也很简单，归纳一下就全对了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n; ll k;
vector<int> ans;
int main() {
    scanf("%d%lld", &n, &k);
    while (n && k >= n - 1) {
        printf("1 ");
        k -= n - 1, n--;
    }
    int n0 = n;
    for (int i = n; i >= 1; i--) {
        while (k >= 1ll * i * (i - 1) / 2 && n >= i) {
            k -= 1ll * i * (i - 1) / 2, n -= i;
            ans.push_back(i);
        }
    }
    for (int i = 0; i < ans.size(); i++) {
        for (int j = 1; j <= ans[i]; j++) printf("%d ", i + n0);
    }
    return 0;
}