はじめに
問題リンク
「The Lost World: Jigsaw Puzzle and Detective」writerのvwxyzです。
昨年のA問題をさらに難しくした問題です。面倒なだけでそれほど難しくはない問題のはずなのですが、昨年と同様に取り組んだチーム自体が少なく、コンテスト中にACできたチームは0チームでした。
解説
回したり裏返したりして一致するピースを同一のものとして考えるとピースは$21$種類あります。
そのうち、すべての辺が普通の辺であるようなピースがジグゾーパズルに含まれていることはありません（ジグゾーパズルは$3$枚以上のピースから成るため）。
よって、実際にピースとして使われる可能性があるものは$20$種類に絞ることができます。
ジグゾーパズルの長方形の一方の一辺の長さがピースの一辺分である時、ジグゾーパズルを直線形であると呼ぶことにします。
直線形のジグゾーパズルに使われるピースは$(1,1,1,2)$、$(1,1,1,3)$、$(1,2,1,2)$、$(1,2,1,3)$、$(1,3,1,3)$の$5$種類（「直線タイプ」と呼ぶことにします）で、直線形でないジグゾーパズルに使われるピースはそれ以外の$15$種類（「非直線タイプ」と呼ぶことにします）なので、ジグゾーパズルが直線形かどうかは判別することができます。
残されたピースからわかる情報を調べる
一つのジグゾーパズルに使われるすべてのピースについて凸な辺と凹な辺の数は同じなので、残されたピースの凸な辺と凹な辺の数を数えることで、盗まれた$2$枚のピースに含まれる凸な辺と凹な辺の数の差を計算することができます。これを「凹凸辺差」と呼ぶことにします。
同様にして、盗まれた$2$枚のピースに含まれる凸な辺と凹な辺でそれぞれ普通の辺と隣り合うようなものの数の差を計算することもできます。これを「普通と接する凹凸辺差」と呼ぶことにします。
また、ジグゾーパズルが非直線形の場合、普通の辺がちょうど$2$辺含まれていてそれらが隣り合っているようなピース（「角ピース」と呼ぶことにします）はちょうど$4$つあるはずなので、残されたピースの中に角ピースが何枚あるかを数えることで、盗まれた$2$枚のピースのうち角ピースの枚数（ジグゾーパズルが直線形の場合は$0$とする）を計算することができます。
答えを一意に絞る
直線タイプ同士、または非直線同士の$2$枚のピースの組は$135$通りあり、それぞれについて
(直線タイプかどうか,凹凸辺差,普通と接する凹凸辺差,角ピースの数,条件を満たすような折り目の数,共通変数)
を（プログラムを用いて）計算すると相異なっていることがわかるので、これで答えを一意に絞れることがわかります。
まとめ
事前に前計算をしておくことで、盗まれた$2$枚のピースを$O(\sum N)$で絞り込めることがわかりました。
実装
from collections import defaultdict
import sys
readline=sys.stdin.readline
piece=[(1,1,1,2), (1,1,1,3), (1,1,2,2), (1,1,2,3), (1,1,3,3), (1,2,1,2), (1,2,1,3), (1,2,2,2), (1,2,2,3), (1,2,3,2), (1,2,3,3), (1,3,1,3), (1,3,2,3), (1,3,3,3), (2,2,2,2), (2,2,2,3), (2,2,3,3), (2,3,2,3), (2,3,3,3), (3,3,3,3)]
piece_pair=defaultdict(list)
for i in range(20):
for j in range(i,20):
if (piece[i][0]==piece[i][2]==1 or piece[i][1]==piece[i][3]==1)!=(piece[j][0]==piece[j][2]==1 or piece[j][1]==piece[j][3]==1):
continue
is_line=(piece[i][0]==piece[i][2]==1 or piece[i][1]==piece[i][3]==1)
cnt1=piece[i].count(1)+piece[j].count(1)
cnt23=piece[i].count(2)+piece[j].count(2)-piece[i].count(3)-piece[j].count(3)
if is_line:
cnt12=0
cnt13=(piece[i].count(1)==3)+(piece[j].count(1)==3)
else:
cnt12=sum((piece[i][k]==piece[i][(k+1)%4]==1)+(piece[j][k]==piece[j][(k+1)%4]==1) for k in range(4))
cnt13=0
cnt231=0
for k in range(4):
if piece[i][(k-1)%4]==1 or piece[i][(k+1)%4]==1:
if piece[i][k]==2:
cnt231+=1
elif piece[i][k]==3:
cnt231-=1
if piece[j][(k-1)%4]==1 or piece[j][(k+1)%4]==1:
if piece[j][k]==2:
cnt231+=1
elif piece[j][k]==3:
cnt231-=1
s=0
s+=(piece[i][0]==piece[i][2])+(piece[i][1]==piece[i][3])+(piece[i][0]==piece[i][1] and piece[i][2]==piece[i][3])+(piece[i][0]==piece[i][3] and piece[i][1]==piece[i][2])
s+=(piece[j][0]==piece[j][2])+(piece[j][1]==piece[j][3])+(piece[j][0]==piece[j][1] and piece[j][2]==piece[j][3])+(piece[j][0]==piece[j][3] and piece[j][1]==piece[j][2])
c=sum(min(piece[i].count(k),piece[j].count(k)) for k in range(1,4))
piece_pair[(is_line,cnt23,cnt12,cnt13,cnt231,s,c)].append((piece[i],piece[j]))
for lst in piece_pair.values():
assert len(lst)==1
def solve(S,C,P):
cnt23,cnt12,cnt13,cnt231=0,4,2,0
for p in P:
is_line=(p[0]==p[2]==1) or (p[1]==p[3]==1)
if is_line:
if p.count(1)==3:
cnt13-=1
else:
if p.count(1)==2:
cnt12-=1
cnt23-=p.count(2)-p.count(3)
for k in range(4):
if p[(k-1)%4]==1 or p[(k+1)%4]==1:
if p[k]==2:
cnt231-=1
elif p[k]==3:
cnt231+=1
if is_line:
cnt12=0
else:
cnt13=0
return piece_pair[(is_line,cnt23,cnt12,cnt13,cnt231,S,C)][0]
T=int(readline())
for _ in range(T):
N,S,C=map(int,readline().split())
P=[list(map(int,readline().split())) for _ in range(N)]
ans=solve(S,C,P)
print(*ans[0])
print(*ans[1])