結果

問題 No.470 Inverse S+T Problem
ユーザー NoneNone
提出日時 2021-05-25 13:17:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 337 ms / 2,000 ms
コード長 5,443 bytes
コンパイル時間 194 ms
コンパイル使用メモリ 82,848 KB
実行使用メモリ 125,360 KB
最終ジャッジ日時 2024-06-01 23:07:59
合計ジャッジ時間 2,850 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
53,120 KB
testcase_01 AC 38 ms
52,736 KB
testcase_02 AC 36 ms
53,120 KB
testcase_03 AC 37 ms
53,120 KB
testcase_04 AC 36 ms
53,248 KB
testcase_05 AC 35 ms
52,864 KB
testcase_06 AC 37 ms
52,992 KB
testcase_07 AC 36 ms
52,864 KB
testcase_08 AC 36 ms
52,736 KB
testcase_09 AC 34 ms
53,504 KB
testcase_10 AC 37 ms
54,400 KB
testcase_11 AC 45 ms
61,824 KB
testcase_12 AC 37 ms
53,120 KB
testcase_13 AC 40 ms
54,272 KB
testcase_14 AC 46 ms
62,080 KB
testcase_15 AC 40 ms
54,496 KB
testcase_16 AC 38 ms
53,376 KB
testcase_17 AC 38 ms
53,888 KB
testcase_18 AC 38 ms
54,016 KB
testcase_19 AC 39 ms
54,172 KB
testcase_20 AC 37 ms
53,376 KB
testcase_21 AC 44 ms
61,184 KB
testcase_22 AC 46 ms
61,824 KB
testcase_23 AC 46 ms
62,048 KB
testcase_24 AC 44 ms
62,080 KB
testcase_25 AC 45 ms
61,056 KB
testcase_26 AC 44 ms
61,952 KB
testcase_27 AC 46 ms
61,312 KB
testcase_28 AC 36 ms
53,248 KB
testcase_29 AC 337 ms
125,360 KB
testcase_30 AC 36 ms
53,416 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class CSR:
    def __init__(self, n: int, edges: list):
        self.start = [0] * (n + 1)
        self.elist = [0] * len(edges)
        for e in edges:
            self.start[e[0] + 1] += 1

        for i in range(1, n + 1):
            self.start[i] += self.start[i - 1]

        counter = self.start[::]  # copy
        for e in edges:
            self.elist[counter[e[0]]] = e[1]
            counter[e[0]] += 1

class SccGraph:
    def __init__(self, n: int = 0):
        self.__n = n
        self.__edges = []

    def __len__(self):
        return self.__n

    def add_edge(self, s: int, t: int):
        assert 0 <= s < self.__n and 0 <= t < self.__n
        self.__edges.append([s, t])

    def scc_ids(self):
        g = CSR(self.__n, self.__edges)
        now_ord = group_num = 0
        visited = []
        low = [0] * self.__n
        order = [-1] * self.__n
        ids = [0] * self.__n
        parent = [-1] * self.__n
        for root in range(self.__n):
            if order[root] == -1:
                stack = [root, root]
                while stack:
                    v = stack.pop()
                    if order[v] == -1:
                        visited.append(v)
                        low[v] = order[v] = now_ord
                        now_ord += 1
                        for i in range(g.start[v], g.start[v + 1]):
                            t = g.elist[i]
                            if order[t] == -1:
                                stack += [t, t]
                                parent[t] = v
                            else:
                                low[v] = min(low[v], order[t])

                    else:
                        if low[v] == order[v]:
                            while True:
                                u = visited.pop()
                                order[u] = self.__n
                                ids[u] = group_num
                                if u == v:
                                    break

                            group_num += 1

                        if parent[v] != -1:
                            low[parent[v]] = min(low[parent[v]], low[v])

        for i, x in enumerate(ids):
            ids[i] = group_num - 1 - x

        return group_num, ids

    def scc(self):
        """
        強連結成分のリストを返す。この時、リストはトポロジカルソートされている
        [[強連結成分のリスト], [強連結成分のリスト], ...]
        """
        group_num, ids = self.scc_ids()
        counts = [0] * group_num
        for x in ids:
            counts[x] += 1

        groups = [[] for _ in range(group_num)]
        for i, x in enumerate(ids):
            groups[x].append(i)

        return groups

class TwoSAT():
    def __init__(self, n):
        self.n = n
        self.res = [0]*self.n
        self.scc = SccGraph(2*n)

    def add_clause(self, i, f, j, g):
        # assert 0 <= i < self.n
        # assert 0 <= j < self.n
        self.scc.add_edge(2*i + (not f), 2*j + g)
        self.scc.add_edge(2*j + (not g), 2*i + f)

    def add_or(self, i, f, j, g):
        self.add_clause(i, f, j, g)

    def add_xor(self, i, f, j, g):
        self.add_clause(i, f, j, g)
        self.add_clause(i, f^1, j, g^1)

    def add_and(self, i, f, j, g):
        self.add_clause(i, f, j, g^1)
        self.add_clause(i, f^1, j, g)
        self.add_clause(i, f, j, g)

    def satisfiable(self):
        """
        条件を足す割当が存在するかどうかを判定する。割当が存在するならばtrue、そうでないならfalseを返す。
        """
        group_num, ids = self.scc.scc_ids()
        for i in range(self.n):
            if ids[2*i] == ids[2*i + 1]: return False
            self.res[i] = (ids[2*i] < ids[2*i+1])
        return True

    def result(self):
        """
        最後に呼んだ satisfiable の、クローズを満たす割当を返す。
        """
        return self.res

#############################################################################

import sys
input = sys.stdin.readline

N=int(input())
if N>2756:
    print("Impossible")
    exit()


"""
xi と xj の少なくとも一つは存在 （ (xi,xj) = (0,1) or (1,0) or (1,1)）
    add_clause(i,1,j,1)

xi と xj は共存できない（ (xi,xj) = (0,1) or (1,0) or (0,0)）
    add_clause(i,0,j,0)

xi と xj はペアでのみ存在する（ (xi,xj) = (1,1) or (0,0)）
    add_xor(i,0,j,1)

xi と xj の片一方のみが必ず存在する（ (xi,xj) = (0,1) or (1,0)）
    add_xor(i,1,j,1)

"""
data=[]
for _ in range(N):
    data.append(input().rstrip())

ts = TwoSAT(2*N)
for i in range(N):
    u1=data[i]
    s11,t11=u1[:1],u1[1:]
    s12,t12=u1[:2],u1[2:]
    ts.add_xor(2*i,1,2*i+1,1)
    for j in range(i+1,N):
        u2=data[j]
        s21,t21=u2[:1],u2[1:]
        s22,t22=u2[:2],u2[2:]
        if s11==s21 or s11==t21 or t11==s21 or t11==t21:
            ts.add_or(2*i,0,2*j,0)
        if s12==s21 or s12==t21 or t12==s21 or t12==t21:
            ts.add_or(2*i+1,0,2*j,0)
        if s11==s22 or s11==t22 or t11==s22 or t11==t22:
            ts.add_or(2*i,0,2*j+1,0)
        if s12==s22 or s12==t22 or t12==s22 or t12==t22:
            ts.add_or(2*i+1,0,2*j+1,0)


flg=ts.satisfiable()
if not flg:
    print("Impossible")
    exit()

res=ts.result()

for i in range(N):
    u=data[i]
    if res[2*i]==1:
        print(u[:1],u[1:])
    else:
        print(u[:2],u[2:])
0