Luogu

LOJ

分析

感觉同步赛上的我就是个 SB /kk

下面没有证明。

为了方便我们把所有 $d_i$ 从小到大排序。

先考虑 $m=n-1$ 的情况。此时显然会有 $d_1< k,d_1+d_n\geq k$，于是我们可以把 $d_1$ 和 $d_n$ 放在一起做一道菜，这样子变成了 $n'=n-1,m'=m-1$ 的情况。所以我们只要每次把最少的和最多的拿出来即可。

再考虑 $m\geq n$ 的情况。此时显然会有 $d_n\geq k$，于是我们可以拿 $d_n$ 单独做一道菜，这样子就转化为了 $n'=n/n-1,m'=m-1$ 的情况（前者是 $d_n=k$，后者是 $d_n>k$）。如果到最后都只出现了第一种情况，说 明 $n=m$ 且 $d_i=k$，显然可以构造出解；否则最后一定可以转化为 $m=n-1$ 的情况。

最后考虑 $m=n-2$ 的情况。可以发现，如果我们能把集合划分成两个部分 $S$ 和 $T$，满足 $\sum_{i\in S}d_i=(|S|-1)k$，则可以转化为两个 $m=n-1$ 的部分解决，否则无解。我们把式子转化为 $\sum_{i\in S}(d_i-k)=-k$，于是相当于 01 背包，std::bitset 优化一下即可做到 $\mathcal{O}(\frac{n^2k}{\omega})$。

实现时可以用 std::multiset 来维护 $d_i$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define mp make_pair
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500+10,M=5000+10;

int n,m,k,d[N];

void solve(int n,int m,multiset<pair<int,int>> S,vector<pair<int,int>> ans[]) {
    for (int i=1;i<=m;++i) ans[i].clear();
    int cnt=0;
    while (m>S.size()-1) {
        auto x=*S.rbegin(); S.erase(--S.end());
        ans[++cnt].emplace_back(mp(x.second,k));
        x.first-=k; if (x.first) S.insert(x);
        --m;
    }
    while (m) {
        auto x=*S.begin(),y=*S.rbegin();
        S.erase(S.begin()),S.erase(--S.end());
        ans[++cnt].emplace_back(mp(x.second,x.first));
        ans[cnt].emplace_back(mp(y.second,k-x.first));
        y.first-=k-x.first; if (y.first) S.insert(y);
        --m;
    }
}

namespace Yui {
    vector<pair<int,int>> ans[M];
    multiset<pair<int,int>> S;
    void main() {
        S.clear();
        for (int i=1;i<=n;++i) S.insert(mp(d[i],i));
        solve(n,m,S,ans);
        for (int i=1;i<=m;++i) {
            for (auto j:ans[i]) printf("%d %d ",j.first,j.second);
            puts("");
        }
    }
}

namespace Ui {
    vector<pair<int,int>> ansx[M],ansy[M];
    multiset<pair<int,int>> S,T;
    bitset<5000001> dp[N];
    void main() {
        for (int i=0;i<=n;++i) dp[i].reset();
        dp[0][2500000]=1;
        for (int i=1;i<=n;++i) {
            if (d[i]>k) dp[i]=dp[i-1]|(dp[i-1]<<(d[i]-k));
            else dp[i]=dp[i-1]|(dp[i-1]>>(k-d[i]));
        }
        if (!dp[n][2500000-k]) { puts("-1"); return; }
        S.clear(),T.clear();
        for (int i=n,x=2500000-k;i;--i) {
            if (x-d[i]+k>=0&&x-d[i]+k<=5000000&&dp[i-1][x-d[i]+k])
                S.insert(mp(d[i],i)),x-=d[i]-k;
            else T.insert(mp(d[i],i));
        }
        solve(S.size(),S.size()-1,S,ansx);
        solve(T.size(),T.size()-1,T,ansy);
        for (int i=1;i<=S.size()-1;++i) {
            for (auto j:ansx[i]) printf("%d %d ",j.first,j.second);
            puts("");
        }
        for (int i=1;i<=T.size()-1;++i) {
            for (auto j:ansy[i]) printf("%d %d ",j.first,j.second);
            puts("");
        }
    }
}

int main() {
    int T=read();
    while (T--) {
        n=read(),m=read(),k=read();
        for (int i=1;i<=n;++i) d[i]=read();
        if (m==n-2) Ui::main();
        else Yui::main();
    }
    return 0;
}