結果

問題 No.3724 Domination
コンテスト
ユーザー nagi
提出日時 2026-09-19 18:23:14
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 3,875 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 61 ms
コンパイル使用メモリ 82,284 KB
実行使用メモリ 123,828 KB
最終ジャッジ日時 2026-09-19 18:23:25
合計ジャッジ時間 9,612 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge5_1
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点 20 % AC * 8
満点 80 % AC * 9 TLE * 1 -- * 42
合計 2.5 * 20% = 50 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import Counter


def solve():
    N = int(input())
    R = list(map(int, input().split()))
    C = list(map(int, input().split()))

    # R[v] = v を持つ行
    row = [0] * (N + 1)
    for i, v in enumerate(R):
        row[v] = i

    # C における各値の出現回数
    freq = Counter(C)

    # まず各行を R[i] で埋める
    A = [[R[i]] * N for i in range(N)]

    # ------------------------------------------------------------
    # 各列 j について、
    # C[j] を「唯一の最頻値」にするために C[j] を入れる。
    #
    # 行 i に C[j] を入れたとき、
    #   C[j] == R[i] なら、その行の R[i] の個数は減らない
    #   C[j] != R[i] なら、その行の R[i] を 1 個減らす
    #
    # そこで、各行について
    #   R[i] の個数 > 他のどの値の個数
    # を保つようにする。
    # ------------------------------------------------------------

    # 各行に「R[i] 以外の値」が何個入っているか
    # ではなく、各値がその行に何個入ったかを管理する。
    cnt = [Counter() for _ in range(N)]

    for i in range(N):
        cnt[i][R[i]] = N

    # 列ごとに C[j] を入れる場所を決める。
    #
    # なるべく C[j] 自身の行 row[C[j]] を使う。
    # このマスは元から C[j] なので、行条件を壊さない。
    #
    # 残りは、その値をまだあまり使っていない行に入れる。
    #
    # 各値 v について、その値を置く行を round-robin で回す。
    pos = [0] * (N + 1)

    # 各値 v の列一覧
    cols = [[] for _ in range(N + 1)]
    for j, v in enumerate(C):
        cols[v].append(j)

    # ------------------------------------------------------------
    # v の列には、まず v の本来の行を使う。
    # さらに他の行へ v を配置する。
    #
    # 「どの行にも同じ値を偏らせない」ように、
    # v ごとに行を巡回させる。
    # ------------------------------------------------------------

    for v in range(1, N + 1):
        if not cols[v]:
            continue

        base = row[v]

        # v の列それぞれについて、
        # v が入る行を決める。
        #
        # まず base 行は全部そのまま v。
        for j in cols[v]:
            A[base][j] = v

        # 残りの行については、
        # 各列に対して順番に v を入れていく。
        #
        # N//2 個程度まで入れれば、
        # 列の v を十分強くできる。
        need = N // 2

        p = 0
        for j in cols[v]:
            used = 0

            while used < need:
                i = (base + 1 + p) % N
                p += 1

                if i == base:
                    continue

                # この行で v が R[i] の個数以上にならないようにする
                if cnt[i][v] + 1 >= cnt[i][R[i]]:
                    continue

                A[i][j] = v
                cnt[i][v] += 1
                cnt[i][R[i]] -= 1
                used += 1

    # ------------------------------------------------------------
    # 最後に検証
    # ------------------------------------------------------------

    for i in range(N):
        c = Counter(A[i])
        m = max(c.values())

        if c[R[i]] != m:
            print(-1)
            return

        # 唯一の最頻値
        if sum(x == m for x in c.values()) != 1:
            print(-1)
            return

    for j in range(N):
        c = Counter(A[i][j] for i in range(N))
        m = max(c.values())

        if c[C[j]] != m:
            print(-1)
            return

        if sum(x == m for x in c.values()) != 1:
            print(-1)
            return

    for row_ in A:
        print(*row_)


T = int(input())

for _ in range(T):
    solve()
0