oj.uz

Submission #868587

# Submission time Handle Problem Language Result Execution time Memory
868587 2023-10-31T22:50:52 Z Karoot Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 429 ms 120492 KB 
#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
 
#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()
 
using namespace std;
 
typedef long long ll;
 
ll linf = 1e15+1;
 
inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}
 
const int MAXN = 1e7+1;
 
pair<int, int> dp[MAXN];
int distFrom[MAXN];
int biggestPrime;
 
 
void initDistFrom(int latestW){
    for (int i = 1; i < biggestPrime; i++){
        distFrom[i] = 1;
    }
 
    for (int i = biggestPrime; i <= MAXN; i++){
        if (dp[i].second == 0){
            distFrom[i] = 0;
            continue;
        }
        distFrom[i] = (distFrom[i-i%dp[i].second] == 0 ? 0 : distFrom[i-i%dp[i].second]+1);
    }
}
 
 
int main(){
    scoobydoobydoo();
    int n, q; cin >> n >> q;
    vector<int> primez(n);
    for (int i = 0; i < n; i++){
        cin >> primez[i];
    }
 
    biggestPrime = primez[n-1];
 
    int latest = -1;
    int latestW = -1;
 
    for (int e : primez){
        int worth = ((int)1e7)%e;
        if (worth >= latestW){
            latestW = worth;
            latest = e;
        }
    }
 
 
    vector<int> ans;
 
    for (int i = n-1; i >= 0; i--){
        for (int e = primez[i]-1; e <= MAXN; e += primez[i]){
            if (!dp[e].first){
                dp[e] = {primez[i]-1, primez[i]};
            }
        }
    }
 
    
    for (int i = MAXN; i >= 0; i--){
        if (dp[i].first){
            if (i%latest > dp[i].first){
                dp[i].first = i%latest;
                dp[i].second = latest;
            } else {
                latest = dp[i].second;
            }
        } else {
            dp[i] = {i%latest, latest};
        }
    }
 
    initDistFrom(latestW);
 
    while (q--){
        int x; cin >> x;
        if (distFrom[x] == 0)ans.push_back(-1);
        else ans.push_back(distFrom[x]);
    }
 
    for (auto& e : ans){
        if (e == -1)cout << "oo" << endl;
        else cout << e << endl;
    }
 
 
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 117836 KB Output is correct
2 Correct 195 ms 117856 KB Output is correct
3 Correct 193 ms 118096 KB Output is correct
4 Correct 173 ms 117844 KB Output is correct
5 Correct 188 ms 117844 KB Output is correct
6 Correct 185 ms 118096 KB Output is correct
7 Correct 195 ms 117844 KB Output is correct
8 Correct 202 ms 117756 KB Output is correct
9 Correct 234 ms 117832 KB Output is correct
10 Correct 263 ms 117844 KB Output is correct
11 Correct 247 ms 117644 KB Output is correct
12 Correct 156 ms 117628 KB Output is correct
13 Correct 309 ms 117648 KB Output is correct
14 Correct 313 ms 118100 KB Output is correct
15 Correct 208 ms 117844 KB Output is correct
16 Correct 198 ms 117844 KB Output is correct
17 Correct 194 ms 117840 KB Output is correct
18 Correct 165 ms 117844 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 117772 KB Output is correct
2 Correct 115 ms 118864 KB Output is correct
3 Correct 293 ms 118512 KB Output is correct
4 Correct 175 ms 117664 KB Output is correct
5 Correct 232 ms 118232 KB Output is correct
6 Correct 169 ms 117648 KB Output is correct
7 Correct 140 ms 117924 KB Output is correct
8 Correct 183 ms 117644 KB Output is correct
9 Correct 261 ms 118404 KB Output is correct
10 Correct 287 ms 118592 KB Output is correct
11 Correct 288 ms 118228 KB Output is correct
12 Correct 231 ms 117652 KB Output is correct
13 Correct 146 ms 117844 KB Output is correct
14 Correct 176 ms 117844 KB Output is correct
15 Correct 266 ms 118188 KB Output is correct
16 Correct 111 ms 118876 KB Output is correct
17 Correct 312 ms 117844 KB Output is correct
18 Correct 254 ms 118772 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 119060 KB Output is correct
2 Correct 345 ms 118860 KB Output is correct
3 Correct 364 ms 119256 KB Output is correct
4 Correct 356 ms 119252 KB Output is correct
5 Correct 248 ms 120280 KB Output is correct
6 Correct 407 ms 119372 KB Output is correct
7 Correct 287 ms 119692 KB Output is correct
8 Correct 318 ms 119360 KB Output is correct
9 Correct 310 ms 119092 KB Output is correct
10 Correct 251 ms 118096 KB Output is correct
11 Correct 243 ms 118096 KB Output is correct
12 Correct 295 ms 118228 KB Output is correct
13 Correct 395 ms 119516 KB Output is correct
14 Correct 368 ms 119640 KB Output is correct
15 Correct 318 ms 118356 KB Output is correct
16 Correct 324 ms 118352 KB Output is correct
17 Correct 268 ms 118476 KB Output is correct
18 Correct 330 ms 118860 KB Output is correct
19 Correct 168 ms 118256 KB Output is correct
20 Correct 364 ms 119260 KB Output is correct
21 Correct 385 ms 119764 KB Output is correct
22 Correct 407 ms 120280 KB Output is correct
23 Correct 270 ms 119496 KB Output is correct
24 Correct 265 ms 119340 KB Output is correct
25 Correct 356 ms 119304 KB Output is correct
26 Correct 354 ms 119172 KB Output is correct
27 Correct 363 ms 119768 KB Output is correct
28 Correct 274 ms 119636 KB Output is correct
29 Correct 380 ms 120276 KB Output is correct
30 Correct 373 ms 120236 KB Output is correct
31 Correct 267 ms 119252 KB Output is correct
32 Correct 300 ms 119256 KB Output is correct
33 Correct 250 ms 119644 KB Output is correct
34 Correct 277 ms 119872 KB Output is correct
35 Correct 277 ms 119300 KB Output is correct
36 Correct 411 ms 120492 KB Output is correct
37 Correct 253 ms 120276 KB Output is correct
38 Correct 389 ms 119244 KB Output is correct
39 Correct 280 ms 119256 KB Output is correct
40 Correct 357 ms 119336 KB Output is correct
41 Correct 264 ms 120224 KB Output is correct
42 Correct 429 ms 119504 KB Output is correct