QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #298181 | #4637. Cell Tower | defyers | TL | 2ms | 3724kb | C++17 | 7.2kb | 2024-01-05 19:27:48 | 2024-01-05 19:27:48 |
Judging History
answer
#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")
#pragma GCC targetr("avx2")
using namespace std;
using ll = long long;
using pii = pair<int, int>;
vector<pair<vector<pii>, int>> block3 = {
{{{-2, 0}, {-1, 0}, {0, 0}}, 1},
{{{0, 0}, {0, 1}, {0, 2}}, 3},
{{{-1, -1}, {-1, 0}, {0, 0}}, 1},
{{{-1, 1}, {0, 0}, {0, 1}}, 2},
{{{-1, 0}, {0, 0}, {0, 1}}, 2},
{{{-1, 0}, {-1, 1}, {0, 0}}, 1},
};
vector<pair<vector<pii>, int>> block4 = {
{{{-2, 0}, {-2, 1}, {-1, 0}, {0, 0}}, 1},
{{{-2, -1}, {-2, 0}, {-1, 0}, {0, 0}}, 1},
{{{-1, 0}, {-1, 1}, {0, 0}, {0, 1}}, 2},
{{{-2, 1}, {-1, 1}, {0, 0}, {0, 1}}, 2},
{{{-2, 0}, {-1, 0}, {0, 0}, {0, 1}}, 2},
{{{-3, 0}, {-2, 0}, {-1, 0}, {0, 0}}, 1},
{{{0, 0}, {0, 1}, {0, 2}, {0, 3}}, 4},
{{{-1, -1}, {-1, 0}, {0, 0}, {0, 1}}, 2},
{{{-1, 1}, {-1, 2}, {0, 0}, {0, 1}}, 2},
{{{-2, 1}, {-1, 0}, {-1, 1}, {0, 0}}, 1},
{{{-2, -1}, {-1, -1}, {-1, 0}, {0, 0}}, 1},
{{{-1, -1}, {-1, 0}, {-1, 1}, {0, 0}}, 1},
{{{-2, 0}, {-1, -1}, {-1, 0}, {0, 0}}, 1},
{{{-2, 0}, {-1, 0}, {-1, 1}, {0, 0}}, 1},
{{{-1, 1}, {0, 0}, {0, 1}, {0, 2}}, 3},
{{{-1, 0}, {0, 0}, {0, 1}, {0, 2}}, 3},
{{{-1, -2}, {-1, -1}, {-1, 0}, {0, 0}}, 1},
{{{-1, 2}, {0, 0}, {0, 1}, {0, 2}}, 3},
{{{-1, 0}, {-1, 1}, {-1, 2}, {0, 0}}, 1},
};
vector<pair<vector<pii>, int>> block = {
{{{-2, 0}, {-1, 0}, {0, 0}}, 1},
{{{0, 0}, {0, 1}, {0, 2}}, 3},
{{{-1, -1}, {-1, 0}, {0, 0}}, 1},
{{{-1, 1}, {0, 0}, {0, 1}}, 2},
{{{-1, 0}, {0, 0}, {0, 1}}, 2},
{{{-1, 0}, {-1, 1}, {0, 0}}, 1},
{{{-2, 0}, {-2, 1}, {-1, 0}, {0, 0}}, 1},
{{{-2, -1}, {-2, 0}, {-1, 0}, {0, 0}}, 1},
{{{-1, 0}, {-1, 1}, {0, 0}, {0, 1}}, 2},
{{{-2, 1}, {-1, 1}, {0, 0}, {0, 1}}, 2},
{{{-2, 0}, {-1, 0}, {0, 0}, {0, 1}}, 2},
{{{-3, 0}, {-2, 0}, {-1, 0}, {0, 0}}, 1},
{{{0, 0}, {0, 1}, {0, 2}, {0, 3}}, 4},
{{{-1, -1}, {-1, 0}, {0, 0}, {0, 1}}, 2},
{{{-1, 1}, {-1, 2}, {0, 0}, {0, 1}}, 2},
{{{-2, 1}, {-1, 0}, {-1, 1}, {0, 0}}, 1},
{{{-2, -1}, {-1, -1}, {-1, 0}, {0, 0}}, 1},
{{{-1, -1}, {-1, 0}, {-1, 1}, {0, 0}}, 1},
{{{-2, 0}, {-1, -1}, {-1, 0}, {0, 0}}, 1},
{{{-2, 0}, {-1, 0}, {-1, 1}, {0, 0}}, 1},
{{{-1, 1}, {0, 0}, {0, 1}, {0, 2}}, 3},
{{{-1, 0}, {0, 0}, {0, 1}, {0, 2}}, 3},
{{{-1, -2}, {-1, -1}, {-1, 0}, {0, 0}}, 1},
{{{-1, 2}, {0, 0}, {0, 1}, {0, 2}}, 3},
{{{-1, 0}, {-1, 1}, {-1, 2}, {0, 0}}, 1},
};
void solve(int TC) {
// for (auto [b, d]: block) {
// vector<string> s(8);
// for (int i = 0; i < 8; i++) s[i] = "........";
// int c = 0;
// for (auto [dx, dy]: b) {
// s[dx + 3][dy + 3] = '0' + (++c);
// }
// for (int i = 0; i < 8; i++) cout << s[i] << "\n";
// cout << "====\n";
// }
vector<vector<int>> a(8, vector<int>(8));
vector<vector<char>> board(8, vector<char>(8));
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
cin >> a[i][j];
board[i][j] = a[i][j] + '0';
}
}
int n;
cin >> n;
vector<string> s(n);
set<string> dict;
for (int i = 0; i < n; i++) {
cin >> s[i];
dict.insert(s[i]);
}
vector dp(9, vector(9, map<ll, ll>()));
dp[0][0][(1ll << 24) - 1]++;
vector<vector<int>> rep(8, vector<int>(8));
vector<vector<int>> occ(8, vector<int>(8));
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
for (auto [boardstate, ways]: dp[i][j]) {
// cout << "i: " << i << " j: " << j << " " << ways << " " << boardstate << endl;
int curx = i - 3;
int cury = j;
// for (int i = 0; i < 8; i++) for (int j = 0; j < 8; j++) occ[i][j] = 0;
// for (int i = 0; i < curx; i++) for (int j = 0; j < 8; j++) occ[i][j] = 1;
// for (int i = 0; i < cury; i++) if (curx >= 0) occ[curx][i] = 1;
for (int i = 0; i < 24; i++) {
if (curx >= 0 && curx < 8 && cury >= 0 && cury < 8) {
rep[curx][cury] = i;
// cout << "$$ " << curx << " " << cury << " " << (boardstate & (1ll << i)) << " " << !!(boardstate & (1ll << i)) << endl;
occ[curx][cury] = !!(boardstate & (1ll << i));
}
++cury;
if (cury == 8) {
++curx;
cury = 0;
}
}
// for (int i = 0; i < 8; i++) {
// for (int j = 0; j < 8; j++) {
// cout << rep[i][j] << " ";
// }
// cout << "\n";
// }
// cout << ".==.=..=.=.\n";
// for (int i = 0; i < 8; i++) {
// for (int j = 0; j < 8; j++) {
// cout << occ[i][j] << " ";
// }
// cout << "\n";
// }
// cout << ".==.=..=.=.\n";
for (auto [b, dis]: block) {
// {
// // for (int i = 0; i < 8; i++) for (int j = 0; j < 8; j++) occ[i][j] = 0;
// int curx = i - 3;
// int cury = j;
// for (int i = 0; i < 24; i++) {
// if (curx >= 0 && curx < 8 && cury >= 0 && cury < 8) {
// rep[curx][cury] = i;
// occ[curx][cury] = !!(boardstate & (1ll << i));
// }
// ++cury;
// if (cury == 8) {
// ++curx;
// cury = 0;
// }
// }
// }
bool fail = false;
ll nstate = boardstate;
string key = "";
for (auto [dx, dy]: b) {
int nx = i + dx, ny = j + dy;
if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8) {
fail = true;
break;
}
if (occ[nx][ny] && dx != 0) {
fail = true;
break;
}
// occ[nx][ny] = 2;
key += board[nx][ny];
if (dx == 0) {
}
else {
nstate = nstate | (1ll << rep[nx][ny]);
}
}
if (fail) continue;
// cout << "=====\n";
// for (int i = 0; i < 8; i++) {
// for (int j = 0; j < 8; j++) {
// cout << occ[i][j] << " ";
// }
// cout << "\n";
// }
// for (auto [dx, dy]: b) cout << " (" << dx << ", " << dy << ") ";
// cout << endl;
// cout << "@" << i << " " << j << " " << key << endl;
if (!dict.count(key)) {
continue;
}
// cout << "C@" << i << " " << j << " " << key << endl;
if ((nstate & ((1 << dis) - 1)) == (1 << dis) - 1) {
int ni = i;
int nj = j + dis;
if (nj == 8) {
ni = i + 1;
nj = 0;
// cout << ">>> " << ((nstate >> dis) | (((1ll << 24) - 1) - ((1ll << (24 - dis)) - 1))) << endl;
// if (ni == 8 && ((nstate >> dis) | (((1ll << 24) - 1) - ((1ll << (24 - dis)) - 1))) == ((1ll << 24) - 1)) {
// for (int i = 0; i < 10; i++) {
// cout << "OWOWOWOWOWOWOW" << endl;
// }
// }
}
// bitset<24> bs(((nstate >> dis) | (((1ll << 24) - 1) - ((1ll << (24 - dis)) - 1))));
// cout << ">>> " << ni << " " << nj << " " << ((nstate >> dis) | (((1ll << 24) - 1) - ((1ll << (24 - dis)) - 1))) << endl;
// cout << bs << endl;
dp[ni][nj][(nstate >> dis) | (((1ll << 24) - 1) - ((1ll << (24 - dis)) - 1))] += ways;
}
}
if (boardstate & 1) {
int ni = i;
int nj = j + 1;
if (nj == 8) {
ni = i + 1;
nj = 0;
}
dp[ni][nj][(boardstate >> 1)] += ways;
}
}
}
}
ll ans = dp[8][0][(1ll << 24) - 1];
cout << ans << "\n";
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cout << fixed << setprecision(10);
int t = 1;
// cin >> t;
for (int i = 1; i <= t; i++) {
solve(i);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3724kb
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: -100
Time Limit Exceeded
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...