QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#520036 | #5416. Fabulous Fungus Frenzy | Z_drj | RE | 2ms | 4100kb | C++20 | 3.2kb | 2024-08-15 10:25:58 | 2024-08-15 10:25:58 |
Judging History
answer
#include <cstdio>
#include <map>
#include <vector>
#include <cassert>
#include <cstring>
#include <algorithm>
#define PII std::pair<int, int>
using i64 = long long;
const int N = 105;
int n[N], m[N], k;
char mat[N][N][N];
char now[N][N];
int cnt[128], need[N][128];
struct Op {
int op, x, y;
Op(int _o = 0, int _x = 0, int _y = 0) : op(_o), x(_x), y(_y) {}
};
std::vector<Op> ans;
void move(int a, int b, int c, int d) { // 把 (a,b) 换成 (c, d)
while (b > d) { ans.emplace_back(-1, c, d); std::swap(now[c][d], now[c][d + 1]); ++d;}
while (b < d) { ans.emplace_back(-2, c, d); std::swap(now[c][d], now[c][d - 1]); --d;}
while (a > c) { ans.emplace_back(-3, c, d); std::swap(now[c][d], now[c + 1][d]); ++c;}
while (a < c) { ans.emplace_back(-4, c, d); std::swap(now[c][d], now[c - 1][d]); --c;}
}
bool match(int x) {
int res = 0;
for (int i = 'a'; i <= 'z'; i++) {
if (cnt[i] < need[x][i]) {
res += (need[x][i] - cnt[i]);
}
}
for (int i = 'A'; i <= 'Z'; i++) {
if (cnt[i] < need[x][i]) {
res += (need[x][i] - cnt[i]);
}
}
for (int i = '0'; i <= '9'; i++) {
if (cnt[i] < need[x][i]) {
res += (need[x][i] - cnt[i]);
}
}
return res <= cnt[63] && ((x != 0 && res < n[x] * m[x]) || x == 0);
}
bool vis[N][N];
PII find(int x, int y, int id) {
for (int i = x; i <= n[0]; i++) {
for (int j = 1; j <= m[0]; j++) {
if (!vis[i][j] && now[i][j] == mat[id][x][y]) {
return std::make_pair(i, j);
}
}
}
for (int i = x; i <= n[0]; i++) {
for (int j = 1; j <= m[0]; j++) {
if (!vis[i][j] && now[i][j] == '?') {
return std::make_pair(i, j);
}
}
}
assert(false);
}
void change(int x) {
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n[x]; i++) {
for (int j = 1; j <= m[x]; j++) {
if (now[i][j] != mat[x][i][j]) {
if (cnt[mat[x][i][j]] || now[i][j] != '?') {
PII where = find(i, j, x);
move(i, j, where.first, where.second);
}
}
vis[i][j] = true;
--cnt[now[i][j]];
}
}
}
void stamp(int x) {
for (int i = 1; i <= n[x]; i++) {
for (int j = 1; j <= m[x]; j++) {
++cnt['?']; now[i][j] = '?';
}
}
ans.emplace_back(x, 1, 1);
}
int main() {
scanf("%d %d %d", n, m, &k);
for (int i = 1; i <= n[0]; i++) {
scanf(" ");
for (int j = 1; j <= m[0]; j++) {
mat[0][i][j] = getchar();
++need[0][mat[0][i][j]];
}
}
for (int i = 1; i <= n[0]; i++) {
scanf(" ");
for (int j = 1; j <= m[0]; j++) {
now[i][j] = getchar();
++cnt[now[i][j]];
}
}
for (int i = 1; i <= k; i++) {
scanf("%d %d", n + i, m + i);
for (int j = 1; j <= n[i]; j++) {
scanf(" ");
for (int k = 1; k <= m[i]; k++) {
mat[i][j][k] = getchar();
++need[i][mat[i][j][k]];
}
}
}
while (!match(0)) {
bool ok = false;
for (int i = 1; i <= k; i++) {
if (match(i)) {
ok = true; change(i); stamp(i);
}
}
if (!ok) {
break;
}
}
if (match(0)) {
change(0);
printf("%d\n", (int)ans.size());
while (!ans.empty()) {
int op = ans.back().op, x = ans.back().x, y = ans.back().y;
printf("%d %d %d\n", op, x, y);
ans.pop_back();
}
} else {
puts("-1");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3876kb
input:
3 3 1 OOO GOG BGB OOO GGG BBB 3 1 B G B
output:
13 -2 3 2 -4 3 3 -1 3 2 -2 2 2 -4 2 3 -1 2 2 -2 1 3 -2 1 2 1 1 1 -2 3 2 -2 2 2 -4 2 1 -4 3 1
result:
ok puzzle solved
Test #2:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
2 2 1 OO OO PP PP 1 2 OP
output:
-1
result:
ok puzzle solved
Test #3:
score: 0
Accepted
time: 0ms
memory: 3984kb
input:
4 8 4 11122222 33344444 55556666 77777777 NIxSHUOx DExDUIxx DANxSHIx YUANSHEN 2 3 NIy DEx 3 8 zzzzzzzz DANNSH9I YUA9SHEN 1 1 x 2 5 SHO8y DUUI8
output:
165 3 1 1 -4 2 1 -4 3 1 -4 4 1 -2 4 2 -2 4 3 -2 4 4 -2 4 5 -2 4 6 -2 4 7 -2 4 8 1 1 1 -4 3 3 -4 4 3 -2 4 4 -2 4 5 -2 4 6 3 1 1 -4 2 1 -4 3 1 -4 4 1 -2 4 2 -2 4 3 -2 4 4 2 1 1 -4 4 8 -1 4 7 -1 4 6 -1 4 5 -1 4 4 -1 4 3 -1 4 2 -1 4 1 -4 4 7 -1 4 6 -1 4 5 -1 4 4 -1 4 3 -1 4 2 -1 4 1 -4 4 6 -2 4 7 -2 4 8...
result:
ok puzzle solved
Test #4:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
2 2 1 OO OO OP PP 1 2 PP
output:
8 -4 2 1 -2 2 2 1 1 1 -4 2 1 1 1 1 -4 2 2 -1 2 1 -2 1 2
result:
ok puzzle solved
Test #5:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
2 2 1 OO OO OP PO 2 1 P P
output:
4 -4 2 2 -2 1 2 1 1 1 -2 1 2
result:
ok puzzle solved
Test #6:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
2 2 1 OO OO OP PO 2 2 PP PP
output:
-1
result:
ok puzzle solved
Test #7:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
2 2 1 OO OO OP PP 1 2 OP
output:
7 1 1 1 -4 2 2 -1 2 1 1 1 1 -4 2 2 -1 2 1 1 1 1
result:
ok puzzle solved
Test #8:
score: 0
Accepted
time: 2ms
memory: 4100kb
input:
20 20 20 bofelagiqboebdqplbhq qsrksfthhptcmikjohkt qrnhpoatbekggnkdonet aoalekbmpbisgflbhmol djnhnlitcakltqgegqrt fdctfarsmbnbeosdgilo ttrsljgiratfmioajorh gorljkihdnmnofnblfhm bqjkaehetdjlgctmijpc geslcskpoqjcgtbdspoa riqthroqmmhqgprqhsba fdiarrcomockfqdjjdkd jsbnigfqgsfekbbnnkir ildqctqtqrpcetaocp...
output:
9694 8 1 1 -4 2 1 -4 3 1 -4 4 1 -4 5 1 -4 6 1 -4 7 1 -4 8 1 -4 9 1 -4 10 1 -4 11 1 -4 12 1 -4 13 1 -4 14 1 -4 15 1 -4 16 1 -4 17 1 -4 18 1 -4 19 1 -4 20 1 -2 20 2 -2 20 3 -2 20 4 -2 20 5 -2 20 6 -2 20 7 -2 20 8 -2 20 9 -2 20 10 -2 20 11 -2 20 12 -2 20 13 -2 20 14 -2 20 15 -2 20 16 -2 20 17 -2 20 18 ...
result:
ok puzzle solved
Test #9:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
20 20 2 HbevPluVL5ORtUFcV9gf Mrq6zdTPMPnwlN7Fpzx6 Nfp71dVuxTZp9Qet0Ca9 ugbaF34DquDdbUnk5x7V fDFszn4PmvMpJ5BDWueJ 2YvFxKJgst8XbftPfy9T F7Q4huk87Lrp1M7i08is Q41E5AqLkkP3Q5qONXC2 MuM7iIzev3ZpxItvriQK 6OBdEC0sso5vdNQlrCSR BJQtKjN6RmppsMGIYL81 yyKsWJSoKorGGblNle0r RkKEQACh8f0bS5nPTtJH fQgoc39vdsPAUmxlYYL...
output:
-1
result:
ok puzzle solved
Test #10:
score: -100
Runtime Error
input:
20 20 2 pqo3Mcpvo74RFSsJszsa znrYm92Qr8fbqhbCTOgq 4KiMYr0kLAxPGNG15x7L QHKmq6xaJ4PU4msuRAiv UBfS6VUO87hRnMAjGXKX zCgknw3FfhdifmVcT6FF GH6ohIAzZuprlC3vMDVh mHIJ9KlQvWxt6EgGbJkA 3SwJNhRSdEeF9BNtc9k2 mZmEuriH7Rc4ccMjqI0Y cFfI8TC1iM4PkKziLOiN 15CUjuwudnrums3c3dsl ekL52LiFEpzmU4vaGtuX CfrnQtWb5zAN9oQS2fj...