QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#388929 | #4637. Cell Tower | james1BadCreeper | TL | 350ms | 36000kb | C++23 | 3.1kb | 2024-04-13 21:39:34 | 2024-04-13 21:39:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int a[15][15];
inline int id(int i, int j) { return (i << 3) + j; }
inline bool he(int x) { return x >= 0 && x < 8; }
map<ulong, ulong> mp;
bool dic3[1005], dic4[10005];
// 999
const int _3[6][2][2] = {
{{0, 1}, {1, 0}},
{{0, 1}, {1, 1}},
{{1, 0}, {1, 1}},
{{1, -1}, {1, 0}},
{{0, 1}, {0, 2}},
{{1, 0}, {2, 0}}
};
const int _4[19][3][2] = {
{{1, 0}, {2, 0}, {3, 0}},
{{0, 1}, {0, 2}, {0, 3}},
{{1, 0}, {1, 1}, {1, 2}},
{{1, -2}, {1, -1}, {1, 0}},
{{1, -1}, {1, 0}, {1, 1}},
{{0, 1}, {0, 2}, {1, 2}},
{{0, 1}, {0, 2}, {1, 0}},
{{0, 1}, {0, 2}, {1, 1}},
{{0, 1}, {1, 0}, {2, 0}},
{{1, 0}, {1, 1}, {2, 0}},
{{0, 1}, {1, -1}, {1, 0}},
{{1, 0}, {2, 0}, {2, 1}},
{{0, 1}, {1, 1}, {2, 1}},
{{1, -1}, {1, 0}, {2, 0}},
{{1, 0}, {2, -1}, {2, 0}},
{{1, 0}, {1, 1}, {2, 1}},
{{1, -1}, {1, 0}, {2, -1}},
{{0, 1}, {1, 0}, {1, 1}},
{{0, 1}, {1, 1}, {1, 2}}
};
int main(void) {
ios::sync_with_stdio(0); cin.tie(0);
double st = clock();
for (int i = 0; i < 8; ++i)
for (int j = 0; j < 8; ++j)
cin >> a[i][j];
int m; cin >> m;
while (m--) {
string x; cin >> x;
if (x.length() == 3) dic3[atoi(x.c_str())] = 1;
else dic4[atoi(x.c_str())] = 1;
}
const ulong ED = -1;
mp[0] = 1;
queue<ulong> q[65]; q[0].push(0);
for (int et = 0; et < 62; ++et) while (!q[et].empty()) {
ulong u = q[et].front(); q[et].pop();
int i = -1;
for (i = 0; i < 64; ++i) if (!(u >> i & 1)) break;
int x = i >> 3, y = i & 7;
const ulong now = mp[u];
for (int k = 0; k < 6; ++k) {
int _x = x + _3[k][0][0], _y = y + _3[k][0][1];
if (_x >= 8 || !he(_y) || (u >> id(_x, _y) & 1)) continue;
int __x = x + _3[k][1][0], __y = y + _3[k][1][1];
if (__x < 8 && he(__y) && !(u >> id(__x, __y) & 1) && dic3[a[x][y] * 100 + a[_x][_y] * 10 + a[__x][__y]]) {
ulong v = (u | 1ull << id(x, y) | 1ull << id(_x, _y) | 1ull << id(__x, __y));
if ((mp[v] += now) == now) q[et + 3].push(v);
}
}
for (int k = 0; k < 19; ++k) {
int _x = x + _4[k][0][0], _y = y + _4[k][0][1];
if (_x >= 8 || !he(_y) || (u >> id(_x, _y) & 1)) continue;
int x_ = x + _4[k][1][0], y_ = y + _4[k][1][1];
if (x_ >= 8 || !he(y_) || (u >> id(x_, y_) & 1)) continue;
int __x = x + _4[k][2][0], __y = y + _4[k][2][1];
if (__x < 8 && he(__y) && !(u >> id(__x, __y) & 1) && dic4[a[x][y] * 1000 + a[_x][_y] * 100 + a[x_][y_] * 10 + a[__x][__y]]) {
ulong v = (u | 1ull << id(x, y) | 1ull << id(_x, _y) | 1ull << id(x_, y_) | 1ull << id(__x, __y));
if ((mp[v] += now) == now) q[et + 4].push(v);
}
}
}
cout << mp[ED] << "\n";
double ed = clock();
cerr << (ed - st) * 1000 / CLOCKS_PER_SEC << "ms\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4024kb
input:
1 1 1 1 2 3 3 3 0 4 4 4 2 2 2 3 0 0 5 5 6 6 7 7 0 9 5 5 6 8 7 7 9 9 9 1 6 8 8 8 3 1 1 1 2 2 2 2 4 5 6 0 0 4 4 3 7 8 9 0 0 4 3 3 16 1111 2222 3333 444 0000 5555 6666 7777 8888 9999 111 333 3456 789 3478 569
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 2ms
memory: 4648kb
input:
2 0 1 2 3 3 3 0 1 2 1 4 1 3 0 1 1 1 3 0 0 2 3 4 4 1 3 3 4 0 3 4 3 2 0 3 3 0 2 1 4 4 3 3 4 1 2 4 1 0 2 4 0 0 2 4 3 1 0 3 3 4 0 3 1000 953 1289 0424 673 9845 811 6865 0695 388 037 974 101 2416 560 1847 6433 6461 5835 457 629 788 456 498 2762 223 013 418 945 3275 9724 7059 2075 0231 587 100 2420 0606 2...
output:
1313
result:
ok single line: '1313'
Test #3:
score: 0
Accepted
time: 1ms
memory: 4216kb
input:
3 3 0 3 4 4 4 4 3 2 2 3 4 3 4 4 3 3 3 3 4 0 4 4 2 3 2 3 1 3 4 4 3 1 4 4 3 3 2 0 4 3 3 0 2 1 2 2 0 3 4 4 1 2 4 3 4 3 2 3 2 4 1 2 1500 9714 381 3673 8409 6682 464 962 290 931 2243 609 172 4735 133 3406 099 1957 6466 8420 759 0468 1364 354 835 8953 7017 3525 3755 012 9201 132 5326 1504 454 7940 774 258...
output:
28
result:
ok single line: '28'
Test #4:
score: 0
Accepted
time: 7ms
memory: 5112kb
input:
2 7 1 4 3 2 2 4 3 7 4 8 4 2 4 6 7 9 4 2 4 0 3 0 4 6 7 0 3 3 6 0 3 3 3 1 4 5 0 6 1 2 6 1 3 8 5 2 2 7 2 3 8 6 4 2 7 3 8 4 7 4 2 8 1500 534 632 6554 471 765 832 846 4108 4471 7322 5893 229 7676 950 154 823 4904 557 4525 6585 4959 0140 341 0082 619 2582 5914 8091 669 3866 040 432 776 5622 0681 9663 960 ...
output:
11009
result:
ok single line: '11009'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3972kb
input:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1500 5680 9670 4076 6022 8226 798 6514 7136 1248 321 4999 3696 3679 2105 137 076 110 620 633 9795 6912 556 846 696 435 492 8732 8137 9663 0068 011 081 1840 1646 204 726 796...
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 4ms
memory: 4704kb
input:
2 2 2 2 3 2 2 2 2 1 3 3 3 0 3 1 3 2 3 2 3 2 1 3 3 3 3 3 1 2 2 2 2 2 2 2 0 2 1 3 2 3 1 2 1 2 1 3 2 0 3 0 0 0 3 2 3 3 2 2 3 2 0 2 2600 1859 505 251 3357 6613 422 9040 234 8007 5549 783 1002 3129 519 2139 543 2944 186 649 887 255 3768 1978 454 952 1200 273 399 5095 6540 185 682 685 433 104 9762 2777 33...
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 2ms
memory: 4440kb
input:
5 2 2 4 0 9 8 8 5 1 5 6 8 4 9 2 0 3 4 7 0 6 8 5 8 9 6 0 7 4 3 5 1 4 0 4 6 5 5 6 4 1 7 1 6 1 3 0 4 9 5 2 4 7 3 9 7 3 2 7 9 1 9 8 3000 8737 0086 3383 6957 0433 5556 3554 8016 9128 4963 2454 7848 4426 5336 0306 5859 5201 8976 6286 2310 4805 6781 0717 4782 2427 4919 5732 4203 0329 4954 2266 8241 6328 66...
output:
224
result:
ok single line: '224'
Test #8:
score: 0
Accepted
time: 18ms
memory: 6748kb
input:
2 9 5 3 8 5 1 4 3 5 5 9 5 1 2 0 4 2 1 2 5 7 6 2 3 5 6 8 5 1 5 6 5 9 5 1 3 8 3 9 8 0 3 3 0 7 2 7 2 8 5 4 3 4 8 6 2 4 1 6 7 2 4 5 4000 3974 7080 6916 0713 0718 5580 2585 5267 4829 4225 6877 3242 7457 6763 2957 7821 3964 7909 5566 5286 6900 5458 9525 7774 3429 2897 0013 5130 7162 9855 0187 0379 7927 81...
output:
6629
result:
ok single line: '6629'
Test #9:
score: 0
Accepted
time: 21ms
memory: 7588kb
input:
6 9 5 3 5 0 9 4 5 6 7 3 4 3 8 8 5 3 1 7 9 4 9 6 7 2 4 4 7 9 3 3 9 9 4 7 2 6 2 6 7 2 9 1 7 7 8 7 9 9 5 5 6 9 9 5 7 6 7 7 9 7 1 0 4100 8758 218 204 1316 9551 5607 059 082 655 6721 426 6668 3958 675 1589 385 159 795 800 366 973 3966 808 6609 7982 8211 858 147 2993 490 3801 378 857 2218 339 2779 4298 17...
output:
4162
result:
ok single line: '4162'
Test #10:
score: 0
Accepted
time: 31ms
memory: 8152kb
input:
7 0 8 9 8 1 8 5 8 4 5 2 7 4 6 3 6 9 7 9 8 9 6 7 3 0 3 0 3 9 8 6 8 5 9 8 7 4 5 6 9 9 6 3 4 5 9 9 8 3 5 9 9 7 6 8 8 8 8 4 4 7 9 8 5000 6459 9824 1478 9540 1682 1062 9262 6397 5567 5788 7287 4427 3613 9095 3852 5503 5894 1081 4273 2501 8672 4446 3851 1643 3056 0368 3743 0939 4728 2175 2640 9383 5418 99...
output:
239770
result:
ok single line: '239770'
Test #11:
score: 0
Accepted
time: 53ms
memory: 10452kb
input:
2 6 6 9 8 2 8 6 9 5 8 8 9 4 6 7 8 8 8 6 6 5 9 4 7 9 7 4 6 4 7 9 5 9 9 9 7 9 3 2 5 8 4 8 7 5 8 5 9 8 5 8 8 6 6 4 9 9 9 3 9 8 5 9 6010 1530 852 316 3289 6625 5759 172 812 6082 263 741 0561 6774 267 7565 1806 940 2780 754 811 7522 1435 5940 5942 0953 4724 6522 8965 4046 3633 5708 7913 3936 3334 8215 85...
output:
5042195
result:
ok single line: '5042195'
Test #12:
score: 0
Accepted
time: 53ms
memory: 10504kb
input:
2 1 0 0 1 1 0 1 2 1 0 0 2 2 1 2 0 0 0 0 1 1 1 2 1 0 0 1 1 2 2 2 1 2 1 1 1 0 2 1 2 0 2 1 2 1 0 0 0 2 1 2 2 2 0 1 0 1 2 2 1 1 1 1 6010 487 0096 510 7213 906 901 738 8707 276 0695 894 693 929 367 2310 6839 8974 6566 7419 7787 5910 7581 4550 8852 5936 5303 9967 3339 6613 3720 9111 2819 9756 7349 1192 38...
output:
3586625
result:
ok single line: '3586625'
Test #13:
score: 0
Accepted
time: 63ms
memory: 11868kb
input:
2 2 1 1 1 2 2 0 2 2 1 1 0 0 0 1 0 1 1 0 2 1 2 2 0 1 2 1 1 1 0 2 0 1 0 1 1 2 1 1 2 2 1 2 2 0 1 2 0 1 2 1 1 2 1 2 0 0 2 0 2 0 1 2 7000 1380 3344 5274 6832 7080 6642 5683 9082 2948 6451 3170 7733 9872 1644 4649 2444 9277 8818 6373 9942 1816 0699 9710 8694 2414 3176 6777 0903 2266 6620 5640 2504 3881 98...
output:
24521314
result:
ok single line: '24521314'
Test #14:
score: 0
Accepted
time: 8ms
memory: 5260kb
input:
9 9 6 9 5 9 4 8 2 2 7 7 9 7 7 7 1 9 8 9 9 5 7 1 9 3 9 6 2 6 8 4 6 7 6 9 6 4 8 9 5 4 8 5 5 7 7 2 3 5 3 2 6 9 8 7 3 6 6 2 9 6 7 9 4000 3184 6746 5697 4009 6578 9082 4836 9135 1116 8771 0002 5746 8598 5246 1551 9500 4102 4529 5203 3209 4765 2522 0549 1871 8379 5269 4607 5430 4179 2661 9990 7616 6628 50...
output:
4309
result:
ok single line: '4309'
Test #15:
score: 0
Accepted
time: 8ms
memory: 5156kb
input:
3 2 0 1 1 2 1 1 1 3 3 1 1 1 0 2 2 2 2 1 2 1 3 2 3 3 2 3 3 1 1 3 2 0 2 0 3 3 0 1 3 1 0 0 0 0 2 1 0 3 0 1 3 1 2 1 1 0 1 0 1 3 3 0 1332 4465 0603 1696 784 9852 7412 016 9986 051 2147 4311 7915 1385 236 8062 494 2868 651 5572 0287 7521 0553 350 495 6665 070 095 351 4264 792 602 630 2904 543 1863 999 369...
output:
40240
result:
ok single line: '40240'
Test #16:
score: 0
Accepted
time: 32ms
memory: 8212kb
input:
0 0 1 2 1 2 2 0 0 1 0 0 0 2 0 2 1 1 0 0 2 2 2 0 1 0 1 1 1 1 1 1 2 2 2 0 1 0 2 0 0 1 2 2 0 2 2 0 2 1 1 2 0 0 0 2 1 2 2 0 1 2 0 1 1332 839 392 799 559 778 5603 1836 8959 8465 647 915 106 363 015 594 3820 246 134 2252 662 3998 9921 2410 5339 1444 512 112 6752 3642 3335 791 2358 0245 9931 122 3067 069 4...
output:
3094345
result:
ok single line: '3094345'
Test #17:
score: 0
Accepted
time: 17ms
memory: 6344kb
input:
2 2 3 3 4 2 1 4 1 4 2 2 1 0 4 3 3 2 1 4 3 4 4 3 3 1 1 1 4 1 1 2 3 4 2 1 1 2 2 4 4 2 4 4 4 1 1 4 2 3 3 3 3 4 2 3 1 3 4 2 4 4 1 2 2000 952 697 213 2355 8660 9322 417 077 520 921 781 663 1577 0128 981 072 3258 3882 611 127 8836 811 2733 4353 646 464 5018 8646 6276 0142 1429 6133 4076 6519 7142 7471 792...
output:
840870
result:
ok single line: '840870'
Test #18:
score: 0
Accepted
time: 20ms
memory: 6776kb
input:
2 2 0 1 1 2 3 3 0 1 0 0 0 2 2 3 3 0 2 1 3 0 3 0 1 3 0 3 3 1 2 3 2 3 3 1 0 2 0 1 3 2 0 1 0 0 2 0 2 0 3 3 1 0 1 3 3 3 1 1 2 3 2 1 1025 7760 3929 7472 2501 134 062 789 277 941 467 4879 842 2309 7134 6126 331 424 5685 907 857 3076 153 8625 564 747 9798 0208 192 893 5915 380 851 897 5049 612 135 428 9213...
output:
64396225
result:
ok single line: '64396225'
Test #19:
score: 0
Accepted
time: 350ms
memory: 36000kb
input:
5 0 8 9 8 3 6 5 8 6 3 0 0 5 7 7 4 7 0 2 6 3 1 8 6 7 4 7 3 5 6 7 2 2 8 1 4 9 4 3 1 4 2 6 3 8 5 7 2 0 4 3 1 3 7 8 0 9 5 5 5 0 7 3 10010 3237 429 338 5339 967 886 874 155 597 339 564 788 7569 5219 1831 3214 9476 7648 6630 3226 9234 3869 9709 2449 8841 2392 9727 4780 8802 9027 7165 9008 3130 8383 6401 6...
output:
19077209438
result:
ok single line: '19077209438'
Test #20:
score: 0
Accepted
time: 320ms
memory: 32644kb
input:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7000 8002 1902 9005 4672 7701 8106 3302 4277 9001 3104 0519 0321 2892 1219 6821 2817 3349 1223 1814 4404 3503 6068 6900 8180 0440 6715 5785 0903 8958 7054 9151 2280 9731 62...
output:
19077209438
result:
ok single line: '19077209438'
Test #21:
score: 0
Accepted
time: 29ms
memory: 7692kb
input:
2 2 6 8 6 4 4 0 2 0 7 6 4 6 3 3 6 5 5 3 4 3 5 6 2 8 4 5 0 1 3 3 7 0 7 8 4 2 4 4 8 0 2 4 3 6 4 3 5 3 7 0 7 1 7 3 8 8 0 3 5 6 1 6 1024 832 4846 3292 4305 157 9826 1130 614 4317 8715 718 879 713 259 591 594 567 387 958 5611 6288 8687 0987 469 749 2326 6216 568 431 1273 311 750 812 314 235 4194 6563 791...
output:
84301565
result:
ok single line: '84301565'
Test #22:
score: 0
Accepted
time: 16ms
memory: 6288kb
input:
4 7 4 7 7 3 8 9 7 3 8 4 6 9 0 7 6 9 7 3 7 4 1 3 4 4 8 9 9 6 6 8 7 9 9 8 5 9 8 6 8 9 6 4 6 7 5 9 7 3 4 6 8 9 6 4 1 9 3 9 9 7 9 8 1001 476 4277 392 461 092 638 988 437 187 753 999 917 058 298 379 141 922 583 024 549 283 061 211 873 966 662 488 884 737 422 090 680 423 837 043 572 989 984 281 578 054 34...
output:
0
result:
ok single line: '0'
Test #23:
score: -100
Time Limit Exceeded
input:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6000 440 4014 3778 2421 974 876 3054 9418 652 233 4525 047 0843 6566 463 0664 2578 060 585 084 451 822 981 6569 453 2466 462 814 210 2545 7432 4530 130 6415 036 760 2746 05...