QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#388825#4637. Cell Towerjames1BadCreeperTL 662ms59200kbC++143.3kb2024-04-13 20:36:592024-04-13 20:37:00

Judging History

你现在查看的是最新测评结果

  • [2024-04-13 20:37:00]
  • 评测
  • 测评结果:TL
  • 用时:662ms
  • 内存:59200kb
  • [2024-04-13 20:36:59]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

int a[8][8]; 
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; 
set<ulong> vis; 
int dic3[200005], dic4[200005]; 
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); 
    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); vis.insert(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; 
        if (et + 3 != 63 && et + 3 != 62) {
            for (int k = 0; k < 6; ++k) {
                int _x = x + _3[k][0][0], _y = y + _3[k][0][1]; 
                if (!he(_x) || !he(_y) || (u >> id(_x, _y) & 1)) continue; 

                int __x = x + _3[k][1][0], __y = y + _3[k][1][1]; 
                if (he(__x) && 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)); 
                    mp[v] += mp[u]; 
                    if (vis.find(v) == vis.end()) q[et + 3].push(v), vis.insert(v); 
                }
            }
        }
        if (et + 4 != 63 && et + 4 != 62) {
            for (int k = 0; k < 19; ++k) {
                int _x = x + _4[k][0][0], _y = y + _4[k][0][1]; 
                if (!he(_x) || !he(_y) || (u >> id(_x, _y) & 1)) continue; 

                int x_ = x + _4[k][1][0], y_ = y + _4[k][1][1]; 
                if (!he(x_) || !he(y_) || (u >> id(x_, y_) & 1)) continue; 

                int __x = x + _4[k][2][0], __y = y + _4[k][2][1]; 
                if (he(__x) && 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)); 
                    mp[v] += mp[u]; 
                    if (vis.find(v) == vis.end()) q[et + 4].push(v), vis.insert(v); 
                }
            }
        }
    }
    cout << mp[ED] << "\n"; 
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3760kb

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: 7ms
memory: 4696kb

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: 2ms
memory: 4220kb

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: 12ms
memory: 5692kb

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: 3712kb

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: 3ms
memory: 4844kb

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: 4168kb

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: 26ms
memory: 8164kb

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: 40ms
memory: 9920kb

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: 55ms
memory: 10936kb

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: 84ms
memory: 15172kb

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: 89ms
memory: 15000kb

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: 115ms
memory: 17596kb

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: 10ms
memory: 5892kb

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: 13ms
memory: 5820kb

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: 56ms
memory: 11076kb

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: 25ms
memory: 7736kb

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: 32ms
memory: 8560kb

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: 662ms
memory: 59200kb

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: 574ms
memory: 53520kb

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: 54ms
memory: 10116kb

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: 30ms
memory: 7728kb

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...

output:


result: