QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#388833#4637. Cell Towerjames1BadCreeperTL 0ms0kbC++143.5kb2024-04-13 20:43:362024-04-13 20:43:38

Judging History

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

  • [2024-04-13 20:43:38]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-04-13 20:43:36]
  • 提交

answer

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx", "avx2")
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); 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); 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 (_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)); 
                    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 (_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)); 
                    mp[v] += mp[u]; 
                    if (vis.find(v) == vis.end()) q[et + 4].push(v), vis.insert(v); 
                }
            }
        }
    }
    cout << mp[ED] << "\n"; 
    double ed = clock(); 
    cerr << (ed - st) * 1000 / CLOCKS_PER_SEC << "ms\n"; 
    return 0;
}

详细

Test #1:

score: 0
Time Limit Exceeded

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:


result: