結果

問題 No.3585 Make Ends Meet (Easy)
コンテスト
ユーザー Lidelie
提出日時 2026-07-11 00:06:49
言語 C++23
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,315 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,178 ms
コンパイル使用メモリ 344,908 KB
実行使用メモリ 9,388 KB
最終ジャッジ日時 2026-07-11 00:06:55
合計ジャッジ時間 4,260 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 45 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

ll binomial_coefficient(ll n,ll k){
    if(n<k)return 0;
    ll res = 1;
    if(k>n/2)k = n-k;
    for(ll i = 1;i<=k;i++)
    res = (n+1-i)*res/i;
    return res;
}
int main(){
    ll N,M,K;
    cin >> N >> M >> K;
    ll C = N - (K + 1);
    
    if(! (N*(N-1)/2 - (min(K,3ll)*C + K + binomial_coefficient(C,2)) <= M && M <= N*(N-1)/2 - K)){
        cout << "No\n";
        exit(0);
    }
    ll put = N*(N-1)/2 - M;
    vector<pair<ll,ll>> E;
    for(ll i = 0;i<K;i++){
        if(i == K-1)E.emplace_back(i,N-1);
        else E.emplace_back(i,i+1);
        put--;
    }
    for(ll s = 0;s<=min({N,K-1,2ll}) && put;s++){
        for(ll j = K;j<N-1 && put;j++){
            E.emplace_back(s,j);
            put--;
        }
    }
    if(K == 2) for(ll j = K;j<N-1 && put; j++){
        E.emplace_back(N-1,j);
        put--;
    }
    for(ll i = K;i<N-1 && put; i++){
        for(ll j = i+1;j<N-1 && put; j++){
            E.emplace_back(i,j);
            put--;
        }
    }
    for(auto&[a,b] : E){
        if(a>b)swap(a,b);
    }
    set<pair<ll,ll>> S;
    for(ll i = 0;i<N;i++) for(ll j = i+1;j<N;j++) S.emplace(i,j);
    for(auto [a,b] : E) S.erase({a,b});
    cout << "Yes\n";
    for(auto [a,b] : S) cout << a+1 << ' ' << b+1 << '\n';
}
0