import java.io.*;
import java.util.*;
public class sirni {
public static void main(String[] args) throws IOException {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
int cardNum = Integer.parseInt(read.readLine());
int[] cards = new int[cardNum];
for (int c = 0; c < cardNum; c++) {
cards[c] = Integer.parseInt(read.readLine());
}
// we can erase the dupes bc modding them with the original one = 0
cards = Arrays.stream(cards).distinct().sorted().toArray();
int largest = Arrays.stream(cards).max().getAsInt();
// nextLargest[i] contains the index of lowest card value that's >= i
int[] nextLargest = new int[largest + 1];
Arrays.fill(nextLargest, -1);
for (int i = 0; i < cards.length; i++) {
nextLargest[cards[i]] = i;
}
for (int c = largest - 1; c >= 0; c--) {
// if this isn't assigned yet, assign it the previous one
if (nextLargest[c] == -1) {
nextLargest[c] = nextLargest[c + 1];
}
}
List<Pair>[] goodLinks = new ArrayList[largest + 1];
for (int i = 0; i < goodLinks.length; i++) {
goodLinks[i] = new ArrayList<>();
}
for (int i = 0; i < cards.length - 1; i++) {
// get all relevant cards this card could be connected to
goodLinks[cards[i + 1] % cards[i]].add(new Pair(i, i + 1));
for (int at = 2 * cards[i]; at <= largest; at += cards[i]) {
int goodMod = nextLargest[at];
goodLinks[cards[goodMod] % cards[i]].add(new Pair(i, goodMod));
}
}
long totalCost = 0;
DisjointSets linkedCards = new DisjointSets(cards.length);
for (int c = 0; c <= largest; c++) {
for (Pair link : goodLinks[c]) {
if (linkedCards.union(link.first, link.second)) {
totalCost += c;
}
}
}
System.out.println(totalCost);
}
}
// BeginCodeSnip{Pair Class}
class Pair {
public int first, second;
public Pair(int first, int second) {
this.first = first;
this.second = second;
}
}
// EndCodeSnip
// BeginCodeSnip{DSU (from the module)}
class DisjointSets {
int[] parents; // 0-indexed
int[] sizes;
public DisjointSets(int size) {
sizes = new int[size];
parents = new int[size];
Arrays.fill(sizes, 1);
Arrays.fill(parents, -1);
}
// finds the "representative" node in a's component
public int find(int x) {
return parents[x] == -1 ? x : (parents[x] = find(parents[x]));
}
// returns whether the merge changed connectivity
public boolean union(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
if (xRoot == yRoot) { return false; }
if (sizes[xRoot] < sizes[yRoot]) {
parents[xRoot] = yRoot;
sizes[yRoot] += sizes[xRoot];
} else {
parents[yRoot] = xRoot;
sizes[xRoot] += sizes[yRoot];
}
return true;
}
// returns whether two nodes are in the same connected component
public boolean connected(int x, int y) { return find(x) == find(y); }
}
// EndCodeSnip
Compilation message
Note: sirni.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
954 ms |
421492 KB |
Output is correct |
| 2 |
Correct |
1339 ms |
634112 KB |
Output is correct |
| 3 |
Correct |
1111 ms |
534084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
23224 KB |
Output is correct |
| 2 |
Runtime error |
1370 ms |
786432 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
953 ms |
422064 KB |
Output is correct |
| 2 |
Correct |
974 ms |
421480 KB |
Output is correct |
| 3 |
Correct |
986 ms |
422472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
850 ms |
126056 KB |
Output is correct |
| 2 |
Correct |
1236 ms |
238180 KB |
Output is correct |
| 3 |
Correct |
1036 ms |
181196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
542 ms |
100488 KB |
Output is correct |
| 2 |
Correct |
932 ms |
177092 KB |
Output is correct |
| 3 |
Correct |
722 ms |
108944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1018 ms |
189648 KB |
Output is correct |
| 2 |
Correct |
1375 ms |
343160 KB |
Output is correct |
| 3 |
Correct |
861 ms |
171036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
513 ms |
59812 KB |
Output is correct |
| 2 |
Correct |
1473 ms |
332280 KB |
Output is correct |
| 3 |
Correct |
867 ms |
168316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1704 ms |
587676 KB |
Output is correct |
| 2 |
Runtime error |
1737 ms |
786432 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1771 ms |
627032 KB |
Output is correct |
| 2 |
Runtime error |
1656 ms |
786432 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1552 ms |
552160 KB |
Output is correct |
| 2 |
Runtime error |
1996 ms |
786432 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
