QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#656407#9478. Shift Puzzleucup-team4938#RE 0ms3968kbC++145.3kb2024-10-19 12:49:392024-10-19 12:49:39

Judging History

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

  • [2024-10-19 12:49:39]
  • 评测
  • 测评结果：RE
  • 用时：0ms
  • 内存：3968kb
查看
  • [2024-10-19 12:49:39]
  • 提交

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++)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++){
		// cout<<i<<" a\n";
		// for(int ii=1;ii<=n;ii++){
			// for(int jj=1;jj<=n;jj++)cout<<a[ii][jj];cout<<"\n";
		// }
		bool fl=1;
		for(int j=1;j<n;j++)fl&=(a[i][j]==b[i][j]);
		if(fl)continue;
		for(int j=n;j;j--){
			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});
			if(!a[i][n]){
				for(int l=1;l<=n;l++)tmp[nxt[l]]=a[l][n];
				for(int l=1;l<=n;l++)a[l][n]=tmp[l];
				ans.pb({2,n});
				while(i==n&&!a[i][n]){
					for(int l=1;l<=n;l++)tmp[nxt[l]]=a[l][n];
					for(int l=1;l<=n;l++)a[l][n]=tmp[l];
					ans.pb({2,n});
				}
			}
		}
		fl=1;
		for(int j=1;j<n;j++)fl&=(a[i][j]==b[i][j]);
		if(fl)continue;
		// cout<<i<<" a\n";
		// for(int ii=1;ii<=n;ii++){
			// for(int jj=1;jj<=n;jj++)cout<<a[ii][jj];cout<<"\n";
		// }
		for(int j=n-1;j;j--){
			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});
			if(a[i][n]!=b[i][j]){
				bool fl=0;
				for(int k=n;k>=1;k--)if(i!=k){
					for(int l=n;l>=(k<=i?n:1);l--)if(a[k][l]==b[i][j]){
						int u=k,v=l;
						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];
						}
						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];
						}
						// 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;
				}
				// if(!fl){
					// cout<<i<<" "<<j<<" err\n";
					// for(int ii=1;ii<=n;ii++){
						// for(int jj=1;jj<=n;jj++)cout<<a[ii][jj];cout<<"\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});
		// cout<<i<<" "<<ans.size()<<"\n";
	}
	// 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();
}
源文件, 语言: C++14

详细

Test #1:

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

input:

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

output:

Yes
14
1 1
2 3
1 1
1 1
1 1
2 3
1 1
2 3
1 1
1 3
2 1
2 1
1 1
1 1

result:

ok AC

Test #2:

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

input:

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

output:

Yes
23
1 2
1 2
2 3
1 2
2 3
1 2
2 3
2 3
1 2
1 2
1 3
2 3
1 3
1 3
2 3
1 3
2 3
1 3
2 3
1 3
1 2
2 1
2 1

result:

ok AC

Test #3:

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

input:

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

output:

No

result:

ok AC

Test #4:

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

input:

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

output:

No

result:

ok AC

Test #5:

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

input:

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

output:

No

result:

ok AC

Test #6:

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

input:

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

output:

No

result:

ok AC

Test #7:

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

input:

2
..
..
..
..

output:

Yes
0

result:

ok AC

Test #8:

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

input:

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

output:

Yes
13
1 3
2 3
1 3
1 3
1 3
2 3
1 3
2 3
1 3
1 3
2 1
2 1
1 2

result:

ok AC

Test #9:

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

input:

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

output:

Yes
9
1 3
1 3
1 3
2 3
1 3
1 3
2 3
2 3
1 3

result:

ok AC

Test #10:

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

input:

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

output:

Yes
23
1 1
1 1
1 1
2 3
1 1
2 3
1 1
2 3
1 1
1 2
2 3
1 2
1 2
1 2
1 2
2 3
2 3
1 2
1 3
1 3
1 2
1 1
1 1

result:

ok AC

Test #11:

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

input:

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

output:

Yes
39
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 4
2 4
1 1
1 2
1 2
1 2
2 4
1 2
1 3
1 3
1 3
1 3
2 4
1 3
1 3
2 4
2 4
2 4
1 3
1 3
1 4
1 4
2 4
1 4
1 4
1 4
2 4
2 4
1 4
2 4
1 4
1 4

result:

ok AC

Test #12:

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

input:

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

output:

Yes
54
1 1
2 4
1 1
1 1
2 4
1 1
1 1
1 1
1 4
1 4
1 4
2 4
1 1
2 4
1 1
1 2
1 2
2 4
1 2
2 4
1 2
1 2
1 2
1 2
1 4
2 4
2 4
1 2
1 3
1 3
1 3
1 3
1 3
2 4
2 4
2 4
1 3
2 4
2 4
2 4
1 3
1 3
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: -100
Runtime Error

input:

2
.#
.#
#.
#.

output:

result:
English 繁體中文 简体中文

服务器时间: 2025-01-21 00:56:14 | 开源项目