QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#470658#5416. Fabulous Fungus FrenzyWRuperDWA 1ms3668kbC++145.2kb2024-07-10 15:43:012024-07-10 15:43:01

Judging History

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

  • [2024-07-10 15:43:01]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3668kb
  • [2024-07-10 15:43:01]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int MAX = 123;

int endt[MAX][MAX];
int cntt[MAX];
int nowctt;
int cntnow[MAX];
int s[MAX][MAX];

struct node{
	int n, m;
	int s[MAX][MAX];
	int cnt[MAX];
	int cntnb;
}; node a[MAX];

struct op{
	int op, x, y;
	int op2;
	
	inline void Op(int op_, int x_, int y_, int op2_){
		op = op_, x = x_, y = y_, op2 = op2_;
	}
	
	void print(){
		write(op), put(), write(x), put(), write(y), endl;
	}
	
}; 

bool del[MAX];
	
vector <op> ans;

int change(int x, int y, int x2, int y2){
	bool fl = 0;
	int op2 = 0;
	op now;
	while(x < x2){
		now.Op(-3, x, y, -1);
		swap(s[x][y], s[x + 1][y]);
		x++;
		ans.pb(now);
		op2 = 1;
	}
	while(x > x2){
		now.Op(-4, x, y, -1);
		swap(s[x][y], s[x - 1][y]);
		x--;
		ans.pb(now);
		op2 = 2;
	}
	while(y < y2){
		now.Op(-1, x, y, -1);
		swap(s[x][y], s[x][y + 1]);
		y++;
		ans.pb(now);
		op2 = 3;
	}
	while(y > y2){
		now.Op(-2, x, y, -1);
		swap(s[x][y], s[x][y - 1]);
		y--;
		op2 = 4;
		ans.pb(now);
	}
	return op2;
}

void exchange(int x, int y, int x2, int y2){
	int le = change(x, y, x2, y2);
	if(le == 1){
		change(x2 - 1, y2, x, y);
	}
	if(le == 2){
		change(x2 + 1, y2, x, y);
	}
	if(le == 3){
		change(x2, y2 - 1, x, y);
	}
	if(le == 4){
		change(x2, y2 + 1, x, y);
	}
}

int n, m, k;

void print(){
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cout<<char(s[i][j]),put();
		}endl;
	}endl;
}

void solve(){
	n = read(), m = read(), k = read();
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			char ch;
			cin>>ch;
			cntt[ch]++;
			endt[i][j] = ch;
		}
	}	
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			char ch;
			cin>>ch;
			cntnow[ch]++;
			s[i][j] = ch;
		}
	}
	
	for(int i = 1; i <= k; i++){
		a[i].n = read(), a[i].m = read();
		for(int j = 1; j <= a[i].n; j++){
			for(int k = 1; k <= a[i].m; k++){
				char ch;
				cin>>ch;
				a[i].s[j][k] = ch;
				a[i].cnt[ch]++;
			}
		}
	}
	
	while(1){
		int nowid = 0;
		for(int i = 1; i <= k; i++){
			if(del[i])	continue;
			int cst = 0;
			for(int i2 = 0; i2 < MAX; i2++){
				cst += max(0ll, a[i].cnt[i2] - cntnow[i2]);
			}
			// write(cst), endl;
			if(cst > nowctt){
				continue;
			}
			nowid = i;
		}
		if(!nowid)	break;
		int nown = a[nowid].n, nowm = a[nowid].m;
		for(int i = 1; i <= nown; i++){
			for(int j = 1; j <= nowm; j++){
				if(s[i][j] != a[nowid].s[i][j]){
					bool fll = 0;
					for(int i2 = i; i2 <= n; i2++){
						for(int j2 = 1; j2 <= m; j2++){
							if(i2 == i and j2 <= j)	continue;
							if(s[i2][j2] == a[nowid].s[i][j]){
								exchange(i, j, i2, j2);
								fll = 1;
								break;
							}
						}
						if(fll)	break;
					}
					if(!fll){
						for(int i2 = i; i2 <= n; i2++){
							for(int j2 = 1; j2 <= m; j2++){
								if(i2 == i and j2 <= j)	continue;
								if(s[i2][j2] == -1){
									exchange(i, j, i2, j2);
									fll = 1;
									break;
								}
							}
							if(fll)	break;
						}
						if(!fll)	puts("fuckyou1"), print();
					}
				}
			}
		}
		op nowop;
		nowop.Op(nowid, 1, 1, -1);
		ans.pb(nowop);
		for(int i = 1; i <= nown; i++){
			for(int j = 1; j <= nowm; j++){
				if(s[i][j] != -1)	nowctt++, cntnow[s[i][j]]--;
				s[i][j] = -1;
			}
		}
		for(int i = 1; i <= nown; i++){
			for(int j = 1; j <= nowm; j++){
				if(cntnow[a[nowid].s[i][j]] != 0){
					for(int i2 = 1; i2 <= n; i2++){
						for(int j2 = 1; j2 <= m; j2++){
							if(s[i2][j2] == a[nowid].s[i][j]){
								exchange(i2, j2, i, j);
								ans.pb(nowop);
								cntnow[a[nowid].s[i][j]]--;
								nowctt++;
								s[i][j] = -1;
							}
						}
					}
				}
			}
		}
		// write(nowid), endl;
		// print();
		del[nowid] = 1;
	}
	int cst = 0;
	for(int i = 0; i < MAX; i++){
		cst += max(0ll, cntt[i] - cntnow[i]);
	}
	if(cst > nowctt){
		puts("-1");
		return ;
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(s[i][j] == endt[i][j])	continue;
			bool flll = 0;
			for(int i2 = i; i2 <= n; i2++){
				for(int j2 = 1; j2 <= m; j2++){
					if(i2 == i and j2 <= j)	continue;
					if(s[i2][j2] == endt[i][j]){
						exchange(i, j, i2, j2);
						flll = 1;
						break;
					}
				}
				if(flll)	break;
			}
			if(!flll and s[i][j] != -1){
				for(int i2 = i; i2 <= n; i2++){
					for(int j2 = 1; j2 <= m; j2++){
						if(i2 == i and j2 <= j)	continue;
						if(s[i2][j2] == -1){
							exchange(i, j, i2, j2);
							flll = 1;
							break;
						}
					}
					if(flll)	break;
				}
				// if(!flll)	puts("fuckyou2");
			}
		}
	}
	// print();
	// write(cst), put(), write(nowctt), endl;
	write(ans.size()), endl;
	for(int i = ans.size() - 1; i >= 0; i--){
		ans[i].print();
	}
}

signed main(){
	int t = 1;
	while(t--)	solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 3 1
OOO
GOG
BGB

OOO
GGG
BBB

3 1
B
G
B

output:

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

result:

ok puzzle solved

Test #2:

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

input:

2 2 1
OO
OO

PP
PP

1 2
OP

output:

-1

result:

ok puzzle solved

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3652kb

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:

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

result:

wrong answer puzzle remain unsolved