結果
| 問題 |
No.470 Inverse S+T Problem
|
| コンテスト | |
| ユーザー |
 zkou
|
| 提出日時 | 2021-03-13 10:37:39 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 112 ms / 2,000 ms |
| コード長 | 6,895 bytes |
| コンパイル時間 | 281 ms |
| コンパイル使用メモリ | 82,288 KB |
| 実行使用メモリ | 79,040 KB |
| 最終ジャッジ日時 | 2024-12-22 14:04:34 |
| 合計ジャッジ時間 | 3,300 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 27 |
ソースコード
class _csr:
def __init__(self, n, edges):
self.start = [0] * (n + 1)
self.elist = [0] * len(edges)
for v, _ in edges:
self.start[v + 1] += 1
for i in range(1, n + 1):
self.start[i] += self.start[i - 1]
counter = self.start.copy()
for v, e in edges:
self.elist[counter[v]] = e
counter[v] += 1
class scc_graph:
"""It calculates the strongly connected components of directed graphs.
"""
def __init__(self, n):
"""It creates a directed graph with n vertices and 0 edges.
Constraints
-----------
> 0 <= n <= 10 ** 8
Complexity
----------
> O(n)
"""
self.n = n
self.edges = []
def add_edge(self, from_, to):
"""It adds a directed edge from the vertex `from_` to the vertex `to`.
Constraints
-----------
> 0 <= from_ < n
> 0 <= to < n
Complexity
----------
> O(1) amortized
"""
# assert 0 <= from_ < self.n
# assert 0 <= to < self.n
self.edges.append((from_, to))
def _scc_ids(self):
g = _csr(self.n, self.edges)
now_ord = 0
group_num = 0
visited = []
low = [0] * self.n
order = [-1] * self.n
ids = [0] * self.n
parent = [-1] * self.n
stack = []
for i in range(self.n):
if order[i] == -1:
stack.append(i)
stack.append(i)
while stack:
v = stack.pop()
if order[v] == -1:
low[v] = order[v] = now_ord
now_ord += 1
visited.append(v)
for i in range(g.start[v], g.start[v + 1]):
to = g.elist[i]
if order[to] == -1:
stack.append(to)
stack.append(to)
parent[to] = v
else:
low[v] = min(low[v], order[to])
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):
"""It returns the list of the "list of the vertices" that satisfies the following.
> Each vertex is in exactly one "list of the vertices".
> Each "list of the vertices" corresponds to the vertex set of a strongly connected component.
The order of the vertices in the list is undefined.
> The list of "list of the vertices" are sorted in topological order,
i.e., for two vertices u, v in different strongly connected components,
if there is a directed path from u to v,
the list contains u appears earlier than the list contains v.
Complexity
----------
> O(n + m), where m is the number of added edges.
"""
group_num, ids = self._scc_ids()
groups = [[] for _ in range(group_num)]
for i, x in enumerate(ids):
groups[x].append(i)
return groups
class two_sat:
"""It solves 2-SAT.
For variables x[0], x[1], ..., x[n-1] and clauses with form
> ((x[i] = f) or (x[j] = g)),
it decides whether there is a truth assignment that satisfies all clauses.
"""
def __init__(self, n):
"""It creates a 2-SAT of n variables and 0 clauses.
Constraints
-----------
> 0 <= n <= 10 ** 8
Complexity
----------
> O(n)
"""
self.n = n
self._answer = [False] * n
self.scc = scc_graph(2 * n)
def add_clause(self, i, f, j, g):
"""It adds a clause ((x[i] = f) or (x[j] = g)).
Constraints
-----------
> 0 <= i < n
> 0 <= j < n
Complexity
----------
> O(1) amortized
"""
# assert 0 <= i < self.n
# assert 0 <= j < self.n
self.scc.add_edge(2 * i + (f == 0), 2 * j + (g == 1))
self.scc.add_edge(2 * j + (g == 0), 2 * i + (f == 1))
def satisfiable(self):
"""If there is a truth assignment that satisfies all clauses, it returns `True`.
Otherwise, it returns `False`.
Constraints
-----------
> You may call it multiple times.
Complexity
----------
> O(n + m), where m is the number of added clauses.
"""
_, ids = self.scc._scc_ids()
for i in range(self.n):
if ids[2 * i] == ids[2 * i + 1]:
return False
self._answer[i] = (ids[2*i] < ids[2*i+1])
return True
def answer(self):
"""It returns a truth assignment that satisfies all clauses of the last call of `satisfiable`.
If we call it before calling `satisfiable` or when the last call of `satisfiable` returns `False`,
it returns the list of length n with undefined elements.
Complexity
----------
> O(n)
"""
return self._answer.copy()
def main():
N = int(input())
Us = [input() for _ in range(N)]
# (52 ** 2 + 52) // 2 = 1378
# Thus, if N > 1378, then "Impossible"
if N > 1378:
print("Impossible")
return
ts = two_sat(N)
for i in range(N):
Ui = Us[i]
i_true_1 = Ui[0]
i_true_2 = Ui[1:]
i_false_1 = Ui[2]
i_false_2 = Ui[:2]
for j in range(i + 1, N):
Uj = Us[j]
j_true_1 = Uj[0]
j_true_2 = Uj[1:]
j_false_1 = Uj[2]
j_false_2 = Uj[:2]
if i_true_1 == j_true_1 or i_true_2 == j_true_2:
ts.add_clause(i, 0, j, 0)
if i_true_1 == j_false_1 or i_true_2 == j_false_2:
ts.add_clause(i, 0, j, 1)
if i_false_1 == j_true_1 or i_false_2 == j_true_2:
ts.add_clause(i, 1, j, 0)
if i_false_1 == j_false_1 or i_false_2 == j_false_2:
ts.add_clause(i, 1, j, 1)
sts = ts.satisfiable()
if not sts:
print("Impossible")
return
for i, ans in enumerate(ts.answer()):
print(Us[i][:2 - ans], Us[i][2 - ans:])
main()