#include <iostream>
#include <algorithm>
#include <vector>
#define DIM 100010
using namespace std;
//ifstream fin ("date.in");
//ofstream fout ("date.out");
struct idk{
int x,y,cost;
};
vector <idk> mch;
int n,i,j,k,last,maxi,nr;
int v[DIM],t[DIM],poz[DIM];
inline int cmp (idk a, idk b){
return a.cost < b.cost;
}
inline int rad (int x){
while (t[x] > 0)
x = t[x];
return x;
}
int main (){
cin>>n;
for (i=1;i<=n;i++){
cin>>v[i];
maxi = max (maxi,v[i]);
}
sort (v+1,v+n+1);
k = 1;
for (i=2;i<=n;i++)
if (v[i] != v[i-1])
v[++k] = v[i];
for (i=1;i<=n;i++)
poz[v[i]] = i;
n = k;
for (i=1;i<=n;i++){
int last = i+1;
if (i < n){
int r = min (v[i]%v[i+1],v[i+1]%v[i]);
mch.push_back({i,i+1,r});
}
for (j=v[i]+v[i];j<=maxi;j+=v[i]){
if (poz[j]){ /// e in sir
if (last != poz[j]){
int r = min (v[i]%j,j%v[i]);
mch.push_back({i,poz[j],r});
last = poz[j];
}
} else {
int st = 1, dr = n, val = j;
while (st <= dr){
int mid = (st+dr)>>1;
if (v[mid] >= val){
dr = mid-1;
nr = mid;
} else st = mid+1;
}
if (last != nr){
int r = min (v[i]%v[nr],v[nr]%v[i]);
mch.push_back({i,nr,r});
last = nr;
}}}}
sort (mch.begin(),mch.end(),cmp);
int sol = 0;
for (int i=0;i<mch.size();i++){
int x = mch[i].x, y = mch[i].y;
int rx = rad(x), ry = rad(y);
if (rx != ry){
sol += mch[i].cost;
if (t[rx] < t[ry]){
t[rx] += t[ry];
t[ry] = rx;
} else {
t[ry] += t[rx];
t[rx] = ry;
}}}
cout<<sol;
return 0;
}
Compilation message
sirni.cpp: In function 'int main()':
sirni.cpp:68:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<mch.size();i++){
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
764 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
69 ms |
3548 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
2936 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
68 ms |
3524 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5053 ms |
7756 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
74 ms |
3580 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
75 ms |
3736 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
2680 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
