QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#519983#5416. Fabulous Fungus FrenzyZ_drjRE 1ms4008kbC++203.1kb2024-08-15 10:04:092024-08-15 10:04:09

Judging History

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

  • [2024-08-15 10:04:09]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:4008kb
  • [2024-08-15 10:04:09]
  • 提交

answer

#include <cstdio>
#include <map>
#include <vector>
#include <cassert>	
#include <algorithm>

#define PII std::pair<int, int>

using i64 = long long;

const int N = 25;

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(-2, c, d); std::swap(now[c][d], now[c][d - 1]); --d;}
	while (b > d) { ans.emplace_back(-1, c, d); std::swap(now[c][d], now[c][d + 1]); ++d;}
	while (a < c) { ans.emplace_back(-4, c, d); std::swap(now[c][d], now[c - 1][d]); --c;}
	while (a > c) { ans.emplace_back(-3, 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);
}

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 (((x == i && j > y) || x != i) && 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 (((x == i && j > y) || x != i) && now[i][j] == '?') {
				return std::make_pair(i, j);
			}
		}
	}
	assert(false);
}

void change(int x) {
	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);
				}
			}
			--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[63]; 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 (true) {
		bool ok = false;
		for (int i = 1; i <= k; i++) {
			if (match(i)) {
				ok = true; change(i); stamp(i);
			}
		}
		if (!ok || match(0)) {
			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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3784kb

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: 0ms
memory: 3596kb

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: 3936kb

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: 3896kb

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: 3924kb

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: 3832kb

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: 3924kb

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: 1ms
memory: 4008kb

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: 3776kb

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

output:


result: