// #pragma GCC optimze("O3")
// #pragma GCC target("avx,avx2,sse4")
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
struct DSU {
vector<int> p, r;
DSU(int n) {
p.assign(n,0);
r.assign(n,0);
for (int i=0;i<n;i++)p[i]=i;
}
int get(int i) {
if (i != p[i]) p[i]=get(p[i]);
return p[i];
}
bool unite(int a,int b) {
assert(a < p.size() && b < p.size());
a=get(a);
b=get(b);
if (a==b)return false;
if (r[a]<r[b])swap(a,b);
p[b]=a;
if (r[a]==r[b])r[a]++;
return true;
}
};
signed test(int n, vector<int> b) {
vector<int> clos(b.back()+1,-1);
for (int x:b) {
clos[x]=x;
}
for (int i=clos.size()-2;i>=0;i--) {
if (clos[i] == -1) {
clos[i]=clos[i+1];
}
}
typedef array<int,3> pii;
vector<pii> edg;
for (int x:b) {
vector<pii> tmp;
if (x != b.back()) {
tmp.push_back({clos[x+1] % x, x, clos[x+1]});
}
for (int j=2*x;j<=b.back();j+=x) {
if (clos[j] != -1) {
if (!tmp.size()) {
tmp.push_back({clos[j] % x, clos[j], x});
}
else if (tmp.back()[1] != clos[j]) {
tmp.push_back({clos[j] % x, clos[j], x});
}
}
}
if (tmp.size() == 0 || tmp.back()[1] != clos[b.back()]) {
tmp.push_back({clos[b.back()] % x, clos[b.back()], x});
}
for (auto y:tmp) edg.push_back(y);
}
sort(edg.begin(),edg.end());
map<int,int> mp;
for (int i=0;i<b.size();i++) {
mp[b[i]]=i;
}
for (auto &x:edg) {
// cout<<x[1]<<" "<<x[2]<<"\n";
x[1]=mp[x[1]];
x[2]=mp[x[2]];
}
// cout<<"\n";
DSU d(b.size());
int cost=0;
for (auto x:edg) {
if (d.unite(x[1], x[2])) {
// cout<<b[x[1]]<<" "<<b[x[2]]<<"\n";
cost+=x[0];
}
}
return cost;
}
// bool brute() {
// int len=(rand() % 5)+5;
// vector<int> b;
// set<int> chose;
// for (int i=0;i<len;i++) {
// int j=(rand() % 20) + 5;
// while (chose.find(j) != chose.end()) {
// j=(rand() % 20) + 5;
// }
// chose.insert(j);
// b.push_back(j);
// }
// sort(b.begin(),b.end());
// typedef array<int,3> pii;
// vector<pii> g;
// for (int i=0;i<len;i++) {
// for (int j=i+1;j<len;j++) {
// g.push_back({b[j] % b[i], j, i});
// }
// }
// sort(g.begin(),g.end());
// DSU d(len);
// int cost=0;
// for (auto x:g) {
// if (d.unite(x[1], x[2])) {
// cout<<b[x[1]]<<" "<<b[x[2]]<<"\n";
// cost += x[0];
// }
// }
// cout<<"\n";
// int cost2 = test(len, b);
// cout<<"\n";
// cout<<cost<<" "<<cost2<<"\n\n";
// for (int x:b) {
// cout<<x<<" ";
// }
// cout<<"\n";
// return true;
// }
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;cin>>n;
vector<int> a(n);
for (int &x:a)cin>>x;
sort(a.begin(),a.end());
vector<int> b;
for (int x:a) {
if (b.size()==0||b.back()!=x)b.push_back(x);
}
cout<<test(n,b)<<"\n";
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from sirni.cpp:4:
sirni.cpp: In member function 'bool DSU::unite(int64_t, int64_t)':
sirni.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | assert(a < p.size() && b < p.size());
| ~~^~~~~~~~~~
sirni.cpp:23:34: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | assert(a < p.size() && b < p.size());
| ~~^~~~~~~~~~
sirni.cpp: In function 'int test(int64_t, std::vector<long int>)':
sirni.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for (int i=0;i<b.size();i++) {
| ~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
35 ms |
78932 KB |
Output is correct |
| 2 |
Correct |
104 ms |
85688 KB |
Output is correct |
| 3 |
Correct |
35 ms |
78848 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
860 KB |
Output is correct |
| 2 |
Correct |
304 ms |
80048 KB |
Output is correct |
| 3 |
Correct |
34 ms |
79152 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
34 ms |
78932 KB |
Output is correct |
| 2 |
Correct |
32 ms |
78676 KB |
Output is correct |
| 3 |
Correct |
34 ms |
79100 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
410 ms |
62156 KB |
Output is correct |
| 2 |
Correct |
1333 ms |
113780 KB |
Output is correct |
| 3 |
Correct |
524 ms |
64464 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
56 ms |
16340 KB |
Output is correct |
| 2 |
Correct |
741 ms |
109724 KB |
Output is correct |
| 3 |
Correct |
384 ms |
59380 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
867 ms |
111836 KB |
Output is correct |
| 2 |
Correct |
1743 ms |
211880 KB |
Output is correct |
| 3 |
Correct |
531 ms |
64744 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
129 ms |
16632 KB |
Output is correct |
| 2 |
Correct |
1784 ms |
210524 KB |
Output is correct |
| 3 |
Correct |
485 ms |
64424 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
570 ms |
133284 KB |
Output is correct |
| 2 |
Runtime error |
671 ms |
786432 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
568 ms |
134296 KB |
Output is correct |
| 2 |
Runtime error |
659 ms |
786432 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
112 ms |
86036 KB |
Output is correct |
| 2 |
Runtime error |
610 ms |
786432 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
