QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#293847#5416. Fabulous Fungus FrenzyhuzhaoyangWA 2ms3880kbC++142.0kb2023-12-29 20:55:592023-12-29 20:56:01

Judging History

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

  • [2023-12-29 20:56:01]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3880kb
  • [2023-12-29 20:55:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=25,M=100;
int n,m,k,cnt[M];
char s[N][N];
vector<pair<int,pair<int,int> > >ans;
int get(char c){
	if (c=='?')return 62;
	if (c<='9')return c-'0';
	if (c<='Z')return c-'A'+10;
	return c-'a'+36;
}
struct Matrix{
	int n,m,cnt[M];
	char s[N][N];
	void init(){
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)cnt[get(s[i][j])]++;
	}
}a[N];
void swapD(int x,int y){
	swap(s[x][y],s[x+1][y]);
	ans.push_back(make_pair(-3,make_pair(x,y)));
}
void swapR(int x,int y){
	swap(s[x][y],s[x][y+1]);
	ans.push_back(make_pair(-1,make_pair(x,y)));
}
bool check(int k){
	int s=0;
	for(int i=0;i<62;i++)s+=max(a[k].cnt[i]-cnt[i],0);
	if (s>cnt[62])return 0;
	if (!k)return 1;
	for(int i=0;i<62;i++)
		if ((a[k].cnt[i])&&(cnt[i]))return 1;
	return 0;
}
void calc(int k){
	for(int i=1;i<=a[k].n;i++)
		for(int j=1;j<=a[k].m;j++){
			int c=get(a[k].s[i][j]);
			if (!cnt[c])c=62;
			for(int x=1;x<=n;x++)
				for(int y=1;y<=m;y++)
					if ((get(s[x][y])==c)&&((x>i)||(x==i)&&(y>=j))){
						while (x<i)swapD(x++,y);
						while (y<j)swapR(x,y++);
						while (x>i)swapD(--x,y);
						while (y>j)swapR(x,--y);
						x=y=114514;
					}
			s[i][j]='?',cnt[c]--,cnt[62]++;
		}
	if (k)ans.push_back(make_pair(k,make_pair(1,1)));
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	a[0].n=n,a[0].m=m;
	for(int i=1;i<=n;i++)scanf("%s",a[0].s[i]+1);
	for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
	for(int t=1;t<=k;t++){
		scanf("%d%d",&a[t].n,&a[t].m);
		for(int i=1;i<=a[t].n;i++)scanf("%s",a[t].s[i]+1);
	}
	for(int t=0;t<=k;t++)a[t].init();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)cnt[get(s[i][j])]++;
	while (1){
		if (check(0)){
			calc(0);
			break;
		}
		bool flag=0;
		for(int t=1;t<=k;t++)
			if (check(t))flag=1,calc(t);
		if (!flag){
			puts("-1");
			return 0;
		}
	}
	printf("%d\n",ans.size());
	reverse(ans.begin(),ans.end());
	for(pair<int,pair<int,int> >i:ans)printf("%d %d %d\n",i.first,i.second.first,i.second.second);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3580kb

input:

3 3 1
OOO
GOG
BGB

OOO
GGG
BBB

3 1
B
G
B

output:

13
-1 3 1
-3 2 3
-1 3 2
-1 2 1
-3 1 3
-1 2 2
-1 1 2
-1 1 1
1 1 1
-1 3 1
-1 2 1
-3 1 1
-3 2 1

result:

ok puzzle solved

Test #2:

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

input:

2 2 1
OO
OO

PP
PP

1 2
OP

output:

-1

result:

ok puzzle solved

Test #3:

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

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:

122
3 1 1
-1 1 1
-1 1 2
-1 1 3
-1 1 4
-1 1 5
-1 1 6
-1 1 7
-3 1 8
-3 2 8
-3 3 8
1 1 1
-1 2 3
-1 2 4
-1 2 5
-1 2 6
-3 2 7
-3 3 7
3 1 1
-1 1 1
-1 1 2
-1 1 3
-3 1 4
-3 2 4
-3 3 4
2 1 1
-3 3 6
-3 3 5
-3 3 3
-1 4 2
-1 3 2
-1 3 3
-1 3 4
-1 3 5
-1 3 6
-1 3 7
-3 3 1
-3 2 6
-3 2 5
-1 2 4
-1 2 5
-1 2 6
-1 2 7...

result:

ok puzzle solved

Test #4:

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

input:

2 2 1
OO
OO

OP
PP

1 2
PP

output:

8
-1 1 1
-3 1 2
1 1 1
-3 1 1
1 1 1
-3 1 2
-1 2 1
-1 1 1

result:

ok puzzle solved

Test #5:

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

input:

2 2 1
OO
OO

OP
PO

2 1
P
P

output:

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

result:

ok puzzle solved

Test #6:

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

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

input:

2 2 1
OO
OO

OP
PP

1 2
OP

output:

7
1 1 1
-3 1 2
-1 2 1
1 1 1
-3 1 2
-1 2 1
1 1 1

result:

ok puzzle solved

Test #8:

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

input:

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

output:

8497
8 1 1
-1 1 1
-1 1 2
-1 1 3
-1 1 4
-1 1 5
-1 1 6
-1 1 7
-1 1 8
-1 1 9
-1 1 10
-1 1 11
-1 1 12
-3 1 13
-3 2 13
-3 3 13
-3 4 13
-3 5 13
-3 6 13
-3 7 13
-3 8 13
-3 9 13
-3 10 13
-3 11 13
-3 12 13
-3 13 13
-3 14 13
-3 15 13
-3 16 13
-3 17 13
-3 18 13
-3 19 13
8 1 1
-1 1 1
-1 1 2
-1 1 3
-1 1 4
-1 1 5...

result:

ok puzzle solved

Test #9:

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

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
Wrong Answer
time: 2ms
memory: 3824kb

input:

20 20 2
pqo3Mcpvo74RFSsJszsa
znrYm92Qr8fbqhbCTOgq
4KiMYr0kLAxPGNG15x7L
QHKmq6xaJ4PU4msuRAiv
UBfS6VUO87hRnMAjGXKX
zCgknw3FfhdifmVcT6FF
GH6ohIAzZuprlC3vMDVh
mHIJ9KlQvWxt6EgGbJkA
3SwJNhRSdEeF9BNtc9k2
mZmEuriH7Rc4ccMjqI0Y
cFfI8TC1iM4PkKziLOiN
15CUjuwudnrums3c3dsl
ekL52LiFEpzmU4vaGtuX
CfrnQtWb5zAN9oQS2fj...

output:

5586
-1 20 7
-1 20 8
-1 20 9
-1 20 10
-1 20 11
-1 20 12
-1 20 13
-1 20 14
-1 20 15
-1 20 16
-1 20 6
-1 20 7
-1 20 8
-1 20 9
-1 20 10
-1 20 11
-1 20 12
-1 20 5
-1 20 6
-1 20 7
-1 20 8
-1 20 9
-1 20 10
-1 20 4
-1 20 5
-1 20 6
-1 20 7
-1 20 8
-1 20 3
-1 20 4
-1 20 5
-1 20 6
-1 20 2
-1 20 3
-1 20 4
-1 2...

result:

wrong answer puzzle remain unsolved