#1150951 (PyPy3) No.470 Inverse S+T Problem

• 問題: No.470 Inverse S+T Problem
• ユーザー: detteiuu
• 提出日時: 2026-03-01 22:55:58
• 言語: PyPy3 (7.3.17)
• 結果: RE
• 実行時間: -
• コード長: 4,691 bytes
• コンパイル時間: 303 ms
• コンパイル使用メモリ: 85,312 KB
• 実行使用メモリ: 83,508 KB
• 最終ジャッジ日時: 2026-03-01 22:56:01
• 合計ジャッジ時間: 2,871 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
sample	AC * 4
other	AC * 22 RE * 5

ソースコード

from sys import stdin
input = stdin.readline

def scc(N,edges):
    M=len(edges)
    start=[0]*(N+1)
    elist=[0]*M
    for e in edges:
        start[e[0]+1]+=1
    for i in range(1,N+1):
        start[i]+=start[i-1]
    counter=start[:]
    for e in edges:
        elist[counter[e[0]]]=e[1]
        counter[e[0]]+=1
    visited=[]
    low=[0]*N
    Ord=[-1]*N
    ids=[0]*N
    NG=[0,0]
    def dfs(v):
        stack=[(v,-1,0),(v,-1,1)]
        while stack:
            v,bef,t=stack.pop()
            if t:
                if bef!=-1 and Ord[v]!=-1:
                    low[bef]=min(low[bef],Ord[v])
                    stack.pop()
                    continue
                low[v]=NG[0]
                Ord[v]=NG[0]
                NG[0]+=1
                visited.append(v)
                for i in range(start[v],start[v+1]):
                    to=elist[i]
                    if Ord[to]==-1:
                        stack.append((to,v,0))
                        stack.append((to,v,1))
                    else:
                        low[v]=min(low[v],Ord[to])
            else:
                if low[v]==Ord[v]:
                    while(True):
                        u=visited.pop()
                        Ord[u]=N
                        ids[u]=NG[1]
                        if u==v:
                            break
                    NG[1]+=1
                low[bef]=min(low[bef],low[v])
    for i in range(N):
        if Ord[i]==-1:
            dfs(i)
    for i in range(N):
        ids[i]=NG[1]-1-ids[i]
    group_num=NG[1]
    counts=[0]*group_num
    for x in ids:
        counts[x]+=1
    groups=[[] for i in range(group_num)]
    for i in range(N):
        groups[ids[i]].append(i)
    return groups

class TwoSAT:
    def __init__(self, N, M):
        self.N = N
        self.M = M
        self.edge = []
        self.solution = [False]*self.N
        self.cnt = 0
        self.solved = False
    
    def add_constraint(self, u, f, v, g):
        self.edge.append((u+(self.N+self.M)*f, v+(self.N+self.M)*g))

    def add_clause(self, u, f, v, g):
        self.add_constraint(u, f^True, v, g)
        self.add_constraint(v, g^True, u, f)
    
    def add_at_most_one(self, A):
        for i in range(len(A)):
            self.add_clause(A[i][0], A[i][1], self.N+self.cnt+i, True)
            if i+1 < len(A):
                self.add_clause(self.N+self.cnt+i, False, self.N+self.cnt+i+1, True)
                self.add_clause(self.N+self.cnt+i, False, A[i+1][0], A[i+1][1])
        self.cnt += len(A)
    
    def solve(self):
        SCC = scc((self.N+self.M)*2, self.edge)
        order = [-1]*((self.N+self.M)*2)
        for i, s in enumerate(SCC):
            for n in s:
                order[n] = i
        for i in range(self.N):
            if order[i] == order[i+self.N+self.M]:
                return False
            if order[i] > order[i+self.N+self.M]:
                self.solution[i] = False
            else:
                self.solution[i] = True
        self.solved = True
        return True
    
    def result(self):
        return self.solution[:self.N] if self.solved else None

def code(s):
    if s.islower():
        return ord(s)-ord("a")
    else:
        return ord(s)-ord("A")+26

def encode(s):
    if len(s) == 2:
        return code(s[0])*L+code(s[1])
    else:
        return L*L+code(s[0])

N = int(input())
U = [input().rstrip("\n") for _ in range(N)]

L = 52

A = [[] for _ in range((L+1)*L)]
cnt = [0]*((L+1)*L)
for i, u in enumerate(U):
    a, b = encode(u[0]), encode(u[1:])
    A[a].append(i)
    A[b].append(i)
    a, b = encode(u[:2]), encode(u[2])
    A[a].append(i)
    A[b].append(i)
    if 2 <= len(A[a]) and A[a][-2:] == [i, i]:
        cnt[a] += 1
        if cnt[a] == 2:
            exit(print("Impossible"))
        for _ in range(2):
            A[a].pop()
    if 2 <= len(A[b]) and A[b][-2:] == [i, i]:
        cnt[b] += 1
        if cnt[b] == 2:
            exit(print("Impossible"))
        for _ in range(2):
            A[b].pop()

TS = TwoSAT(N, N*4)
for i in range((L+1)*L):
    if cnt[i] == 0:
        E = []
        for idx in A[i]:
            if encode(U[idx][0]) == i or encode(U[idx][1:]) == i:
                E.append((idx, True))
            else:
                E.append((idx, False))
        TS.add_at_most_one(E)
    else:
        for idx in A[i]:
            if encode(U[idx][0]) == i or encode(U[idx][1:]) == i:
                TS.add_constraint(idx, False, idx, True)
            else:
                TS.add_constraint(idx, True, idx, False)

TS.solve()
for i, res in enumerate(TS.result()):
    if not res:
        print(U[i][0], U[i][1:])
    else:
        print(U[i][:2], U[i][2])