#include<iostream>
#include<algorithm>
#include<vector>
#define f first
#define s second
#define DIM 100005
using namespace std;
int n, i, j, r1, r2, p;
long long sol;
int v[DIM], r[DIM], nxt[10000005];
vector< pair<int, int> > w;
int cmp(pair<int, int> a, pair<int, int> b){
return v[a.f] % v[a.s] < v[b.f] % v[b.s];
}
int rad(int x){
int y = x;
while(r[y] > 0){
y = r[y];
}
while(r[x] > 0){
int aux = r[x];
r[x] = y;
x = aux;
}
return x;
}
int main(){
cin>> n;
for(i = 1; i <= n; i++){
cin>> v[i];
}
sort(v + 1, v + n + 1);
p = 1;
for(i = 2; i <= n; i++){
if(v[i] != v[p]){
v[++p] = v[i];
}
}
if(v[1] == 1){
cout<< 0;
return 0;
}
for(i = 1; i <= n; i++){
nxt[ v[i] ] = i;
}
for(i = v[n]; i >= v[1]; i--){
if(nxt[i] == 0){
nxt[i] = nxt[i + 1];
}
}
n = p;
for(i = 1; i < n; i++){
if(v[i + 1] < 2 * v[i]){
w.push_back( make_pair(i + 1, i) );
}
}
for(i = 1; i < n; i++){
p = i + 1;
for(j = v[i] + v[i]; j <= v[n]; j += v[i]){
p = nxt[j];
if(v[p] < j + v[i]){
w.push_back( make_pair(p, i) );
p++;
}
}
}
sort(w.begin(), w.end(), cmp);
for(i = 1; i <= n; i++){
r[i] = -1;
}
for(i = 0; i < w.size(); i++){
r1 = rad(w[i].f);
r2 = rad(w[i].s);
if(r1 != r2){
sol += v[ w[i].f ] % v[ w[i].s ];
if(r[r1] < r[r2]){
r[r1] += r[r2];
r[r2] = r1;
}
else{
r[r2] += r[r1];
r[r1] = r2;
}
}
}
cout<< sol;
}
Compilation message
sirni.cpp: In function 'int main()':
sirni.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i < w.size(); i++){
~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
70 ms |
39416 KB |
Output is correct |
2 |
Incorrect |
180 ms |
41552 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
70 ms |
39544 KB |
Output is correct |
2 |
Incorrect |
72 ms |
39400 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
353 ms |
13256 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
55 ms |
6632 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
762 ms |
37716 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
117 ms |
5604 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
564 ms |
56464 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
535 ms |
56528 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
135 ms |
41704 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |