結果

問題 No.3211 NAND Oracle
ユーザー tnakao0123
提出日時 2025-07-28 09:12:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 7 ms / 2,000 ms
コード長 1,771 bytes
コンパイル時間 452 ms
コンパイル使用メモリ 63,260 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-07-28 09:12:09
合計ジャッジ時間 4,408 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:59:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   59 |   scanf("%d%d", &qn, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 3211.cc:  No.3211 NAND Oracle - yukicoder
 */

#include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

/* constant */

const int MAX_N = 200000;

/* typedef */

using vi = vector<int>;
using pii = pair<int,int>;
using vpii = vector<pii>;

/* global variables */

/* subroutines */

void rec(int qn, int k, vi avs[], int ss[], vpii &ops) {
  if (ops.size() >= qn) {
    puts("Yes");
    for (auto [i, j]: ops) printf("%d %d\n", i + 1, j + 1);
    exit(0);
  }

  int n = ops.size() + 2;
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++) {
      int maxs = 0, ss1[4];
      for (int l = 0; l < 4; l++) {
	int al = (avs[l][i] & avs[l][j]) ^ 1;
	ss1[l] = ss[l] + al;
	maxs = max(maxs, ss1[l]);
	avs[l].push_back(al);
      }

      if (maxs <= k) {
	ops.push_back({i, j});
	rec(qn, k, avs, ss1, ops);
	ops.pop_back();
      }

      for (int l = 0; l < 4; l++) avs[l].pop_back();
    }
}

/* main */

int main() {
  int qn, k;
  scanf("%d%d", &qn, &k);

  //  1,2  2,3   1,4    1,5     1,5      6,7
  // 00->001->0011->00111->001111->0011111->00111110->..
  // 01->011->0110->01101->011011->0110111->01101110->..
  // 10->101->1011->10110->101101->1011011->10110110->..
  // 11->110->1101->11010->110101->1101011->11010110->..

  if (k >= 5) {
    puts("Yes");
    for (int i = 0; i < qn; i++)
      switch (i) {
      case 0: puts("1 2"); break;
      case 1: puts("2 3"); break;
      case 2: puts("1 4"); break;
      case 3: puts("1 5"); break;
      case 4: puts("1 5"); break;
      default: puts("6 7");
      }
    return 0;
  }

  vi avs[4] = {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
  int ss[4] = {0, 1, 1, 2};
  vpii ops;
  
  rec(qn, k, avs, ss, ops);

  puts("No");
  
  return 0;
}
0