QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#298126 | #4629. Longest Increasing Subsequence | defyers# | WA | 1ms | 3628kb | C++17 | 4.6kb | 2024-01-05 18:12:31 | 2024-01-05 18:12:31 |
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}}, 2},
};
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}, {1, 0}, {1, 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},
};
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}}, 2},
{{{-2, 0}, {-2, 1}, {-1, 0}, {0, 0}}, 1},
{{{-2, -1}, {-2, 0}, {-1, 0}, {0, 0}}, 1},
{{{-1, 0}, {-1, 1}, {1, 0}, {1, 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},
};
void solve(int TC) {
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<bool>> occ(8, vector<bool>(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 << endl;
cout << "board: ";
for (int i = 23; i >= 0; i--) {
cout << !!(boardstate & (1 << i));
}
cout << " " << ways << endl;
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;
}
}
for (auto [b, dis]: block) {
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;
}
key += board[nx][ny];
if (dx == 0) {
}
else {
nstate = nstate | (1ll << rep[nx][ny]);
}
}
if (fail) continue;
for (auto [dx, dy]: b) cout << " (" << dx << ", " << dy << ") ";
cout << endl;
cout << "@" << i << " " << j << " " << key << endl;
if (!dict.count(key)) {
continue;
}
if (nstate & ((1 << dis) - 1)) {
int ni = i;
int nj = j + dis;
if (nj == 8) {
ni = i + 1;
nj = 0;
}
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: 0
Wrong Answer
time: 1ms
memory: 3628kb
input:
7 7 41 53 58 75 78 81
output:
i: 0 j: 0 board: 111111111111111111111111 1 (0, 0) (0, 1) (0, 2) @0 0 77Y (0, 0) (0, 1) (0, 2) (0, 3) @0 0 77Ye i: 0 j: 1 board: 011111111111111111111111 1 (0, 0) (0, 1) (0, 2) @0 1 7Ye (0, 0) (0, 1) (0, 2) (0, 3) @0 1 7Yej i: 0 j: 2 board: 001111111111111111111111 1 (0, 0) (0, 1...
result:
wrong answer 1st lines differ - expected: '22', found: 'i: 0 j: 0'