#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];
char viz[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;
}
n = p;
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];
}
}
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++){
if(viz[ v[i] ] == 1){
continue;
}
p = i + 1;
for(j = v[i] + v[i]; j <= v[n]; j += v[i]){
viz[j] = 1;
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:76:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i < w.size(); i++){
~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
77 ms |
47480 KB |
Output is correct |
2 |
Correct |
413 ms |
51364 KB |
Output is correct |
3 |
Correct |
81 ms |
49272 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
504 KB |
Output is correct |
2 |
Correct |
408 ms |
49436 KB |
Output is correct |
3 |
Correct |
81 ms |
49528 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
81 ms |
47864 KB |
Output is correct |
2 |
Correct |
74 ms |
44636 KB |
Output is correct |
3 |
Correct |
79 ms |
49400 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
295 ms |
14548 KB |
Output is correct |
2 |
Correct |
482 ms |
22608 KB |
Output is correct |
3 |
Correct |
410 ms |
22736 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
54 ms |
7404 KB |
Output is correct |
2 |
Correct |
443 ms |
22580 KB |
Output is correct |
3 |
Correct |
246 ms |
12000 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
462 ms |
22640 KB |
Output is correct |
2 |
Correct |
424 ms |
22756 KB |
Output is correct |
3 |
Correct |
279 ms |
14520 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
80 ms |
3692 KB |
Output is correct |
2 |
Correct |
412 ms |
22608 KB |
Output is correct |
3 |
Correct |
349 ms |
14556 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
598 ms |
66644 KB |
Output is correct |
2 |
Correct |
2758 ms |
116260 KB |
Output is correct |
3 |
Correct |
702 ms |
67024 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
556 ms |
66264 KB |
Output is correct |
2 |
Correct |
3266 ms |
115476 KB |
Output is correct |
3 |
Correct |
877 ms |
66936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
148 ms |
51608 KB |
Output is correct |
2 |
Execution timed out |
5019 ms |
181372 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |