QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #123464 | #90. Fishing Game | bashkort# | 100 ✓ | 936ms | 196856kb | C++20 | 3.1kb | 2023-07-12 16:48:55 | 2024-07-04 00:37:11 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 1e9 + 7, N = 101;
int dp[2 * N][2 * N][2 * N][2][3];
int pos[3 * N];
void madd(int &x, const int &y) {
if ((x += y) >= MOD) {
x -= MOD;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, test = 1;
cin >> n >> test;
while (test--) {
memset(dp, 0, sizeof(dp));
memset(pos, 0, sizeof(pos));
for (int t = 1; t <= 3; ++t) {
for (int i = 1; i <= 2 * n; ++i) {
int x;
cin >> x;
pos[--x] ^= t;
}
}
int isa = 0, isb = 0, isc = 0;
for (int i = 0; i < 3 * n; ++i) {
if (pos[i]) {
if (pos[i] == 3) {
isa += 1;
} else if (pos[i] == 1) {
isb += 1;
} else {
assert(pos[i] == 2);
isc += 1;
}
}
}
dp[isa][isb][isc][0][0] = 1;
for (int sum = isa + isb + isc; sum > 0; --sum) {
int s[3]{};
for (int w = 1; w >= 0; --w) {
for (int m = 0; m < 3; ++m) {
int nxt = m == 2 ? 0 : m + 1;
int prv = m == 0 ? 2 : m - 1;
for (s[0] = 0; s[0] <= 2 * n; ++s[0]) {
for (s[1] = 0; s[1] <= 2 * n; ++s[1]) {
s[2] = sum - s[0] - s[1];
if (s[2] < 0 || s[2] > 2 * n) {
continue;
}
int x = dp[s[0]][s[1]][s[2]][w][m];
if (x == 0) {
continue;
}
if (s[m]) {
madd(dp[s[0] - (m == 0)][s[1] - (m == 1)][s[2] - (m == 2)][1 * (m != 2)][nxt],
1LL * x * s[m] % MOD);
}
if (w == 1 || m != 2) {
if (s[prv]) {
s[prv] -= 1;
s[nxt] += 1;
madd(dp[s[0]][s[1]][s[2]][w * (m != 2)][nxt], 1LL * x * (s[(m + 2) % 3] + 1) % MOD);
s[prv] += 1;
s[nxt] -= 1;
}
if (!s[m] && !s[prv]) {
madd(dp[s[0]][s[1]][s[2]][w * (m != 2)][nxt], x);
}
}
}
}
}
}
}
int ans = 0;
for (int x = 0; x < 3; ++x) {
for (int y = 0; y < 2; ++y) {
madd(ans, dp[0][0][0][y][x]);
}
}
cout << ans << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 33ms
memory: 196664kb
input:
2 3 6 1 5 2 1 6 4 2 3 4 5 3 6 3 1 5 2 3 5 6 2 4 4 1 1 2 3 4 3 4 5 6 1 2 5 6
output:
690 690 19400
result:
ok 3 lines
Test #2:
score: 10
Accepted
time: 71ms
memory: 196748kb
input:
3 5 9 6 3 8 1 5 4 9 4 2 1 6 5 7 7 3 2 8 4 5 7 5 6 8 2 9 7 1 4 9 3 3 1 6 2 8 7 2 1 3 6 9 8 3 5 4 6 7 4 8 9 5 1 2 8 8 2 5 4 6 1 2 9 3 9 4 6 7 3 5 1 7 1 2 3 4 5 6 4 5 6 7 8 9 1 2 3 7 8 9
output:
920808 19400 339064275 19400 339064275
result:
ok 5 lines
Test #3:
score: 10
Accepted
time: 80ms
memory: 196780kb
input:
10 5 15 22 9 24 13 11 7 25 21 14 3 5 4 26 19 26 18 29 16 29 16 7 13 30 17 1 4 15 23 9 12 20 22 2 23 18 5 3 10 21 12 30 14 28 27 11 24 8 10 28 17 27 2 20 1 25 6 19 8 6 19 15 27 9 16 21 14 10 19 15 12 11 2 7 16 28 26 25 18 18 12 24 13 29 13 14 1 1 20 29 22 17 3 23 11 28 20 17 5 10 4 24 3 6 4 5 21 22 2...
output:
169430774 184903628 864843034 186397548 145548558
result:
ok 5 lines
Test #4:
score: 10
Accepted
time: 72ms
memory: 196704kb
input:
20 5 26 19 51 35 32 56 13 57 27 9 44 35 34 58 42 12 59 12 8 33 59 16 1 17 11 50 60 28 34 7 33 1 15 8 32 11 29 22 27 52 9 24 15 2 45 19 56 39 28 18 21 3 14 41 6 18 23 25 6 26 23 49 52 17 2 42 10 16 41 31 4 54 43 29 30 46 55 24 49 44 10 21 20 55 20 60 14 4 37 54 45 48 31 5 47 3 5 40 36 36 38 53 7 43 4...
output:
147852189 405005016 808713263 143513805 739432483
result:
ok 5 lines
Test #5:
score: 10
Accepted
time: 234ms
memory: 196788kb
input:
50 10 103 51 39 35 6 66 124 140 131 19 117 97 47 98 14 101 60 41 99 140 94 58 132 30 128 116 44 41 104 7 1 90 75 37 14 95 89 45 116 79 90 86 138 11 7 102 43 87 29 110 127 127 84 26 62 128 107 56 136 47 64 42 124 149 119 71 48 100 40 81 59 11 59 83 62 91 55 4 146 5 73 46 145 117 75 24 20 26 16 97 122...
output:
417911208 97351943 508312273 671488492 300257045 924447116 20804203 895244811 807592393 291510686
result:
ok 10 lines
Test #6:
score: 10
Accepted
time: 312ms
memory: 196844kb
input:
60 10 180 96 39 136 47 63 77 105 74 67 142 122 70 72 137 143 155 95 156 105 121 37 81 3 159 167 139 130 152 180 88 148 149 114 31 43 112 146 127 84 90 75 27 2 46 128 178 116 69 83 117 135 173 177 118 129 34 127 94 40 174 150 56 99 159 116 43 44 59 32 163 175 131 54 113 50 132 50 83 94 149 88 27 161 ...
output:
718107834 439651991 48285391 327444608 41848771 251710848 768601859 5616262 115722825 621268852
result:
ok 10 lines
Test #7:
score: 10
Accepted
time: 415ms
memory: 196768kb
input:
70 10 78 164 105 187 88 118 8 96 82 143 38 127 27 93 18 171 19 158 112 91 179 17 40 15 99 205 113 19 186 16 26 82 4 41 193 5 110 79 201 106 161 59 183 196 123 127 69 37 117 130 88 141 96 93 149 113 176 206 46 195 35 178 102 111 155 41 25 148 150 179 185 61 166 136 118 176 46 50 61 84 124 150 112 185...
output:
574244039 90258414 671372789 692447351 517891232 162057897 813520656 477874859 894331726 632896864
result:
ok 10 lines
Test #8:
score: 10
Accepted
time: 561ms
memory: 196788kb
input:
80 10 125 87 139 196 191 41 58 194 2 175 150 76 18 87 1 40 180 166 13 119 159 123 210 135 61 224 142 149 222 216 197 113 234 194 9 231 96 71 198 176 98 36 24 185 235 157 80 122 226 187 42 240 154 171 25 218 195 198 124 50 113 32 91 119 45 141 53 12 74 121 158 96 180 116 145 22 142 133 88 182 16 124 ...
output:
182989152 167152295 954966218 901775057 602603484 275584550 365519155 505369311 282255048 698379468
result:
ok 10 lines
Test #9:
score: 10
Accepted
time: 704ms
memory: 196856kb
input:
90 10 42 170 5 215 133 153 104 85 9 164 157 42 87 108 64 161 205 168 228 216 257 81 163 68 195 99 234 136 231 142 127 149 86 182 224 219 80 125 7 230 256 41 204 125 251 77 86 29 28 204 55 15 30 35 174 53 269 23 240 127 262 199 260 232 259 46 80 43 49 169 233 88 192 27 217 186 47 185 228 249 63 245 2...
output:
896986561 569514476 700254599 264959290 267792056 714689018 783303002 760041034 673291395 354051155
result:
ok 10 lines
Test #10:
score: 10
Accepted
time: 936ms
memory: 196800kb
input:
99 10 243 69 109 28 151 100 296 2 258 112 25 206 181 148 21 246 12 84 254 250 91 248 46 14 183 162 38 82 130 48 20 150 139 247 283 24 29 93 191 105 129 38 131 87 147 166 22 297 297 71 232 185 106 123 291 15 63 101 286 214 224 29 187 154 215 292 226 223 225 55 23 170 165 238 137 113 203 79 21 217 289...
output:
842856263 728005420 149195086 227282873 174184496 228908720 657102478 596516687 889614826 509809125
result:
ok 10 lines