QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#656233#9478. Shift Puzzleucup-team4938#RE 3ms4164kbC++144.7kb2024-10-19 11:54:122024-10-19 11:54:19

Judging History

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

  • [2024-10-19 11:54:19]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:4164kb
  • [2024-10-19 11:54:12]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define mod 998244353ll
#define pii pair<int,int>
#define fi first
#define se second
#define mems(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define db double
using namespace std;
const int maxn=85;
const int inf=1e18;
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<<3)+(x<<1)+(ch-48);ch=getchar();}
	return x*f;
}
bool Mbe;

int n;
char s[maxn][maxn],t[maxn][maxn];
int a[maxn][maxn],b[maxn][maxn],c[maxn][maxn],d[maxn][maxn];
int tmp[maxn];
vector<pii> ans,res;
int pre[maxn],nxt[maxn];
void work(){
	n=read();
	for(int i=1;i<=n;i++)pre[i]=i-1,nxt[i]=i+1;
	pre[1]=n,nxt[n]=1;
	for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++)scanf("%s",t[i]+1);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)a[i][j]=s[i][j]=='.';
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)b[i][j]=t[i][j]=='.';
	}
	int num=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)num+=a[i][j];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)num-=b[i][j];
	}
	if(num){
		puts("No");
		return ;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)num+=a[i][j];
	}
	if(num<n){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++)a[i][j]=1-a[i][j],b[i][j]=1-b[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)c[i][j]=a[i][j];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)d[i][j]=b[i][j];
	}
	// for(int i=1;i<=n;i++){
		// for(int j=1;j<=n;j++)cout<<b[i][j];cout<<"\n";
	// }
	for(int i=1;i<=n;i++)if(!b[i][n]){
		bool fl=0;
		for(int j=1;j<=n;j++){
			for(int k=1;k<n;k++)if(b[j][k]){
				int u=j,v=k;
				while(u!=i){
					for(int l=1;l<=n;l++)tmp[pre[l]]=b[l][v];
					for(int l=1;l<=n;l++)b[l][v]=tmp[l];
					res.pb({2,v});
					u=pre[u];
				}
				while(v!=n){
					for(int l=1;l<=n;l++)tmp[pre[l]]=b[u][l];
					for(int l=1;l<=n;l++)b[u][l]=tmp[l];
					res.pb({1,u});
					v=pre[v];
				}
				fl=1;break;
			}
			if(fl)break;
		}
	}
	// for(int i=1;i<=n;i++){
		// for(int j=1;j<=n;j++)cout<<b[i][j];cout<<"\n";
	// }
	reverse(res.begin(),res.end());
	// for(auto[op,x]:res){
		// if(op==1){
			// for(int l=1;l<=n;l++)tmp[nxt[l]]=b[x][l];
			// for(int l=1;l<=n;l++)b[x][l]=tmp[l];
		// }else{
			// for(int l=1;l<=n;l++)tmp[nxt[l]]=b[l][x];
			// for(int l=1;l<=n;l++)b[l][x]=tmp[l];
		// }
	// }
	// for(int i=1;i<=n;i++){
		// for(int j=1;j<=n;j++)cout<<a[i][j];cout<<"\n";
	// }
	// for(int i=1;i<=n;i++){
		// for(int j=1;j<=n;j++)cout<<b[i][j];cout<<"\n";
	// }
	// return ;
	for(int i=1;i<=n;i++){
		for(int j=1;j<n;j++)if(a[i][j]!=b[i][j]){
			bool fl=0;
			for(int k=n;k>=1;k--){
				for(int l=n;l>=(k<i?n:(k==i?j+1:1));l--)if(a[k][l]==b[i][j]){
					int u=k,v=l,vv=j;
					while(v!=n){
						for(int l=1;l<=n;l++)tmp[nxt[l]]=a[u][l];
						for(int l=1;l<=n;l++)a[u][l]=tmp[l];
						ans.pb({1,u});
						v=nxt[v];
						if(i==k)vv=nxt[vv];
					}
					if(i==k){
						for(int l=1;l<=n;l++)tmp[nxt[l]]=a[l][v];
						for(int l=1;l<=n;l++)a[l][v]=tmp[l];
						ans.pb({2,v});
						u=nxt[u];
					}
					while(vv!=n){
						for(int l=1;l<=n;l++)tmp[nxt[l]]=a[i][l];
						for(int l=1;l<=n;l++)a[i][l]=tmp[l];
						ans.pb({1,i});
						vv=nxt[vv];
					}
					// cout<<u<<" "<<v<<"\n";
					while(u!=i){
						for(int l=1;l<=n;l++)tmp[nxt[l]]=a[l][v];
						for(int l=1;l<=n;l++)a[l][v]=tmp[l];
						ans.pb({2,v});
						u=nxt[u];
					}
					while(v!=j){
						for(int l=1;l<=n;l++)tmp[nxt[l]]=a[u][l];
						for(int l=1;l<=n;l++)a[u][l]=tmp[l];
						ans.pb({1,u});
						v=nxt[v];
					}
				// cout<<i<<" "<<j<<" "<<k<<" "<<l<<"\n";
				// for(int ii=1;ii<=n;ii++){
					// for(int jj=1;jj<=n;jj++)cout<<a[ii][jj];cout<<"\n";
				// }
					fl=1;break;
				}
				if(fl)break;
			}
		}
	}
	// cout<<a[5][1]<<" "<<b[5][1]<<"\n";
	for(pii p:res)ans.pb(p);
	puts("Yes");printf("%lld\n",(int)ans.size());
	assert(ans.size()<=n*n*n);
	for(auto[fl,x]:ans)printf("%lld %lld\n",fl,x);
	// for(auto[op,x]:ans){
		// if(op==1){
			// for(int l=1;l<=n;l++)tmp[nxt[l]]=c[x][l];
			// for(int l=1;l<=n;l++)c[x][l]=tmp[l];
		// }else{
			// for(int l=1;l<=n;l++)tmp[nxt[l]]=c[l][x];
			// for(int l=1;l<=n;l++)c[l][x]=tmp[l];
		// }
	// }
	// for(int i=1;i<=n;i++){
		// for(int j=1;j<=n;j++)cout<<c[i][j];
		// cout<<"\n";
	// }
	// for(int i=1;i<=n;i++){
		// for(int j=1;j<=n;j++)assert(c[i][j]==d[i][j]);
	// }
}

// \
444

bool Med;
int T;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	
//	cerr<<(&Mbe-&Med)/1048576.0<<" MB\n";
	
	T=1;
	while(T--)work();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
.#.
#.#
.#.
#.#
...
#.#

output:

Yes
16
1 3
1 1
1 1
2 3
1 1
2 3
1 3
2 3
2 3
1 3
1 3
1 3
2 1
2 1
1 1
1 1

result:

ok AC

Test #2:

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

input:

3
.#.
#.#
.#.
.#.
#.#
.#.

output:

Yes
26
1 2
1 2
2 3
2 3
1 2
1 3
1 2
2 3
2 3
1 2
1 2
2 3
1 3
1 3
2 3
2 3
1 3
2 3
1 3
2 3
2 3
1 3
1 3
1 2
2 1
2 1

result:

ok AC

Test #3:

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

input:

13
.............
....#####....
......#......
......#......
......#......
......#......
.............
....#...#....
....#...#....
....#...#....
....#...#....
.....###.....
.............
....####.....
....#...#....
....####.....
....#........
....#........
.............
.....###.....
....#...#....
......

output:

No

result:

ok AC

Test #4:

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

input:

3
#.#
#.#
###
#.#
.#.
###

output:

No

result:

ok AC

Test #5:

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

input:

4
.#..
.#..
....
...#
....
..#.
#...
....

output:

No

result:

ok AC

Test #6:

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

input:

4
....
....
....
.#..
..##
##.#
####
..##

output:

No

result:

ok AC

Test #7:

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

input:

2
..
..
..
..

output:

Yes
0

result:

ok AC

Test #8:

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

input:

3
.##
##.
.#.
##.
..#
.##

output:

Yes
15
1 3
2 3
1 3
2 3
2 3
1 3
1 3
2 3
2 3
1 3
1 3
1 3
2 1
2 1
1 2

result:

ok AC

Test #9:

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

input:

3
...
#..
..#
...
#..
#..

output:

Yes
6
2 3
1 3
1 3
2 3
2 3
1 3

result:

ok AC

Test #10:

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

input:

3
..#
.##
###
#.#
.##
#.#

output:

Yes
25
1 1
1 1
2 3
1 1
1 1
2 3
1 1
1 1
1 3
1 2
1 2
2 3
2 3
1 2
2 3
1 3
1 3
2 3
2 3
1 3
1 3
1 3
1 2
1 1
1 1

result:

ok AC

Test #11:

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

input:

4
....
#...
...#
#.#.
#...
....
.#..
.##.

output:

Yes
36
1 4
1 1
1 1
1 1
2 4
1 1
1 4
1 2
1 2
1 2
2 4
2 4
1 2
1 3
1 3
2 4
2 4
2 4
1 3
1 3
2 4
1 4
1 4
1 4
2 4
2 4
2 4
1 4
1 4
2 4
1 4
2 4
2 4
2 4
1 4
1 4

result:

ok AC

Test #12:

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

input:

4
#.#.
##..
....
#..#
....
...#
.#.#
#.##

output:

Yes
54
1 1
1 1
2 4
1 1
1 1
1 2
1 2
1 2
2 4
2 4
1 2
1 4
1 2
1 2
2 4
2 4
1 2
1 2
1 3
1 3
2 4
2 4
2 4
1 3
1 3
1 4
1 4
1 3
2 4
2 4
2 4
1 3
1 3
1 3
1 4
2 4
1 4
1 4
2 4
2 4
2 4
1 4
1 4
1 4
1 4
2 3
1 3
1 3
2 2
2 2
1 2
2 1
2 1
2 1

result:

ok AC

Test #13:

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

input:

2
.#
.#
#.
#.

output:

Yes
6
1 1
2 2
1 1
1 2
2 2
1 2

result:

ok AC

Test #14:

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

input:

3
##.
.##
...
...
#..
###

output:

Yes
24
1 1
2 3
1 1
1 1
1 2
1 2
2 3
2 3
1 2
1 2
2 3
2 3
1 2
1 2
1 3
1 3
2 3
1 3
1 3
2 3
1 3
1 3
1 3
2 1

result:

ok AC

Test #15:

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

input:

3
.#.
##.
.#.
#.#
..#
#..

output:

Yes
18
1 3
1 1
1 1
2 3
1 1
1 2
1 2
2 3
2 3
1 2
1 3
1 3
2 3
2 3
1 3
1 2
1 1
1 1

result:

ok AC

Test #16:

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

input:

3
#.#
#..
#..
.#.
.##
.#.

output:

Yes
24
1 1
1 1
2 3
1 1
1 3
1 3
1 1
2 3
1 1
1 1
1 2
2 3
2 3
1 2
1 2
2 3
1 3
2 3
2 3
1 3
1 3
1 2
2 1
2 1

result:

ok AC

Test #17:

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

input:

4
####
#..#
...#
.#..
....
.##.
###.
#.##

output:

Yes
63
1 1
1 1
1 1
2 4
1 1
1 4
1 1
1 1
2 4
1 1
1 1
1 4
1 4
1 1
2 4
1 1
1 1
1 1
1 2
1 2
2 4
2 4
1 2
1 2
1 4
1 2
2 4
2 4
1 2
1 2
1 2
1 4
1 3
1 3
1 3
2 4
2 4
2 4
1 3
1 3
1 3
2 4
2 4
2 4
1 3
1 3
1 3
2 4
2 4
2 4
1 3
1 3
1 3
1 4
2 4
1 4
2 4
2 4
2 4
1 4
1 4
1 4
2 1

result:

ok AC

Test #18:

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

input:

4
.#.#
##..
.#.#
.##.
#.#.
..##
#.#.
#..#

output:

Yes
58
1 4
1 1
1 1
1 1
2 4
1 1
1 1
2 4
1 1
1 1
1 1
1 2
1 2
2 4
2 4
1 2
1 2
1 3
1 3
1 3
2 4
2 4
2 4
1 3
1 3
1 3
2 4
2 4
2 4
1 3
1 3
1 4
1 3
2 4
2 4
2 4
1 3
1 3
1 3
1 4
1 4
2 4
1 4
1 4
1 4
2 4
2 4
1 4
1 4
1 4
1 4
1 4
2 2
1 2
1 2
2 2
2 2
2 2

result:

ok AC

Test #19:

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

input:

19
.######.######..###
...###.##.###.#####
.#.####..#.##...###
.#####.##.######.##
.##.#############..
.#.....##..#.##.#.#
#####.###..#.###.##
#.####.#...##..#.##
.######.##.##..####
.#.###.###.###..###
#######.###.#..###.
#####.###.####.##.#
..#.######..###..#.
#.#.#..####..###.#.
########.####..##...

output:

No

result:

ok AC

Test #20:

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

input:

21
#####################
#####################
#####################
#####################
#####################
#####################
#####################
#########.###########
#####################
#####################
#####################
#####################
#####################
###########...

output:

No

result:

ok AC

Test #21:

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

input:

26
##.###....#######.....#...
.#.##.#####..#..#..###.###
.#.#####.##.##.#.#.##.#..#
###.###...##...#.#....#.#.
.##..###..#.##.#.##..#.#.#
#..##...##.#...####...####
##.#..###.#.####...###....
.##..#..##.##..#.##...#.##
####.###..#.#####..#####..
.#.#.##..###.###..###.####
##.##.#..#..#....###..###.
...

output:

No

result:

ok AC

Test #22:

score: 0
Accepted
time: 3ms
memory: 4164kb

input:

35
####.##.###.####..##.##############
####.####.##############.######.###
###########..######.###.######.###.
#.#.####.##.#####...###############
################.#####.############
#######...#.####.###..######.######
#.##.#############.####.######.#.##
##..####.####.#####################
#####.##....

output:

Yes
21337
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
2 35
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
2 35
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
...

result:

ok AC

Test #23:

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

input:

34
.........#.................#......
...#.#............................
..........#.............#.........
.................................#
.......#..........................
..................................
.......................#..........
.................#................
....................

output:

Yes
3671
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
2 34
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 34
1 34
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
2 34
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1...

result:

ok AC

Test #24:

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

input:

23
####.####.#.#.#########
..####.##.##.###.######
#.###...#.#.###.###.###
###.#####.####..#######
#.#...##.######..#.#.##
.####.##.###########..#
##.#....##..###.#.#..##
##.#.####...##.###..#.#
##.###..###########.###
###.###..###.#.#.#.##.#
#.####.###..##.#####..#
###.######.##.####..#.#
.###.####...

output:

Yes
8256
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
2 23
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
2 23
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 23
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
2 23
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1...

result:

ok AC

Test #25:

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

input:

20
#....###......##...#
.......##...#...#..#
......#.....#.#.....
..#....##.#..#.#....
#..#...#.#...##.#...
...#...#...##.....#.
#####.#........#....
....##...#.#..#.....
.#.#........#....#..
.#.#.###...#........
#.....#..##.##......
##....##..#.........
.#.#..............#.
#..............#..#.
##....

output:

Yes
4767
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
2 20
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
2 20
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
2 20
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
...

result:

ok AC

Test #26:

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

input:

12
##..#.......
.#.##.###.#.
##.#..#.####
##.###..###.
.#.#.##.#.##
##.###.#...#
#..###..####
..####.#####
#.#.##.##.#.
.#.##.####..
.#.....#####
###.#..##.#.
.##.#######.
..###.#.####
#.###...##..
.#...##.#.##
.#.#########
#...##.#.##.
.##.##...##.
..####.#.###
...#.#######
..#.......#.
..#.#..##.#...

output:

Yes
1511
1 12
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
2 12
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
2 12
1 1
1 1
1 1
1 1
1 12
1 12
1 1
1 1
1 1
1 1
1 1
1 1
2 12
1 1
1 1
1 1
1 1
1 1
1 1
1 12
1 1
1 1
1 1
1 1
1 1
2 12
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
2 12
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 ...

result:

ok AC

Test #27:

score: -100
Runtime Error

input:

44
###...##.#....##.#####.##.##...####.##....##
#.#...##..#.#.##..#.###.......####..#..#..#.
..#.########..##.#.....##.....#..##...#.#.#.
#.#.##.#.#.#.#....#.#.######.#....#......###
#.#.#.##...##.#..#.#..#######.#.###..###.###
###..#...#...#........##..#...#.##..#..#..##
..##.#..#..#####......#..##...

output:


result: