| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 631309 | 2022-08-18T03:04:56 Z | SanguineChameleon | Brunhilda’s Birthday (BOI13_brunhilda) | C++14 | 913 ms | 168268 KB |
// BEGIN BOILERPLATE CODE
#include <bits/stdc++.h>
using namespace std;
#ifdef KAMIRULEZ
const bool kami_loc = true;
const long long kami_seed = 69420;
#else
const bool kami_loc = false;
const long long kami_seed = chrono::steady_clock::now().time_since_epoch().count();
#endif
const string kami_fi = "kamirulez.inp";
const string kami_fo = "kamirulez.out";
mt19937_64 kami_gen(kami_seed);
long long rand_range(long long rmin, long long rmax) {
uniform_int_distribution<long long> rdist(rmin, rmax);
return rdist(kami_gen);
}
void file_io(string fi, string fo) {
if (fi != "" && (!kami_loc || fi == kami_fi)) {
freopen(fi.c_str(), "r", stdin);
}
if (fo != "" && (!kami_loc || fo == kami_fo)) {
freopen(fo.c_str(), "w", stdout);
}
}
void set_up() {
if (kami_loc) {
file_io(kami_fi, kami_fo);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
}
void just_do_it();
void just_exec_it() {
if (kami_loc) {
auto pstart = chrono::steady_clock::now();
just_do_it();
auto pend = chrono::steady_clock::now();
long long ptime = chrono::duration_cast<chrono::milliseconds>(pend - pstart).count();
string bar(50, '=');
cout << '\n' << bar << '\n';
cout << "Time: " << ptime << " ms" << '\n';
}
else {
just_do_it();
}
}
int main() {
set_up();
just_exec_it();
return 0;
}
// END BOILERPLATE CODE
// BEGIN MAIN CODE
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
const int ms = 1e7 + 20;
const int inf = 1e9 + 20;
bool g[ms];
int pr[ms];
int p[ms];
int cc[ms];
int dp[ms];
int qz[ms];
int sz;
void just_do_it() {
int n, q;
cin >> n >> q;
p[1] = 1;
for (int i = 2; i < ms; i++) {
if (!p[i]) {
p[i] = i;
pr[sz++] = i;
}
for (int j = 0; j < sz; j++) {
if (i * pr[j] >= ms) {
break;
}
p[i * pr[j]] = pr[j];
if (i % pr[j] == 0) {
break;
}
}
}
for (int i = 0; i < n; i++) {
int d;
cin >> d;
g[d] = true;
}
cc[0] = n;
int lt = 0;
int rt = 0;
for (int i = 1; i < ms; i++) {
int f = -1;
int x = i;
while (x != 1) {
if (p[x] != f) {
f = p[x];
if (g[f]) {
cc[i]++;
cc[i - p[x]]--;
}
}
x /= p[x];
}
while (lt <= rt && !cc[qz[lt]]) {
lt++;
}
if (lt > rt) {
for (int j = i; j < ms; j++) {
dp[j] = inf;
}
break;
}
else {
dp[i] = dp[qz[lt]] + 1;
}
qz[++rt] = i;
}
for (int i = 0; i < q; i++) {
int d;
cin >> d;
if (dp[d] == inf) {
cout << "oo" << '\n';
}
else {
cout << dp[d] << '\n';
}
}
}
// END MAIN CODE
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 126 ms | 81160 KB | Output is correct |
| 2 | Correct | 660 ms | 159384 KB | Output is correct |
| 3 | Correct | 136 ms | 83268 KB | Output is correct |
| 4 | Correct | 598 ms | 159400 KB | Output is correct |
| 5 | Correct | 614 ms | 159528 KB | Output is correct |
| 6 | Correct | 122 ms | 81228 KB | Output is correct |
| 7 | Correct | 143 ms | 83276 KB | Output is correct |
| 8 | Correct | 177 ms | 88224 KB | Output is correct |
| 9 | Correct | 652 ms | 159396 KB | Output is correct |
| 10 | Correct | 653 ms | 159484 KB | Output is correct |
| 11 | Correct | 664 ms | 159376 KB | Output is correct |
| 12 | Correct | 606 ms | 159424 KB | Output is correct |
| 13 | Correct | 716 ms | 159436 KB | Output is correct |
| 14 | Correct | 733 ms | 159512 KB | Output is correct |
| 15 | Correct | 645 ms | 159568 KB | Output is correct |
| 16 | Correct | 631 ms | 159464 KB | Output is correct |
| 17 | Correct | 590 ms | 159392 KB | Output is correct |
| 18 | Correct | 594 ms | 159528 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 642 ms | 160336 KB | Output is correct |
| 2 | Correct | 654 ms | 168180 KB | Output is correct |
| 3 | Correct | 733 ms | 160416 KB | Output is correct |
| 4 | Correct | 692 ms | 159524 KB | Output is correct |
| 5 | Correct | 830 ms | 160712 KB | Output is correct |
| 6 | Correct | 624 ms | 159492 KB | Output is correct |
| 7 | Correct | 663 ms | 160260 KB | Output is correct |
| 8 | Correct | 780 ms | 159452 KB | Output is correct |
| 9 | Correct | 874 ms | 160756 KB | Output is correct |
| 10 | Correct | 825 ms | 160344 KB | Output is correct |
| 11 | Correct | 778 ms | 159952 KB | Output is correct |
| 12 | Correct | 751 ms | 159480 KB | Output is correct |
| 13 | Correct | 762 ms | 159960 KB | Output is correct |
| 14 | Correct | 735 ms | 159504 KB | Output is correct |
| 15 | Correct | 876 ms | 160148 KB | Output is correct |
| 16 | Correct | 649 ms | 168268 KB | Output is correct |
| 17 | Correct | 771 ms | 159512 KB | Output is correct |
| 18 | Correct | 853 ms | 161388 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 862 ms | 160532 KB | Output is correct |
| 2 | Correct | 732 ms | 160312 KB | Output is correct |
| 3 | Correct | 780 ms | 160248 KB | Output is correct |
| 4 | Correct | 824 ms | 159820 KB | Output is correct |
| 5 | Correct | 761 ms | 163932 KB | Output is correct |
| 6 | Correct | 888 ms | 159868 KB | Output is correct |
| 7 | Correct | 867 ms | 161836 KB | Output is correct |
| 8 | Correct | 854 ms | 160520 KB | Output is correct |
| 9 | Correct | 873 ms | 160504 KB | Output is correct |
| 10 | Correct | 803 ms | 159564 KB | Output is correct |
| 11 | Correct | 792 ms | 159572 KB | Output is correct |
| 12 | Correct | 865 ms | 159688 KB | Output is correct |
| 13 | Correct | 818 ms | 160152 KB | Output is correct |
| 14 | Correct | 742 ms | 160056 KB | Output is correct |
| 15 | Correct | 805 ms | 159624 KB | Output is correct |
| 16 | Correct | 783 ms | 159524 KB | Output is correct |
| 17 | Correct | 883 ms | 160220 KB | Output is correct |
| 18 | Correct | 784 ms | 160184 KB | Output is correct |
| 19 | Correct | 640 ms | 160192 KB | Output is correct |
| 20 | Correct | 723 ms | 160188 KB | Output is correct |
| 21 | Correct | 698 ms | 160024 KB | Output is correct |
| 22 | Correct | 844 ms | 161092 KB | Output is correct |
| 23 | Correct | 707 ms | 160652 KB | Output is correct |
| 24 | Correct | 644 ms | 159856 KB | Output is correct |
| 25 | Correct | 791 ms | 159932 KB | Output is correct |
| 26 | Correct | 774 ms | 159820 KB | Output is correct |
| 27 | Correct | 712 ms | 160780 KB | Output is correct |
| 28 | Correct | 652 ms | 159856 KB | Output is correct |
| 29 | Correct | 913 ms | 161156 KB | Output is correct |
| 30 | Correct | 825 ms | 160692 KB | Output is correct |
| 31 | Correct | 675 ms | 159948 KB | Output is correct |
| 32 | Correct | 745 ms | 159772 KB | Output is correct |
| 33 | Correct | 618 ms | 159948 KB | Output is correct |
| 34 | Correct | 793 ms | 161860 KB | Output is correct |
| 35 | Correct | 678 ms | 159872 KB | Output is correct |
| 36 | Correct | 791 ms | 161220 KB | Output is correct |
| 37 | Correct | 673 ms | 163916 KB | Output is correct |
| 38 | Correct | 832 ms | 159884 KB | Output is correct |
| 39 | Correct | 651 ms | 159872 KB | Output is correct |
| 40 | Correct | 816 ms | 159836 KB | Output is correct |
| 41 | Correct | 790 ms | 162724 KB | Output is correct |
| 42 | Correct | 718 ms | 159864 KB | Output is correct |