結果

問題 No.470 Inverse S+T Problem
ユーザー mkawa2mkawa2
提出日時 2020-05-01 11:37:18
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 62 ms / 2,000 ms
コード長 3,206 bytes
コンパイル時間 106 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 16,384 KB
最終ジャッジ日時 2024-06-01 23:02:46
合計ジャッジ時間 2,160 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 28 ms
11,008 KB
testcase_01 AC 31 ms
11,008 KB
testcase_02 AC 28 ms
10,880 KB
testcase_03 AC 30 ms
11,008 KB
testcase_04 AC 26 ms
11,008 KB
testcase_05 AC 27 ms
10,880 KB
testcase_06 AC 61 ms
16,384 KB
testcase_07 AC 61 ms
16,384 KB
testcase_08 AC 62 ms
16,384 KB
testcase_09 AC 28 ms
10,880 KB
testcase_10 AC 28 ms
11,136 KB
testcase_11 AC 27 ms
11,008 KB
testcase_12 AC 27 ms
10,880 KB
testcase_13 AC 27 ms
11,008 KB
testcase_14 AC 27 ms
10,880 KB
testcase_15 AC 28 ms
11,008 KB
testcase_16 AC 26 ms
11,008 KB
testcase_17 AC 27 ms
11,136 KB
testcase_18 AC 27 ms
11,008 KB
testcase_19 AC 28 ms
10,880 KB
testcase_20 AC 27 ms
11,008 KB
testcase_21 AC 27 ms
10,880 KB
testcase_22 AC 27 ms
11,008 KB
testcase_23 AC 28 ms
11,008 KB
testcase_24 AC 28 ms
10,880 KB
testcase_25 AC 26 ms
11,136 KB
testcase_26 AC 27 ms
11,008 KB
testcase_27 AC 26 ms
11,008 KB
testcase_28 AC 32 ms
11,520 KB
testcase_29 AC 27 ms
10,880 KB
testcase_30 AC 28 ms
11,136 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#import matplotlib.pyplot as plt
#import networkx as nx
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

# 2-SATらしい
def main():
    n=II()
    ss=[SI() for _ in range(n)]

    # 1文字の文字列が大小アルファベットの26*2=52種類しかないので、それより多いと無理
    if n>52:
        print("Impossible")
        exit()

    # 「i番目の文字列を左で切ること」を頂点iとする
    # 「i番目の文字列を右で切ること」を頂点n+iとする
    # 分割してできる文字列ごとに頂点をまとめる
    cnt=defaultdict(list)
    for i,s in enumerate(ss):
        cnt[s[0]].append(i)
        cnt[s[1:]].append(i)
        cnt[s[2]].append(i+n)
        cnt[s[:2]].append(i+n)
    #print(cnt)

    # 同じ文字列ができる頂点のうち、使えるのは１つだけ
    # 例えば"ab":[2,3,5]であれば、頂点2が"ab"を使えば頂点3,5は使えない
    # つまり、頂点2を使う場合は、頂点3,5の逆の切り方（+nか-nしたもの）を選ばなくてはいけない
    # よって、2→3,5の逆、3→2,5の逆、5→2,3の逆に辺を張ればよい
    # 強連結成分分解(SCC)のために逆辺(ot)も持っておく
    #G=nx.DiGraph()
    #G.add_edges_from(range(2*n))
    to=[[] for _ in range(n*2)]
    ot=[[] for _ in range(n*2)]
    for uu in cnt.values():
        for u in uu:
            for v in uu:
                if u==v:continue
                v=(v+n)%(2*n)
                if u==v:continue
                to[u].append(v)
                ot[v].append(u)
                #G.add_edge(u,v)
    #print(to)

    # こっからSCC
    # トポロジカル順を作る
    def dfs(u):
        for v in to[u]:
            if fin[v]:continue
            fin[v]=True
            dfs(v)
        top.append(u)

    top=[]
    fin=[False]*(2*n)
    for u in range(2*n):
        if fin[u]:continue
        fin[u]=True
        dfs(u)
    top.reverse()
    #print(top)

    # 逆辺を辿って強結合を探す
    def rdfs(u,k):
        for v in ot[u]:
            if com[v]!=-1:continue
            com[v]=k
            rdfs(v,k)

    com=[-1]*(2*n)
    k=0
    for u in top:
        if com[u]!=-1:continue
        com[u]=k
        rdfs(u,k)
        k+=1
    #print(com)

    # 同じ文字列の異なる切り方(頂点uとu+n)が強連結になっていたら、解なし
    for u in range(n):
        if com[u]==com[u+n]:
            print("Impossible")
            exit()

    # 各頂点のトポロジカル順をチェック
    rank=[0]*(2*n)
    for r,u in enumerate(top):rank[u]=r

    # 各文字列について、トポロジカル順が後の切り方を選ぶ
    for u,s in enumerate(ss):
        if rank[u]>rank[u+n]:print(s[0],s[1:])
        else:print(s[:2],s[2])

    #nx.draw_networkx(G)
    #plt.show()

main()
0