Submission #1005740

# Submission time Handle Problem Language Result Execution time Memory
1005740 2024-06-23T01:37:56 Z orcslop Sirni (COCI17_sirni) C++17
0 / 140
632 ms 243056 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]]++; 
    }
    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 += dist[v[i]]; 
    }
    cout << ans << '\n'; 
    return 0; 
}
# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 175956 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 135 ms 235348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 176976 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 360 ms 242472 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 115 ms 236128 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 414 ms 242516 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 214 ms 237904 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 608 ms 243056 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 632 ms 242936 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 170 ms 236624 KB Output isn't correct
2 Halted 0 ms 0 KB -