#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){
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;
}
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]){
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:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i < w.size(); i++){
~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
504 KB |
Output is correct |
2 |
Correct |
100 ms |
2536 KB |
Output is correct |
3 |
Correct |
7 ms |
632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
504 KB |
Output is correct |
2 |
Correct |
506 ms |
1144 KB |
Output is correct |
3 |
Correct |
7 ms |
632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
415 ms |
9796 KB |
Output is correct |
2 |
Correct |
1390 ms |
34376 KB |
Output is correct |
3 |
Correct |
564 ms |
18004 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
58 ms |
2668 KB |
Output is correct |
2 |
Correct |
816 ms |
34208 KB |
Output is correct |
3 |
Correct |
402 ms |
9908 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
887 ms |
34384 KB |
Output is correct |
2 |
Correct |
1823 ms |
67448 KB |
Output is correct |
3 |
Correct |
531 ms |
18200 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
129 ms |
4964 KB |
Output is correct |
2 |
Correct |
1748 ms |
67116 KB |
Output is correct |
3 |
Correct |
524 ms |
18072 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
530 ms |
18028 KB |
Output is correct |
2 |
Execution timed out |
5087 ms |
263628 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
538 ms |
17492 KB |
Output is correct |
2 |
Execution timed out |
5075 ms |
264084 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
83 ms |
2796 KB |
Output is correct |
2 |
Execution timed out |
5097 ms |
263920 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |