import java.io.*;
import java.util.*;
public class sirni {
static int n, max;
static TreeSet<Node> arr;
static ArrayList<Edge> edges = new ArrayList<>();
public static void main(String[] args) throws IOException{
BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
//BufferedReader file = new BufferedReader(new FileReader("file.in"));
//rintWriter outfile = new PrintWriter (new BufferedWriter(new FileWriter("Sirni.out")));
n = Integer.parseInt(file.readLine());
arr = new TreeSet<>();
for (int i=0; i<n; i++){
int curr = Integer.parseInt(file.readLine());
arr.add(new Node(curr, i));
max = Math.max(max, curr);
}
for (Node i : arr){
findMultiples(i.val, i.id);
}
Collections.sort(edges);
DSU dsu = new DSU(n);
int ans = 0;
for (Edge curr : edges){
if (dsu.find(curr.from) != dsu.find(curr.to)){
dsu.union(curr.from, curr.to);
ans += curr.cost;
}
}
System.out.println(ans);
}
public static void findMultiples(int base, int start){
int k = 1;
while (base*k <= max){
if (k == 1){
Node higher = arr.ceiling(new Node(base*k+1, -1));
if (higher != null){
edges.add(new Edge(start, higher.id, higher.val % base));
}
}else{
Node ceil = arr.ceiling(new Node(base*k, -1));
if (ceil != null){
edges.add(new Edge(start, ceil.id, ceil.val % base));
}
}
k++;
}
}
static class Edge implements Comparable<Edge>{
int from, to, cost;
public Edge(int from ,int to, int cost){
this.from = from;
this.to = to;
this.cost = cost;
}
public int compareTo(Edge o){
return this.cost - o.cost;
}
}
static class Node implements Comparable<Node>{
int val;
int id;
public Node(int val ,int id){
this.val = val;
this.id = id;
}
public int compareTo(Node o){
if (this.val == o.val){
return this.id - o.id;
}
return this.val - o.val;
}
}
static class DSU{
int n;
int[] parent;
int[] size;
public DSU(int n){
this.n = n;
parent = new int[n];
size = new int[n];
for (int i=0; i<n; i++){
parent[i] = i;
size[i] = 1;
}
}
public int find(int a){
if (parent[a] == a){
return a;
}
return parent[a] = find(parent[a]); // Path compression
}
public void union(int a, int b){
a = find(a);
b = find(b);
if (a == b){
// Same component
return;
}
if (size[a] < size[b]){
// Point a to b
parent[a] = b;
size[b] += size[a];
}else{
// Point b to a
parent[b] = a;
size[a] += size[b];
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
196 ms |
11352 KB |
Output is correct |
| 2 |
Incorrect |
1499 ms |
149284 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
177 ms |
11592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
214 ms |
11796 KB |
Output is correct |
| 2 |
Incorrect |
116 ms |
8864 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1392 ms |
60392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
552 ms |
20524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2612 ms |
130232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
776 ms |
31496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1763 ms |
73324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1710 ms |
96388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
675 ms |
21228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
