QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #466115 | #7277. Bring Down the | Forested | 5 | 1219ms | 152972kb | C++17 | 2.0kb | 2024-07-07 16:05:24 | 2024-07-07 16:05:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = V<V<T>>;
template <typename T>
using VVV = VV<V<T>>;
template <typename T>
using VVVV = VVV<V<T>>;
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, l, r) for (i32 i = (i32)(l); i < (i32)(r); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
#define PER3(i, l, r) for (i32 i = (i32)(r) - 1; i >= (i32)(l); --i)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define ALL(x) begin(x), end(x)
#define LEN(x) (i32)(size(x))
template <typename T>
bool chmin(T &x, const T &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
int main() {
i32 s, q;
cin >> s >> q;
constexpr i32 D = 76;
VVVV<i32> is_first(D, VVV<i32>(D, VV<i32>(D, V<i32>(D, -1))));
auto rec = [&](auto rec, i32 ch, i32 fh, i32 cg, i32 fg) -> bool {
if (ch <= 0) {
return false;
}
if (is_first[ch][fh][cg][fg] != -1) {
return is_first[ch][fh][cg][fg];
}
bool ans = false;
i32 dmg = max(0, ch - s * fg);
if (dmg > 0 && !rec(rec, cg - dmg, fg, ch, fh)) {
ans = true;
}
if (fg > 0 && !rec(rec, cg, fg - 1, ch, fh)) {
ans = true;
}
return is_first[ch][fh][cg][fg] = ans;
};
REP(i, q) {
i32 ch, fh, cg, fg;
cin >> ch >> fh >> cg >> fg;
assert(ch <= D && fh <= D && cg <= D && fg <= D);
if (rec(rec, ch, fh, cg, fg)) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 15ms
memory: 152860kb
input:
17 2 42 1 33 1 42 1 33 7
output:
YES NO
result:
ok 2 token(s): yes count is 1, no count is 1
Test #2:
score: 0
Accepted
time: 1183ms
memory: 152876kb
input:
2 250000 75 16 56 55 50 9 49 60 18 67 62 5 30 54 61 39 22 39 42 31 26 30 55 1 23 30 53 16 55 13 6 44 69 8 58 72 53 7 60 12 29 14 26 34 37 64 24 71 19 3 40 1 64 13 33 65 67 24 68 3 64 17 50 66 71 6 62 13 15 29 26 24 51 30 34 45 46 5 40 72 54 52 60 49 35 21 18 30 39 31 35 34 30 74 72 5 74 12 6 15 11 4...
output:
NO NO YES YES NO YES NO NO NO YES NO NO NO NO YES NO YES NO NO NO YES NO NO YES YES NO YES YES NO YES YES NO NO YES NO NO YES YES YES NO NO NO NO YES YES YES YES NO YES NO YES NO YES YES YES YES YES NO NO NO YES NO NO NO YES YES NO YES NO YES NO YES YES YES YES NO YES YES YES NO YES NO NO NO NO YES ...
result:
ok 250000 token(s): yes count is 122161, no count is 127839
Test #3:
score: 0
Accepted
time: 1087ms
memory: 152744kb
input:
7 250000 14 72 33 41 43 64 63 62 34 14 69 9 19 75 21 57 47 6 43 53 19 53 58 46 50 49 49 74 30 75 53 68 36 42 53 14 70 40 52 73 70 44 75 44 38 75 72 46 11 45 20 10 25 67 35 60 54 27 14 28 53 35 26 44 10 20 60 13 61 2 41 6 54 3 66 8 43 34 69 31 52 16 3 41 53 62 33 66 15 75 27 32 73 22 22 44 66 15 56 1...
output:
YES NO YES YES NO YES NO YES YES NO YES YES YES YES YES NO NO YES NO YES NO NO YES NO NO YES NO YES NO YES NO YES YES YES YES YES NO YES YES NO YES YES NO YES YES NO NO YES NO NO NO YES NO YES YES NO NO NO NO NO YES NO YES YES YES NO YES YES NO NO NO NO NO YES YES NO YES NO YES NO NO YES NO NO NO NO...
result:
ok 250000 token(s): yes count is 123236, no count is 126764
Test #4:
score: 0
Accepted
time: 735ms
memory: 152828kb
input:
42 250000 9 44 75 43 56 10 46 11 25 22 40 22 54 4 49 5 4 22 34 16 69 59 72 59 66 75 74 31 5 10 57 10 11 48 36 46 7 40 56 14 32 68 5 74 66 25 59 40 10 6 20 7 48 25 73 24 54 41 51 56 71 32 47 55 17 3 26 10 20 49 8 51 44 17 43 35 75 18 69 33 72 8 74 43 45 75 66 19 56 73 68 15 47 56 57 57 39 69 20 70 7 ...
output:
NO NO YES NO NO YES YES NO YES YES NO NO NO YES NO NO NO NO NO NO NO YES YES NO YES YES YES NO NO YES NO NO YES NO YES NO NO YES NO NO YES NO NO NO NO NO NO NO YES NO YES YES YES NO NO NO YES YES YES YES YES NO NO YES YES NO NO NO NO YES YES NO NO NO NO NO YES NO YES YES NO YES YES NO NO YES NO YES ...
result:
ok 250000 token(s): yes count is 118956, no count is 131044
Test #5:
score: 0
Accepted
time: 1184ms
memory: 152776kb
input:
74 250000 29 38 74 53 17 75 67 32 10 17 14 74 7 35 60 74 18 61 33 14 11 75 47 46 5 66 54 57 11 19 38 35 45 1 66 51 3 57 71 35 48 75 59 48 75 75 75 65 51 54 15 57 6 11 25 65 10 6 36 4 43 29 34 36 32 75 19 59 11 11 41 39 19 55 36 74 44 1 69 2 11 49 39 30 62 75 49 14 47 5 53 71 7 60 38 34 48 75 11 43 7...
output:
NO YES NO NO YES YES NO NO NO NO YES YES NO NO YES NO YES NO NO NO YES YES NO YES YES YES NO NO YES NO NO NO YES NO YES YES NO YES YES YES YES NO NO YES YES YES NO NO YES YES YES NO YES NO YES NO NO YES YES YES NO YES NO NO YES YES YES NO YES YES YES YES YES NO YES YES NO YES YES YES YES NO YES NO N...
result:
ok 250000 token(s): yes count is 107243, no count is 142757
Test #6:
score: 0
Accepted
time: 391ms
memory: 152876kb
input:
33 250000 42 63 17 64 48 31 9 35 46 64 75 15 42 14 16 17 3 37 49 15 70 39 16 43 52 2 8 8 12 12 57 9 36 42 75 1 9 60 30 58 47 71 75 69 75 7 3 30 45 51 24 52 14 15 2 25 55 35 2 53 68 32 31 34 69 43 56 45 44 68 75 57 29 36 2 55 56 61 5 71 36 55 75 21 38 73 75 69 61 72 75 24 67 10 74 10 48 28 28 30 47 6...
output:
YES YES YES NO YES NO NO NO YES YES YES YES YES NO YES NO NO YES NO YES YES YES YES YES NO NO NO NO YES YES YES NO YES YES YES NO YES YES NO NO NO NO YES YES YES NO NO YES NO NO NO NO YES NO NO NO NO YES NO NO NO YES YES YES YES YES NO NO YES NO NO NO YES NO YES NO NO NO NO NO NO YES NO YES YES NO Y...
result:
ok 250000 token(s): yes count is 115599, no count is 134401
Test #7:
score: 0
Accepted
time: 384ms
memory: 152812kb
input:
20 250000 24 13 65 12 8 13 74 5 13 68 67 65 70 58 55 60 54 39 30 41 75 45 20 72 1 27 55 0 4 35 75 18 2 48 75 21 49 70 54 71 9 25 75 37 75 8 72 72 74 0 17 3 1 51 34 18 8 7 28 5 66 13 34 16 65 2 58 3 3 45 49 33 33 15 70 13 53 36 75 6 15 75 55 72 7 0 64 74 75 30 21 55 75 4 39 65 67 21 75 9 47 22 20 23 ...
output:
NO YES NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO NO YES YES YES NO NO NO YES YES NO YES YES YES YES YES NO YES YES YES NO NO YES NO NO NO NO NO NO NO YES YES NO YES NO YES NO YES NO NO NO NO YES NO YES NO YES YES YES YES NO YES YES NO YES NO YES YES NO YES NO YES NO YES NO NO YES YES NO YES NO...
result:
ok 250000 token(s): yes count is 118095, no count is 131905
Test #8:
score: 0
Accepted
time: 440ms
memory: 152828kb
input:
10 250000 50 31 58 32 17 66 46 63 8 39 35 36 75 42 49 64 28 68 75 9 3 73 10 71 64 54 23 58 33 32 16 35 8 31 63 24 51 7 75 65 60 11 38 15 12 75 75 3 4 52 28 45 24 54 2 71 44 39 24 42 46 41 75 4 1 39 74 3 75 9 41 48 75 9 61 72 58 44 74 42 66 34 28 38 64 30 72 29 34 46 62 44 75 6 17 68 29 16 1 45 63 38...
output:
NO YES YES NO YES YES YES NO YES NO NO YES YES NO NO YES NO NO NO YES YES YES NO NO NO YES NO YES YES YES NO YES YES YES YES NO NO YES NO NO YES NO YES NO NO YES YES NO NO YES NO NO YES YES NO YES YES NO NO NO NO YES NO YES NO NO YES YES YES YES YES NO YES NO YES NO NO NO NO NO YES YES YES YES NO NO...
result:
ok 250000 token(s): yes count is 123426, no count is 126574
Test #9:
score: 0
Accepted
time: 1219ms
memory: 152896kb
input:
3 250000 44 27 71 1 61 15 13 29 48 7 36 37 23 71 28 11 39 10 14 6 24 64 39 29 48 28 23 58 22 14 34 64 36 55 29 45 5 55 69 38 56 48 56 63 67 61 24 44 38 6 47 38 3 22 6 59 7 71 4 41 34 8 55 63 53 56 43 7 5 51 5 75 53 72 8 14 40 37 42 14 58 19 70 50 71 13 56 52 42 12 37 62 73 19 58 24 64 63 46 64 46 31...
output:
YES YES NO YES YES YES NO NO YES NO NO YES NO NO YES NO YES NO YES YES NO NO NO YES YES YES YES YES NO NO NO NO YES YES YES YES NO YES YES YES YES NO NO YES NO NO YES YES NO YES NO YES YES NO YES YES YES NO NO YES YES YES NO YES NO NO YES YES NO NO NO YES NO NO YES NO NO NO NO NO YES NO NO YES NO NO...
result:
ok 250000 token(s): yes count is 130142, no count is 119858
Subtask #2:
score: 0
Runtime Error
Dependency #1:
100%
Accepted
Test #10:
score: 5
Accepted
time: 31ms
memory: 152972kb
input:
17 2 42 1 33 1 42 1 33 7
output:
YES NO
result:
ok 2 token(s): yes count is 1, no count is 1
Test #11:
score: -5
Runtime Error
input:
3 250000 266 36 105 90 207 149 109 198 246 93 275 84 12 300 16 299 292 6 137 73 20 300 242 227 1 300 107 245 269 148 177 179 90 300 114 292 254 152 191 173 271 25 223 82 92 133 72 140 227 72 30 138 50 94 285 16 211 60 2 165 11 4 9 5 15 106 290 15 96 26 29 49 299 139 2 288 258 233 58 300 2 92 180 4 2...
output:
result:
Subtask #3:
score: 0
Runtime Error
Test #28:
score: 0
Runtime Error
input:
1 250000 554333015044 833858497873 833858497874 554333015044 655160857180 306396306924 306396306917 655160857187 374728598365 176680698490 176680698490 374728598365 764650258714 835600427315 835600427309 764650258720 521594231110 318048536486 318048536482 521594231115 273627794040 449769302710 10899...
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Runtime Error
Dependency #1:
100%
Accepted
Test #102:
score: 20
Accepted
time: 26ms
memory: 152972kb
input:
17 2 42 1 33 1 42 1 33 7
output:
YES NO
result:
ok 2 token(s): yes count is 1, no count is 1
Test #103:
score: -20
Runtime Error
input:
42 250000 4872 44 1889 116 2940 47 1989 70 3401 74 3146 81 629 27 988 19 2765 125 4409 86 2056 125 4578 65 4953 9 118 125 486576003099 110 843475701009 97 5078 105 4242 125 121 70 71 72 313361668603 101 507029830192 68 3570 94 2302 125 808028848732 24 964525600627 54 3276 39 1670 78 1436 115 1049 12...
output:
result:
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%