QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#521042#5416. Fabulous Fungus FrenzycqzhmWA 8ms27404kbC++142.1kb2024-08-15 20:21:112024-08-15 20:21:12

Judging History

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

  • [2024-08-15 20:21:12]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:27404kb
  • [2024-08-15 20:21:11]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN=505;
int n,m,k;
char s[MAXN];
int mp[MAXN][MAXN][MAXN],t[MAXN][MAXN];
int kn[MAXN],km[MAXN];
int cnt[MAXN<<2],vis[MAXN][MAXN];
struct node{
	int opt,x,y;
};
vector<node> ans;
inline int change(char x){
	if(x>='0' && x<='9') return x-'0'+1;
	if(x>='a' && x<='z') return x-'a'+1+20;
	if(x>='A' && x<='Z') return x-'A'+1+50;
}
inline int check(int d){
	memset(cnt,0,sizeof cnt);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cnt[t[i][j]]++;
	int sum=0;
	for(int i=1;i<=kn[d];i++) for(int j=1;j<=km[d];j++){
		if(cnt[mp[d][i][j]]) cnt[mp[d][i][j]]--,sum++;
		else if(cnt[0]) cnt[0]--;
		else return -1;
	}
	return sum;
}
inline void solve(int d){
	memset(vis,0,sizeof vis);
	for(int i=1;i<=kn[d];i++) for(int j=1;j<=km[d];j++){
		int x=0,y=0;
		for(int ii=1;!x && ii<=n;ii++) for(int jj=1;jj<=m;jj++) if(!vis[ii][jj] && mp[d][i][j]==t[ii][jj]) x=ii,y=jj;
		for(int ii=1;!x && ii<=n;ii++) for(int jj=1;jj<=m;jj++) if(!vis[ii][jj] && !t[ii][jj]) x=ii,y=jj;
		while(x<i) swap(t[x][y],t[x+1][y]),ans.push_back({-3,x++,y});
		while(y<j) swap(t[x][y],t[x][y+1]),ans.push_back({-1,x,y++});
		while(x>i) swap(t[x][y],t[x-1][y]),ans.push_back({-4,x--,y});
		while(y>j) swap(t[x][y],t[x][y-1]),ans.push_back({-2,x,y--});
		vis[i][j]=1;
	}
	for(int i=1;i<=kn[d];i++) for(int j=1;j<=km[d];j++) t[i][j]=0;
	if(d) ans.push_back({d,1,1});
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>k; kn[0]=n; km[0]=m;
	for(int i=1;i<=n;i++){
		cin>>s+1;
		for(int j=1;j<=m;j++) mp[0][i][j]=change(s[j]);
	}
	for(int i=1;i<=n;i++){
		cin>>s+1;
		for(int j=1;j<=m;j++) t[i][j]=change(s[j]);
	}
	for(int d=1;d<=k;d++){
		cin>>kn[d]>>km[d];
		for(int i=1;i<=kn[d];i++){
			cin>>s+1;
			for(int j=1;j<=km[d];j++)
				mp[d][i][j]=change(s[j]);
		}
	}
	while(1){
		if(check(0)>=0) break;
		bool flag=false;
		for(int i=1;i<=k;i++) if(check(i)>=0) flag=true,solve(i);
		if(!flag) return cout<<-1<<'\n',0;
	}
	solve(0);
	reverse(ans.begin(),ans.end());
	cout<<ans.size()<<'\n';
	for(int i=0;i<ans.size();i++) cout<<ans[i].opt<<" "<<ans[i].x<<" "<<ans[i].y<<'\n';
	return 0;
}

详细

Test #1:

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

input:

3 3 1
OOO
GOG
BGB

OOO
GGG
BBB

3 1
B
G
B

output:

16
-2 3 3
-2 3 2
-4 3 3
-2 2 3
-2 2 2
-4 2 3
-2 1 3
-2 1 2
-2 1 3
1 1 1
-2 3 2
-2 2 2
-2 1 2
-2 1 3
-4 2 3
-4 3 3

result:

ok puzzle solved

Test #2:

score: 0
Accepted
time: 1ms
memory: 7776kb

input:

2 2 1
OO
OO

PP
PP

1 2
OP

output:

-1

result:

ok puzzle solved

Test #3:

score: 0
Accepted
time: 2ms
memory: 10756kb

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:

508
-2 4 8
-2 4 7
-2 4 8
-2 4 6
-2 4 7
-2 4 8
-2 4 5
-2 4 6
-2 4 7
-2 4 8
-2 4 4
-2 4 5
-2 4 6
-2 4 7
-2 4 8
-2 4 3
-2 4 4
-2 4 5
-2 4 6
-2 4 7
-2 4 8
-2 4 2
-2 4 3
-2 4 4
-2 4 5
-2 4 6
-2 4 7
-2 4 8
-2 3 8
-2 3 7
-2 3 8
-2 3 6
-2 3 7
-2 3 8
-2 3 5
-2 3 6
-2 3 7
-2 3 8
-2 3 4
-2 3 5
-2 3 6
-2 3 7
-2...

result:

ok puzzle solved

Test #4:

score: 0
Accepted
time: 0ms
memory: 8476kb

input:

2 2 1
OO
OO

OP
PP

1 2
PP

output:

8
-2 2 2
-2 1 2
-4 2 2
1 1 1
-4 2 1
1 1 1
-4 2 2
-2 1 2

result:

ok puzzle solved

Test #5:

score: 0
Accepted
time: 1ms
memory: 6792kb

input:

2 2 1
OO
OO

OP
PO

2 1
P
P

output:

5
-2 2 2
-4 2 2
-2 1 2
1 1 1
-2 1 2

result:

ok puzzle solved

Test #6:

score: 0
Accepted
time: 1ms
memory: 7712kb

input:

2 2 1
OO
OO

OP
PO

2 2
PP
PP

output:

-1

result:

ok puzzle solved

Test #7:

score: 0
Accepted
time: 1ms
memory: 6684kb

input:

2 2 1
OO
OO

OP
PP

1 2
OP

output:

10
-2 2 2
-2 1 2
1 1 1
-4 2 2
-1 2 1
-2 1 2
1 1 1
-4 2 2
-2 1 2
1 1 1

result:

ok puzzle solved

Test #8:

score: -100
Wrong Answer
time: 8ms
memory: 27404kb

input:

20 20 20
bofelagiqboebdqplbhq
qsrksfthhptcmikjohkt
qrnhpoatbekggnkdonet
aoalekbmpbisgflbhmol
djnhnlitcakltqgegqrt
fdctfarsmbnbeosdgilo
ttrsljgiratfmioajorh
gorljkihdnmnofnblfhm
bqjkaehetdjlgctmijpc
geslcskpoqjcgtbdspoa
riqthroqmmhqgprqhsba
fdiarrcomockfqdjjdkd
jsbnigfqgsfekbbnnkir
ildqctqtqrpcetaocp...

output:

15541
-2 20 20
-2 20 19
-2 20 20
-2 20 18
-2 20 19
-2 20 20
-2 20 17
-2 20 18
-2 20 19
-2 20 20
-2 20 16
-2 20 17
-2 20 18
-2 20 19
-2 20 20
-2 20 15
-2 20 16
-2 20 17
-2 20 18
-2 20 19
-2 20 20
-2 20 14
-2 20 15
-2 20 16
-2 20 17
-2 20 18
-2 20 19
-2 20 20
-2 20 13
-2 20 14
-2 20 15
-2 20 16
-2 20 ...

result:

wrong answer preset op exceed 400