oj.uz

Submission #1005741

# Submission time Handle Problem Language Result Execution time Memory
1005741 2024-06-23T01:45:26 Z orcslop Sirni (COCI17_sirni) C++17
0 / 140
 601 ms 242512 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 += min({dist[v[i]], v[n - 1], dist[v[i] - 1] + 1}); 
    }
    cout << ans << '\n'; 
    return 0; 
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 201808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 106 ms 235344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 203956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 361 ms 242008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 236112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 386 ms 241748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 201 ms 237652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 601 ms 242512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 555 ms 242280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 151 ms 236628 KB Output isn't correct
2 Halted 0 ms 0 KB -