H - 卓球 (Table Tennis) Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

JOI 国で卓球の大会が行われた.大会には 1 から N までの番号が付けられている N 匹のビーバーが出場し,総当たりのリーグ戦が行われた.

あなたはビ太郎から大会の試合結果について以下の情報を聞いた.

  • どの試合も引き分けではなかった.
  • 三すくみとなるような 3 匹のビーバーの選び方はちょうど M 通りであった.ただし,3 匹のビーバー i, j, k (1 \leqq i < j < k \leqq N) が三すくみであるとは,以下の 2 つの条件のうちちょうど 1 つが成り立つことをいう.
    • ビーバー i がビーバー j に勝利し,ビーバー j がビーバー k に勝利し,ビーバー k がビーバー i に勝利した.
    • ビーバー i がビーバー k に勝利し,ビーバー k がビーバー j に勝利し,ビーバー j がビーバー i に勝利した.

あなたはビ太郎から聞いた情報が正確か分からないため,聞いた情報に合致するような大会の試合結果が存在するか考えることにした.

ビ太郎から聞いた情報が与えられたとき,情報に合致する試合結果が存在するか判定し,もし存在するならばそのような試合結果を 1 つ求めるプログラムを作成せよ.


入力

1 つのテストケースは Q 個のシナリオからなり,シナリオには 1 から Q までの番号が付けられている.各シナリオに対して,以下の値が定められている.

  • 大会に参加したビーバーの数 N.
  • 三すくみとなるような 3 匹のビーバーの選び方 M.

ここで,入力は以下の形式で標準入力から与えられる.

Q
(シナリオ 1 に対する入力)
(シナリオ 2 に対する入力)
\vdots
(シナリオ Q に対する入力)

また,それぞれのシナリオに対する入力は,以下の形式で与えられる.

N M

出力

標準出力に,シナリオ 1, 2, \ldots, Q の順に以下の形式で出力せよ.

あるシナリオについて,情報に合致する試合結果が存在する場合,以下の形式で出力せよ.

Yes
S_2
S_3
\vdots
S_N

ここで,S_i (2 \leqq i \leqq N) は 0 または 1 からなる i - 1 文字の文字列である.S_i の j 文字目 (1 \leqq j \leqq i - 1) が 0 のときビーバー i がビーバー j に敗北したことを,1 のときビーバー i がビーバー j に勝利したことを示す.情報に合致する試合結果が複数存在する場合は,そのうちどれを出力してもよい.

あるシナリオについて,情報に合致する試合結果が存在しない場合,No と出力せよ.


制約

  • 1 \leqq Q.
  • 3 \leqq N \leqq 5\,000.
  • 0 \leqq M \leqq \dfrac{1}{6}N(N - 1)(N - 2).
  • Q 個のシナリオにおける N の値の合計は 5\,000 以下である.
  • 入力される値はすべて整数である.

小課題

  1. (5 点) M = 0.
  2. (12 点) M \leqq N - 2.
  3. (15 点) M \leqq \dfrac14(N - 1)^2.
  4. (10 点) Q 個のシナリオにおける N の値の合計は 7 以下である.
  5. (23 点) Q 個のシナリオにおける N の値の合計は 20 以下である.
  6. (19 点) Q 個のシナリオにおける N の値の合計は 150 以下である.
  7. (8 点) Q 個のシナリオにおける N の値の合計は 600 以下である.
  8. (8 点) 追加の制約はない.

入力例 1

2
3 1
4 4

出力例 1

Yes
0
10
No

この入力例は Q = 2 個のシナリオからなる.

この出力例におけるシナリオ 1 の試合結果ではビーバー 1 がビーバー 2 に勝利し,ビーバー 2 がビーバー 3 に勝利し,ビーバー 3 がビーバー 1 に勝利した.したがって,3 匹のビーバー 1, 2, 3 は三すくみである.この他に 3 匹のビーバーを選ぶ方法はないので,三すくみとなるような 3 匹のビーバーの選び方はちょうど 1 通りである.

シナリオ 1 に対応する出力として,他に以下のようなものが考えられる.

Yes
1
01

シナリオ 2 では情報に合致する試合結果は存在しない.したがって,No と出力する.

この入力例は小課題 4, 5, 6, 7, 8 の制約を満たす.


入力例 2

1
5 3

出力例 2

Yes
0
11
001
0101

この出力例におけるシナリオ 1 の試合結果ではビーバー 1 がビーバー 4 に勝利し,ビーバー 4 がビーバー 3 に勝利し,ビーバー 3 がビーバー 1 に勝利した.したがって,3 匹のビーバー 1, 3, 4 は三すくみである.この他に三すくみとなるような 3 匹のビーバーの選び方として,ビーバー 2, 3, 4 を選ぶ方法とビーバー 3, 4, 5 を選ぶ方法がある.したがって,三すくみとなるような 3 匹のビーバーの選び方はちょうど 3 通りである.

この入力例は小課題 2, 3, 4, 5, 6, 7, 8 の制約を満たす.


Source Name

JOIG 2023/2024 春季トレーニング Contest Day2