#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, u, mid;
long long sol;
int v[DIM], r[DIM];
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){
while(r[x] > 0){
x = r[x];
}
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;
}
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++){
for(j = v[i] + v[i]; j <= v[n]; j += v[i]){
p = i + 1;
u = n;
while(p <= u){
mid = (p + u) / 2;
if(v[mid] >= j){
u = mid - 1;
}
else{
p = mid + 1;
}
}
if(v[p] < j + v[i]){
w.push_back( make_pair(p, i) );
}
}
}
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:65: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 |
5 ms |
632 KB |
Output is correct |
2 |
Correct |
151 ms |
2540 KB |
Output is correct |
3 |
Correct |
8 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
504 KB |
Output is correct |
2 |
Correct |
1049 ms |
1212 KB |
Output is correct |
3 |
Correct |
8 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
632 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
7 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
466 ms |
9844 KB |
Output is correct |
2 |
Correct |
1639 ms |
34332 KB |
Output is correct |
3 |
Correct |
660 ms |
17956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
64 ms |
2664 KB |
Output is correct |
2 |
Correct |
974 ms |
34300 KB |
Output is correct |
3 |
Correct |
449 ms |
10064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1018 ms |
34444 KB |
Output is correct |
2 |
Correct |
2147 ms |
67200 KB |
Output is correct |
3 |
Correct |
612 ms |
18000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
150 ms |
4964 KB |
Output is correct |
2 |
Correct |
2068 ms |
67196 KB |
Output is correct |
3 |
Correct |
592 ms |
18000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
601 ms |
18128 KB |
Output is correct |
2 |
Execution timed out |
5104 ms |
264332 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
613 ms |
18180 KB |
Output is correct |
2 |
Execution timed out |
5076 ms |
264376 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
95 ms |
2780 KB |
Output is correct |
2 |
Execution timed out |
5037 ms |
264348 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |