# BeginCodeSnip{DSU (from the module)}
class DisjointSets:
def __init__(self, size: int) -> None:
self.parents = [-1 for _ in range(size)]
self.sizes = [1 for _ in range(size)]
# finds the "representative" node in a's component
def find(self, x: int) -> int:
if self.parents[x] == -1:
return x
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
# returns whether the merge changed connectivity
def unite(self, x: int, y: int) -> bool:
x_root = self.find(x)
y_root = self.find(y)
if x_root == y_root:
return False
if self.sizes[x_root] < self.sizes[y_root]:
x_root, y_root = y_root, x_root
self.parents[y_root] = x_root
self.sizes[x_root] += self.sizes[y_root]
return True
# returns whether two nodes are in the same connected component
def connected(self, x: int, y: int) -> bool:
return self.find(x) == self.find(y)
# EndCodeSnip
cards = sorted({int(input()) for _ in range(int(input()))})
largest = cards[-1] # since we sorted the cards already
# next_largest[i] contains the index of lowest card value that's >= i
next_largest = [-1 for _ in range(largest + 1)]
for i, c in enumerate(cards):
next_largest[c] = i
for c in range(largest - 1, -1, -1):
# if this isn't assigned yet, assign it the previous one
if next_largest[c] == -1:
next_largest[c] = next_largest[c + 1]
good_links = [[] for _ in range(largest + 1)]
for i in range(len(cards) - 1):
good_links[cards[i + 1] % cards[i]].append((i, i + 1))
at = 2 * cards[i]
while at <= largest:
good_mod = next_largest[at]
good_links[cards[good_mod] % cards[i]].append((i, good_mod))
at += cards[i]
total_cost = 0
linked_cards = DisjointSets(len(cards))
for c in range(largest + 1):
for a, b in good_links[c]:
result = linked_cards.unite(a, b)
total_cost += c * result
print(total_cost)
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
765 ms |
489972 KB |
Output is correct |
| 2 |
Correct |
1849 ms |
665528 KB |
Output is correct |
| 3 |
Correct |
943 ms |
494596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
22320 KB |
Output is correct |
| 2 |
Runtime error |
1192 ms |
786432 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
785 ms |
490288 KB |
Output is correct |
| 2 |
Correct |
880 ms |
488244 KB |
Output is correct |
| 3 |
Correct |
823 ms |
490368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
630 ms |
135752 KB |
Output is correct |
| 2 |
Correct |
1104 ms |
311660 KB |
Output is correct |
| 3 |
Correct |
722 ms |
199184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
273 ms |
82948 KB |
Output is correct |
| 2 |
Correct |
1236 ms |
186652 KB |
Output is correct |
| 3 |
Correct |
496 ms |
111208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
869 ms |
207832 KB |
Output is correct |
| 2 |
Correct |
1292 ms |
382504 KB |
Output is correct |
| 3 |
Correct |
679 ms |
178904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
288 ms |
53436 KB |
Output is correct |
| 2 |
Correct |
1973 ms |
411612 KB |
Output is correct |
| 3 |
Correct |
653 ms |
178576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1497 ms |
620608 KB |
Output is correct |
| 2 |
Runtime error |
1388 ms |
786432 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1693 ms |
663116 KB |
Output is correct |
| 2 |
Runtime error |
1397 ms |
786432 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1107 ms |
507612 KB |
Output is correct |
| 2 |
Runtime error |
2005 ms |
786432 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
