oj.uz

답안 #1005748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1005748 2024-06-23T02:22:01 Z orcslop Sirni (COCI17_sirni) C++17
0 / 140
 590 ms 242280 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define f first
#define s second
#define mkp make_pair
#define pii pair<int, int>

const int MAXN = 1e5 + 5; 
const int MAXP = 1e7 + 5; 

int n; 
int v[MAXN]; 
int dist[MAXP]; 
int rdist[MAXP]; 
int sieve[MAXP]; 
map<int, int> vis; 

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    fill(dist, dist + MAXP, 1e9); 
    fill(rdist, rdist + MAXP, 1e9); 
    cin >> n; 
    for(int i = 0; i < n; i++){
        cin >> v[i]; 
        vis[v[i]]++; 
    }
    sort(v, v + n, greater<int>()); 
    for(auto x : vis){
        for(int i = x.f; i < MAXP; i += x.f){
            sieve[i]++; 
        }
    }
    for(int i = 1; i < MAXP; i++){
        if(sieve[i] > 0) dist[i] = 0; 
        dist[i] = min(dist[i], dist[i - 1] + 1); 
    }
    for(auto &x : vis){
        if(sieve[x.f] == 1) dist[x.f] = min(dist[x.f - 1] + 1, v[n - 1]); 
        x.s = -1; 
    }
    for(int i = 0; i < n; i++){
        rdist[v[i]] = 0; 
    }
    for(int i = MAXN - 2; i >= 1; i--){
        rdist[i] = min(rdist[i], rdist[i + 1] + 1); 
    }
    for(auto &x : vis){
        if(x.s = -1){
            x.s = 1e9; 
            for(int i = 2 * x.f; i < MAXP; i += x.f){
                x.s = min(x.s, rdist[i]); 
            }
        }
    }
    int ans = 0; 
    for(int i = 0; i < n; i++){
        int curr = v[i] - dist[v[i]]; 
        for(int j = 1; j * j <= curr; j++){
            if(curr % j == 0){
                dist[j] = 0; 
                dist[curr / j] = 0; 
            }
        }
        // cout << dist[v[i]] << ' ' << vis[v[i]] << '\n'; 
        ans += min(dist[v[i]], vis[v[i]]); 
    }
    cout << ans << '\n'; 
    return 0; 
}

Compilation message

sirni.cpp: In function 'int32_t main()':
sirni.cpp:52:16: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   52 |         if(x.s = -1){
      |            ~~~~^~~~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 198736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 140 ms 235340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 199404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 401 ms 242008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 105 ms 236116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 493 ms 241872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 308 ms 237604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 577 ms 242264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 590 ms 242280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 162 ms 236604 KB Output isn't correct
2 Halted 0 ms 0 KB -