結果

問題 No.3211 NAND Oracle
コンテスト
ユーザー srjywrdnprkt
提出日時 2025-07-28 17:53:06
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 291 ms / 2,000 ms
コード長 2,233 bytes
コンパイル時間 3,313 ms
コンパイル使用メモリ 288,608 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-07-28 17:53:15
合計ジャッジ時間 9,156 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder/modint>

using namespace std;
//using namespace atcoder;
using ll = long long;
//using mint = modint998244353;

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    /*
       (1,2)
       (1,2)
       (3,4)
       (4,5)
       (4,5)
       (6,7)繰り返し
       1 2 3 4 5 6 7

       1 1 0 0 1 1 1
       1 0 1 1 0 1 1 
       0 1 1 1 0 1 1 
       0 0 1 1 0 1 1
       Q>=5のときは5以下にできる。
       1 1 0 0 
       1 0 1 1
       0 1 1
       0 0 1 
    */

    int Q, K;
    cin >> Q >> K;

    if (Q <= 5){
        vector<pair<int, int>> v;
        vector<vector<pair<int, int>>> w;
        auto dfs=[&](auto self, int now=2)->void{
            if (now == Q+2){
                w.push_back(v);
                return;
            }
            for (int i=0; i<now; i++){
                for (int j=i+1; j<now; j++){
                    v.push_back({i, j});
                    self(self, now+1);
                    v.pop_back();
                }
            }
        };
        dfs(dfs);
        int mi = 1e9;
        vector<pair<int, int>> ami;
        for (auto &ww : w){
            int mx=-1e9;
            for (int i=0; i<2; i++){
                for (int j=0; j<2; j++){
                    vector<int> vv={i,j};
                    for (auto [a, b] : ww){
                        vv.push_back(!(vv[a]&vv[b]));
                    }
                    int sm=0;
                    for (auto vvv : vv) sm += vvv;
                    mx = max(mx, sm);
                }
            }
            if (mx < mi){
                mi = mx;
                ami = ww;
            }
        }
        if (mi > K) cout << "No" << endl;
        else{
            cout << "Yes" << endl;
            for (auto [a, b] : ami) cout << a+1 << " " << b+1 << endl;
        }
    }
    else{
        if (K <= 4) cout << "No" << endl;
        else{
            cout << "Yes" << endl;
            cout << "1 2" << endl;
            cout << "1 2" << endl;
            cout << "3 4" << endl;
            cout << "4 5" << endl;
            cout << "4 5" << endl;
            for (int i=0; i<Q-5; i++) cout << "6 7" << endl;
        }
    }

    return 0;
}
0