Submission #1005741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005741		orcslop	Sirni (COCI17_sirni)	C++17	0 / 140	601 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]]++; 
    }
    for(auto x : vis){
        // cout << x.f << '\n'; 
        for(int i = x.f; i < MAXP; i += x.f){
            sieve[i]++; 
        }
    }
    // cout << sieve[6] << '\n'; 
    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] = dist[x.f - 1] + 1; 
    }
    sort(v, v + n, greater<int>()); 
    for(int i = 0; i < n; i++){
        int curr = v[i] - dist[v[i]]; 
        for(int j = 1; j * j <= curr; j++){
            dist[j] = dist[curr / j] = 0; 
            // dist[j] = min(dist[j], dist[v[i]]); 
            // dist[curr / j] = min(dist[curr / j], dist[v[i]]); 
        }
    }
    // for(int i = 0; i <= 15; i++){
    //     cout << i << ' ' << dist[i] << '\n'; 
    // }
    int ans = 0; 
    for(int i = 0; i < n; i++){
        ans += min({dist[v[i]], v[n - 1], dist[v[i] - 1] + 1}); 
    }
    cout << ans << '\n'; 
    return 0; 
}

• 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