제출 #1005747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1005747		orcslop	Sirni (COCI17_sirni)	C++17	0 / 140	636 ms	242512 KiB

sirni

#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; 
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14