QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#388833 | #4637. Cell Tower | james1BadCreeper | TL | 0ms | 0kb | C++14 | 3.5kb | 2024-04-13 20:43:36 | 2024-04-13 20:43:38 |
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;
}
Details
Tip: Click on the bar to expand more detailed information
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