QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#298126#4629. Longest Increasing Subsequencedefyers#WA 1ms3628kbC++174.6kb2024-01-05 18:12:312024-01-05 18:12:31

Judging History

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

  • [2024-01-05 18:12:31]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3628kb
  • [2024-01-05 18:12:31]
  • 提交

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);
	}
}

详细

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'