84 lines
2.4 KiB
Python
84 lines
2.4 KiB
Python
|
import sys
|
||
|
|
import collections
|
||
|
|
|
||
|
|
def main():
|
||
|
|
|
||
|
|
lines = sys.stdin.read().splitlines()
|
||
|
|
|
||
|
|
order_rules = set()
|
||
|
|
updates = []
|
||
|
|
i = 0
|
||
|
|
n = len(lines)
|
||
|
|
while i < n and lines[i].strip():
|
||
|
|
line = lines[i].strip()
|
||
|
|
if '|' in line:
|
||
|
|
x, y = line.split('|')
|
||
|
|
x = int(x)
|
||
|
|
y = int(y)
|
||
|
|
order_rules.add((x, y))
|
||
|
|
i += 1
|
||
|
|
|
||
|
|
while i < n and not lines[i].strip():
|
||
|
|
i += 1
|
||
|
|
|
||
|
|
while i < n:
|
||
|
|
line = lines[i].strip()
|
||
|
|
if line:
|
||
|
|
update = [int(x) for x in line.split(',')]
|
||
|
|
updates.append(update)
|
||
|
|
i += 1
|
||
|
|
|
||
|
|
middle_pages_correct = []
|
||
|
|
middle_pages_incorrect = []
|
||
|
|
|
||
|
|
for update in updates:
|
||
|
|
position = {page: idx for idx, page in enumerate(update)}
|
||
|
|
|
||
|
|
valid = True
|
||
|
|
for x, y in order_rules:
|
||
|
|
if x in position and y in position:
|
||
|
|
if position[x] >= position[y]:
|
||
|
|
valid = False
|
||
|
|
break
|
||
|
|
|
||
|
|
if valid:
|
||
|
|
mid_index = len(update) // 2
|
||
|
|
middle_page = update[mid_index]
|
||
|
|
middle_pages_correct.append(middle_page)
|
||
|
|
else:
|
||
|
|
pages_in_update = set(update)
|
||
|
|
graph = collections.defaultdict(list)
|
||
|
|
indegree = collections.defaultdict(int)
|
||
|
|
for x in pages_in_update:
|
||
|
|
indegree[x] = 0
|
||
|
|
|
||
|
|
for x, y in order_rules:
|
||
|
|
if x in pages_in_update and y in pages_in_update:
|
||
|
|
graph[x].append(y)
|
||
|
|
indegree[y] += 1
|
||
|
|
|
||
|
|
queue = collections.deque([node for node in pages_in_update if indegree[node] == 0])
|
||
|
|
sorted_pages = []
|
||
|
|
|
||
|
|
while queue:
|
||
|
|
node = queue.popleft()
|
||
|
|
sorted_pages.append(node)
|
||
|
|
for neighbor in graph[node]:
|
||
|
|
indegree[neighbor] -= 1
|
||
|
|
if indegree[neighbor] == 0:
|
||
|
|
queue.append(neighbor)
|
||
|
|
|
||
|
|
if len(sorted_pages) != len(pages_in_update):
|
||
|
|
print("Cycle detected in ordering rules. Cannot perform topological sort.")
|
||
|
|
sys.exit(1)
|
||
|
|
|
||
|
|
mid_index = len(sorted_pages) // 2
|
||
|
|
middle_page = sorted_pages[mid_index]
|
||
|
|
middle_pages_incorrect.append(middle_page)
|
||
|
|
|
||
|
|
total_incorrect = sum(middle_pages_incorrect)
|
||
|
|
print(total_incorrect)
|
||
|
|
|
||
|
|
if __name__ == "__main__":
|
||
|
|
main()
|