| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 734619 | 2023-05-02T17:19:17 Z | DAleksa | Brunhilda’s Birthday (BOI13_brunhilda) | C++17 | 751 ms | 262144 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 15000000 + 10;
int n, q;
vector<int> p;
vector<int> v;
int cnt[N];
int prime[N];
int prv[N];
int dp[N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
p.resize(n);
for(int i = 0; i < n; i++) cin >> p[i];
for(int i = p.size() - 1; i >= 0; i--) {
for(int j = p[i]; j < N; j += p[i]) {
if(prime[j] == 0) {
cnt[j]++;
prime[j] = p[i];
}
}
}
cnt[0]++;
prime[0] = p.back();
for(int i = 0; i < N; i++) for(int j = 0; j < cnt[i]; j++) v.push_back(i);
int j = 0;
for(int i = 1; i < N; i++) {
while(v[j] + prime[v[j]] <= i) j++;
prv[i] = v[j];
}
for(int i = 1; i < N; i++) {
if(prv[i] == i) dp[i] = -1;
else dp[i] = dp[prv[i]] + 1;
}
while(q--) {
int x;
cin >> x;
if(x < p.back()) cout << "1\n";
else if(dp[x] == -1) cout << "oo\n";
else cout << dp[x] << "\n";
}
return 0;
}
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 230 ms | 245136 KB | Output isn't correct |
| 2 | Runtime error | 340 ms | 262144 KB | Execution killed with signal 9 |
| 3 | Runtime error | 302 ms | 262144 KB | Execution killed with signal 9 |
| 4 | Correct | 229 ms | 239640 KB | Output is correct |
| 5 | Correct | 286 ms | 250732 KB | Output is correct |
| 6 | Incorrect | 247 ms | 245304 KB | Output isn't correct |
| 7 | Runtime error | 331 ms | 262144 KB | Execution killed with signal 9 |
| 8 | Runtime error | 325 ms | 262144 KB | Execution killed with signal 9 |
| 9 | Runtime error | 418 ms | 262144 KB | Execution killed with signal 9 |
| 10 | Runtime error | 430 ms | 262144 KB | Execution killed with signal 9 |
| 11 | Runtime error | 421 ms | 262144 KB | Execution killed with signal 9 |
| 12 | Correct | 175 ms | 238344 KB | Output is correct |
| 13 | Runtime error | 622 ms | 262144 KB | Execution killed with signal 9 |
| 14 | Runtime error | 599 ms | 262144 KB | Execution killed with signal 9 |
| 15 | Runtime error | 411 ms | 262144 KB | Execution killed with signal 9 |
| 16 | Runtime error | 347 ms | 262144 KB | Execution killed with signal 9 |
| 17 | Correct | 293 ms | 250592 KB | Output is correct |
| 18 | Correct | 186 ms | 239512 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 275 ms | 245200 KB | Output is correct |
| 2 | Correct | 285 ms | 248788 KB | Output is correct |
| 3 | Runtime error | 751 ms | 262144 KB | Execution killed with signal 9 |
| 4 | Correct | 367 ms | 258932 KB | Output is correct |
| 5 | Runtime error | 553 ms | 262144 KB | Execution killed with signal 9 |
| 6 | Runtime error | 354 ms | 262144 KB | Execution killed with signal 9 |
| 7 | Correct | 249 ms | 245108 KB | Output is correct |
| 8 | Correct | 354 ms | 256308 KB | Output is correct |
| 9 | Runtime error | 603 ms | 262144 KB | Execution killed with signal 9 |
| 10 | Runtime error | 619 ms | 262144 KB | Execution killed with signal 9 |
| 11 | Runtime error | 702 ms | 262144 KB | Execution killed with signal 9 |
| 12 | Runtime error | 522 ms | 262144 KB | Execution killed with signal 9 |
| 13 | Correct | 245 ms | 249612 KB | Output is correct |
| 14 | Correct | 365 ms | 258920 KB | Output is correct |
| 15 | Runtime error | 617 ms | 262144 KB | Execution killed with signal 9 |
| 16 | Correct | 281 ms | 248796 KB | Output is correct |
| 17 | Runtime error | 640 ms | 262144 KB | Execution killed with signal 9 |
| 18 | Runtime error | 551 ms | 262144 KB | Execution killed with signal 9 |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 532 ms | 262144 KB | Execution killed with signal 9 |
| 2 | Runtime error | 585 ms | 262144 KB | Execution killed with signal 9 |
| 3 | Runtime error | 623 ms | 262144 KB | Execution killed with signal 9 |
| 4 | Runtime error | 460 ms | 262144 KB | Execution killed with signal 9 |
| 5 | Correct | 288 ms | 249860 KB | Output is correct |
| 6 | Runtime error | 522 ms | 262144 KB | Execution killed with signal 9 |
| 7 | Runtime error | 506 ms | 262144 KB | Execution killed with signal 9 |
| 8 | Runtime error | 523 ms | 262144 KB | Execution killed with signal 9 |
| 9 | Runtime error | 529 ms | 262144 KB | Execution killed with signal 9 |
| 10 | Runtime error | 485 ms | 262144 KB | Execution killed with signal 9 |
| 11 | Runtime error | 457 ms | 262144 KB | Execution killed with signal 9 |
| 12 | Runtime error | 522 ms | 262144 KB | Execution killed with signal 9 |
| 13 | Runtime error | 566 ms | 262144 KB | Execution killed with signal 9 |
| 14 | Runtime error | 434 ms | 262144 KB | Execution killed with signal 9 |
| 15 | Runtime error | 522 ms | 262144 KB | Execution killed with signal 9 |
| 16 | Runtime error | 567 ms | 262144 KB | Execution killed with signal 9 |
| 17 | Runtime error | 514 ms | 262144 KB | Execution killed with signal 9 |
| 18 | Runtime error | 599 ms | 262144 KB | Execution killed with signal 9 |
| 19 | Correct | 254 ms | 260008 KB | Output is correct |
| 20 | Runtime error | 601 ms | 262144 KB | Execution killed with signal 9 |
| 21 | Runtime error | 455 ms | 262144 KB | Execution killed with signal 9 |
| 22 | Runtime error | 612 ms | 262144 KB | Execution killed with signal 9 |
| 23 | Correct | 345 ms | 251752 KB | Output is correct |
| 24 | Correct | 261 ms | 246188 KB | Output is correct |
| 25 | Runtime error | 502 ms | 262144 KB | Execution killed with signal 9 |
| 26 | Runtime error | 488 ms | 262144 KB | Execution killed with signal 9 |
| 27 | Runtime error | 615 ms | 262144 KB | Execution killed with signal 9 |
| 28 | Correct | 308 ms | 256244 KB | Output is correct |
| 29 | Runtime error | 564 ms | 262144 KB | Execution killed with signal 9 |
| 30 | Runtime error | 531 ms | 262144 KB | Execution killed with signal 9 |
| 31 | Correct | 326 ms | 257832 KB | Output is correct |
| 32 | Runtime error | 358 ms | 262144 KB | Execution killed with signal 9 |
| 33 | Correct | 210 ms | 241772 KB | Output is correct |
| 34 | Runtime error | 498 ms | 262144 KB | Execution killed with signal 9 |
| 35 | Correct | 304 ms | 257296 KB | Output is correct |
| 36 | Runtime error | 588 ms | 262144 KB | Execution killed with signal 9 |
| 37 | Correct | 294 ms | 249864 KB | Output is correct |
| 38 | Runtime error | 534 ms | 262144 KB | Execution killed with signal 9 |
| 39 | Correct | 292 ms | 249244 KB | Output is correct |
| 40 | Runtime error | 503 ms | 262144 KB | Execution killed with signal 9 |
| 41 | Runtime error | 477 ms | 262144 KB | Execution killed with signal 9 |
| 42 | Runtime error | 564 ms | 262144 KB | Execution killed with signal 9 |