QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#298181#4637. Cell TowerdefyersTL 2ms3724kbC++177.2kb2024-01-05 19:27:482024-01-05 19:27:48

Judging History

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

  • [2024-01-05 19:27:48]
  • 评测
  • 测评结果：TL
  • 用时：2ms
  • 内存：3724kb
查看
  • [2024-01-05 19:27:48]
  • 提交

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);
	}
}
源文件, 语言: C++17

详细

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...

output:

result:
English 繁體中文 简体中文

服务器时间: 2024-12-02 16:00:50 | 开源项目