| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 577107 | 2022-06-14T05:47:01 Z | goodluck2020 | Brunhilda’s Birthday (BOI13_brunhilda) | C++14 | 244 ms | 80264 KB |
#define INPFILE "GROUP.INP"
#define OUTFILE "GROUP.OUT"
#include <bits/stdc++.h>
using namespace std;
bool maximise(int &a, int b) { return a < b ? a = b, true : false; }
const int MAX = 1e7 + 1, INF = 0x3f3f3f3f;
int n, Q, rmax[MAX], f[MAX];
bool used[MAX];
void input(void) {
cin >> n >> Q;
memset(rmax, 0, sizeof rmax);
for (int i = 1; i <= n; i++) {
int x; cin >> x;
if (used[x]) continue;
for (int j = x - 1; j < MAX; j += x)
maximise(rmax[j], x - 1);
maximise(rmax[MAX - 1], (MAX - 1) % x);
}
for (int i = MAX - 2; i >= 0; i--)
maximise(rmax[i], rmax[i + 1] - 1);
}
int main(void) {
if (fopen(INPFILE, "r")) {
freopen(INPFILE, "r", stdin);
freopen(OUTFILE, "w", stdout);
}
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
input();
memset(f, 0x3f, sizeof f); f[0] = 0;
for (int i = 1; i < MAX; i++)
f[i] = f[i - rmax[i]] + 1;
while (Q--) {
int x; cin >> x;
int ans = f[x];
if (ans >= INF) cout << "oo\n";
else cout << ans << '\n';
}
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 76 ms | 78540 KB | Output is correct |
| 2 | Correct | 87 ms | 78492 KB | Output is correct |
| 3 | Correct | 82 ms | 78500 KB | Output is correct |
| 4 | Correct | 74 ms | 78532 KB | Output is correct |
| 5 | Correct | 85 ms | 78492 KB | Output is correct |
| 6 | Correct | 78 ms | 78596 KB | Output is correct |
| 7 | Correct | 99 ms | 78540 KB | Output is correct |
| 8 | Correct | 87 ms | 78488 KB | Output is correct |
| 9 | Correct | 103 ms | 78488 KB | Output is correct |
| 10 | Correct | 113 ms | 78508 KB | Output is correct |
| 11 | Correct | 106 ms | 78532 KB | Output is correct |
| 12 | Correct | 72 ms | 78540 KB | Output is correct |
| 13 | Correct | 189 ms | 78540 KB | Output is correct |
| 14 | Correct | 173 ms | 78536 KB | Output is correct |
| 15 | Correct | 97 ms | 78488 KB | Output is correct |
| 16 | Correct | 90 ms | 78488 KB | Output is correct |
| 17 | Correct | 94 ms | 78664 KB | Output is correct |
| 18 | Correct | 72 ms | 78548 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 81 ms | 78676 KB | Output is correct |
| 2 | Correct | 101 ms | 79276 KB | Output is correct |
| 3 | Correct | 210 ms | 78964 KB | Output is correct |
| 4 | Correct | 97 ms | 78508 KB | Output is correct |
| 5 | Correct | 151 ms | 78932 KB | Output is correct |
| 6 | Correct | 91 ms | 78528 KB | Output is correct |
| 7 | Correct | 81 ms | 78668 KB | Output is correct |
| 8 | Correct | 95 ms | 78596 KB | Output is correct |
| 9 | Correct | 170 ms | 79088 KB | Output is correct |
| 10 | Correct | 220 ms | 78968 KB | Output is correct |
| 11 | Correct | 200 ms | 78792 KB | Output is correct |
| 12 | Correct | 120 ms | 78500 KB | Output is correct |
| 13 | Correct | 78 ms | 78608 KB | Output is correct |
| 14 | Correct | 106 ms | 78668 KB | Output is correct |
| 15 | Correct | 176 ms | 78848 KB | Output is correct |
| 16 | Correct | 98 ms | 79188 KB | Output is correct |
| 17 | Correct | 172 ms | 78504 KB | Output is correct |
| 18 | Correct | 178 ms | 79432 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 181 ms | 79308 KB | Output is correct |
| 2 | Correct | 216 ms | 79180 KB | Output is correct |
| 3 | Correct | 215 ms | 79428 KB | Output is correct |
| 4 | Correct | 150 ms | 79432 KB | Output is correct |
| 5 | Correct | 118 ms | 80264 KB | Output is correct |
| 6 | Correct | 185 ms | 79688 KB | Output is correct |
| 7 | Correct | 179 ms | 79816 KB | Output is correct |
| 8 | Correct | 176 ms | 79304 KB | Output is correct |
| 9 | Correct | 180 ms | 79240 KB | Output is correct |
| 10 | Correct | 143 ms | 78664 KB | Output is correct |
| 11 | Correct | 127 ms | 78788 KB | Output is correct |
| 12 | Correct | 170 ms | 78804 KB | Output is correct |
| 13 | Correct | 206 ms | 79696 KB | Output is correct |
| 14 | Correct | 142 ms | 79812 KB | Output is correct |
| 15 | Correct | 171 ms | 78788 KB | Output is correct |
| 16 | Correct | 189 ms | 78796 KB | Output is correct |
| 17 | Correct | 187 ms | 79116 KB | Output is correct |
| 18 | Correct | 244 ms | 79108 KB | Output is correct |
| 19 | Correct | 86 ms | 78732 KB | Output is correct |
| 20 | Correct | 212 ms | 79432 KB | Output is correct |
| 21 | Correct | 163 ms | 80004 KB | Output is correct |
| 22 | Correct | 232 ms | 80204 KB | Output is correct |
| 23 | Correct | 116 ms | 79820 KB | Output is correct |
| 24 | Correct | 109 ms | 79564 KB | Output is correct |
| 25 | Correct | 157 ms | 79556 KB | Output is correct |
| 26 | Correct | 142 ms | 79432 KB | Output is correct |
| 27 | Correct | 234 ms | 79752 KB | Output is correct |
| 28 | Correct | 99 ms | 79728 KB | Output is correct |
| 29 | Correct | 234 ms | 80208 KB | Output is correct |
| 30 | Correct | 198 ms | 80016 KB | Output is correct |
| 31 | Correct | 117 ms | 79688 KB | Output is correct |
| 32 | Correct | 123 ms | 79556 KB | Output is correct |
| 33 | Correct | 110 ms | 79460 KB | Output is correct |
| 34 | Correct | 176 ms | 79860 KB | Output is correct |
| 35 | Correct | 108 ms | 79600 KB | Output is correct |
| 36 | Correct | 228 ms | 80200 KB | Output is correct |
| 37 | Correct | 128 ms | 80244 KB | Output is correct |
| 38 | Correct | 196 ms | 79628 KB | Output is correct |
| 39 | Correct | 113 ms | 79692 KB | Output is correct |
| 40 | Correct | 161 ms | 79556 KB | Output is correct |
| 41 | Correct | 153 ms | 79816 KB | Output is correct |
| 42 | Correct | 202 ms | 79688 KB | Output is correct |