#include <fstream>
#include <algorithm>
#include <vector>
#define DIM 100010
#define DIMM 10000010
using namespace std;
ifstream cin ("date.in");
ofstream cout ("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[DIMM],w[DIMM],ok[DIMM];
inline int cmp (idk a, idk b){
return a.cost < b.cost;
}
inline int rad (int x){
int nr = x;
while (t[x] > 0)
x = t[x];
while (t[nr] > 0){
int aux = t[nr];
t[nr] = x;
nr = aux;
}
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];
poz[v[k]] = k;
}
n = k;
int idx = n+1;
for (i=maxi;i;--i){
if (i == v[idx-1])
idx--;
w[i] = idx;
}
for (i=1;i<=n;++i){
int last = i+1;
if (i < n){
int r = v[i+1]%v[i];
mch.push_back({i,i+1,r});
}
if (ok[v[i]])
continue;
for (j=v[i]+v[i];j<=maxi;j+=v[i]){
ok[j] = 1;
if (poz[j]){ /// e in sir
if (last != poz[j]){
int r = j%v[i];
mch.push_back({i,poz[j],r});
last = poz[j];
}
} else {
int nr = w[j]; /// cea mai mica pozitie pe care se gaseste primul mai mare decat j
if (last != nr){
int r = v[nr]%v[i];
mch.push_back({i,nr,r});
last = nr;
}}}}
sort (mch.begin(),mch.end(),cmp);
for (i=1;i<=n;++i)
t[i] = -1;
long long 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:80: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 |
8 ms |
504 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
376 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
376 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
504 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
376 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
504 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
476 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
476 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
376 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
376 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
