結果
問題 |
No.3211 NAND Oracle
|
ユーザー |
![]() |
提出日時 | 2025-07-25 22:33:42 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,657 bytes |
コンパイル時間 | 1,775 ms |
コンパイル使用メモリ | 139,220 KB |
実行使用メモリ | 8,064 KB |
最終ジャッジ日時 | 2025-07-25 22:33:51 |
合計ジャッジ時間 | 5,818 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 WA * 5 |
ソースコード
#include <iostream> #include <iomanip> #include <cassert> #include <vector> #include <algorithm> #include <utility> #include <numeric> #include <tuple> #include <ranges> namespace ranges = std::ranges; namespace views = std::views; // #include "Src/Number/IntegerDivision.hpp" // #include "Src/Utility/BinarySearch.hpp" // #include "Src/Sequence/CompressedSequence.hpp" // #include "Src/Sequence/RunLengthEncoding.hpp" // #include "Src/Algebra/Group/AdditiveGroup.hpp" // #include "Src/DataStructure/FenwickTree/FenwickTree.hpp" // #include "Src/DataStructure/SegmentTree/SegmentTree.hpp" // #include "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp" // using namespace zawa; // #include "atcoder/modint" // using mint = atcoder::modint998244353; // using namespace std; int Q, K; int nand(int a, int b) { return (a == 1 and b == 1 ? 0 : 1); } int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin >> Q >> K; vector<vector<int>> A(4); A[0] = {0, 0}; A[1] = {0, 1}; A[2] = {1, 0}; A[3] = {1, 1}; vector<pair<int, int>> ans; auto op = [&](int p, int q) { ans.push_back({p + 1, q + 1}); for (int k = 0 ; k < 4 ; k++) { A[k].push_back(nand(A[k][p], A[k][q])); } }; if (Q >= 4) { // 10 // (1,2)(1,2)(3,4)(3,5)(3,5)(6,7)(6,7)(6,7) // (1,2)(1,2)(3,4)(3,5)(4,5)(6,7)(6,7)(6,7) // (1,2)(1,2)(3,4)(4,5)(3,5)(6,7)(6,7)(6,7) // (1,2)(1,2)(3,4)(4,5)(4,5)(6,7)(6,7)(6,7) // (1,2)(1,3)(2,4)(2,5)(2,5)(6,7)(6,7)(6,7) // (1,2)(2,3)(1,4)(1,5)(1,5)(6,7)(6,7)(6,7) // 5 op(0, 1); op(0, 1); op(2, 3); op(2, 4); op(2, 4); for (int i = 0 ; i < 200000 ; i++) { op(5, 6); } } else { auto eval = [&]() -> int { int res = 0; for (const vector<int>& a : A) res = max(res, accumulate(a.begin(), a.begin() + Q + 2, 0)); return res; }; int val = (int)1e9; vector<vector<pair<int, int>>> oks; vector<pair<int, int>> cur; auto op = [&](int p, int q) -> void { cur.push_back({p + 1, q + 1}); for (int i = 0 ; i < 4 ; i++) { A[i].push_back(nand(A[i][p], A[i][q])); } }; auto dfs = [&](auto dfs) -> void { if (ssize(A[0]) == 2 + Q) { int v = eval(); if (val > v) { oks.clear(); oks.push_back(cur); val = v; } else if (val == v) { oks.push_back(cur); } } else { for (int i = 0 ; i < ssize(A[0]) ; i++) { for (int j = i + 1 ; j < ssize(A[0]) ; j++) { op(i, j); dfs(dfs); for (int k = 0 ; k < 4 ; k++) A[k].pop_back(); cur.pop_back(); } } } }; dfs(dfs); ans = oks[0]; for (auto [i, j] : ans | views::take(Q)) { for (vector<int>& a : A) { a.push_back(nand(a[i], a[j])); } } } int sum = 0; for (const vector<int>& a : A) { // for (int x : a | views::take(Q)) cout << x << ' '; // cout << endl; sum = max(sum, accumulate(a.begin(), a.begin() + Q, 0)); } if (sum <= K) { cout << "Yes\n"; for (auto [i, j] : ans | views::take(Q)) cout << i << ' ' << j << '\n'; } else { cout << "No\n"; } }