题解 | 牛牛的构造

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n, k;
    if (!(cin >> n >> k))
        return 0;

    if (n == 1) { // 只有一种排列，M = 0
        if (k == 0)
            cout << "1\n";
        else
            cout << "-1\n";
        return 0;
    }

    /* ---------- 最大可能答案 M ---------- */
    ll M = 0;
    ll maxPow = 0;
    while ((1LL << (maxPow + 1)) <= n - 1)
        ++maxPow; // floor(log2(n-1))
    for (ll d = 1; d <= n - 1; d <<= 1)
        M += n - d; // 所有 2 的幂次 d

    if (k > M) {
        cout << "-1\n";
        return 0;
    }

    ll R = M - k; // 需要隐藏的边数

    /* ---------- 选择将放置在前面的顶点 ---------- */
    vector<bool> front(n + 1,
                       false); // front[i] 为真  → i 将被插入到前面
    for (int i = 1; i <= n - 1 && R > 0; ++i) {
        int t = n - i; // t ≥ 1
        int deg = 0;
        if (t > 0)
            deg = 31 - __builtin_clz(t) + 1; // floor(log2(t)) + 1
        if ((ll)deg <= R) {
            front[i] = true;
            R -= deg;
        }
    }
    // R 现在必须为 0（根据证明它始终成立）

    /* ---------- 构建排列 ---------- */
    deque<int> dq;
    for (int v = int(n); v >= 1; --v) {
        if (front[v])
            dq.push_front(v);
        else
            dq.push_back(v);
    }

    /* ---------- 输出 ---------- */
    bool first = true;
    for (int x : dq) {
        if (!first)
            cout << ' ';
        cout << x;
        first = false;
    }
    cout << '\n';
    return 0;
}

考虑所有顶点为数字 1 … n 的图。当且仅当 y = x + 2^p（p ≥ 0）时，在两个顶点 x < y 之间连一条无向边。对于一条边 {x , y}，有两种可能性：

• 较大的顶点在排列中出现在前面——该边是正向的，并计入答案中；
• 较大的顶点在排列中出现在后面——该边是反向的，不计入答案中。

因此，只有这两个数中较小的那个决定了这条边的方向。

对于固定的顶点 v，可能的较大顶点为v+1 , v+2 , v+4 , v+8 , … ( ≤ n )

该顶点的度数为

deg(v) = 满足 v+2^p ≤ n 的 p ≥ 0 的个数
       = floor(log2( n – v )) + 1            ( 1 ≤ v ≤ n‑1 )

deg(v) = 0 当 v = n 时

如果在最终的排列中，v 被放置在所有已经放入的数字的右侧，那么它的所有邻居将位于左侧，每个邻居都会贡献一个有效数对——该顶点总共贡献 deg(v) 个有效数对。

如果 v 被放置在所有已存在的数字的左侧，那么它所有的关联边都将变为反向边——贡献为 0。

设

M = 正向边的最大可能数量
    （递减排列，即所有边均为正向）

M = Σd (n – d) （对所有 2 的幂 d 求和，d ≤ n‑1）

如果 k > M，则无解。

从最大值开始，我们可以关闭边。当我们决定将顶点 v 放在最前面时，它的 deg(v) 条正向边将变为反向。所有被移到前面的顶点的度数之和恰好等于从最大值中移除的正向边数量。R = M – k // 需要关闭的边数

我们需要选择一个顶点集 F，使得 Σ_{v∈F} deg(v) = R (1)

如果 F 已知，则答案通过以下构造方式轻易得到：将顶点 n, n‑1, … , 1 依次插入双端队列；如果一个顶点属于集合 F，则将其插入到前端，否则插入到后端。此构造恰好产生数量为 k 的正向边。

贪心决策：从序列的开头（i=1）开始，只要当前元素的预估贡献 deg 在预算 R 之内，就立即使用它。