QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#709602 | #9478. Shift Puzzle | ucup-team902 | RE | 0ms | 3952kb | C++20 | 2.0kb | 2024-11-04 15:43:36 | 2024-11-04 15:43:38 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=100;
int n;
char s[N+5][N+5];
char t[N+5][N+5];
struct oper{
int t,x;
oper(int t=0,int x=0):t(t),x(x){}
};
vector<oper> op;
vector<pair<int,int>> dif[2];
void work(int tp,int x,int c){
for(int i=0;i<c;i++)
op.push_back({tp,x});
if(tp==1){
static char tmp[N+5];
for(int i=0;i<n;i++) tmp[i]=s[x][i];
for(int i=0;i<n;i++) s[x][(i+c)%n]=tmp[i];
}
else{
static char tmp[N+5];
for(int i=0;i<n;i++) tmp[i]=s[i][x];
for(int i=0;i<n;i++) s[(i+c)%n][x]=tmp[i];
}
}
void rotate(int x1,int y1,int x2,int y2,int tp){
if(tp==0){
work(1,x1,(y2-y1+n)%n);
work(2,y2,(x1-x2+n)%n);
work(1,x1,(y1-y2+n)%n);
work(2,y2,(x2-x1+n)%n);
}
else{
work(2,y2,(x1-x2+n)%n);
work(1,x1,(y2-y1+n)%n);
work(2,y2,(x2-x1+n)%n);
work(1,x1,(y1-y2+n)%n);
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%s",s[i]);
for(int j=0;j<n;j++)
scanf("%s",t[j]);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(s[i][j]!=t[i][j]){
dif[s[i][j]=='#'].push_back({i,j});
}
if(dif[0].size()!=dif[1].size()){
puts("No");
return 0;
}
for(int i=0;i<dif[0].size();i++){
auto [x1,y1]=dif[0][i];
auto [x2,y2]=dif[1][i];
// printf("%d %d %d %d\n",x1,y1,x2,y2);
if(x1!=x2&&y1!=y2){
rotate(x1,y1,x2,y2,s[x1][y1]!=s[x1][y2]);
}
else if(x1!=x2){
rotate(x1,(y1-1+n)%n,x2,y1,s[x1][(y1-1+n)%n]==s[x1][y1]);
}
else if(y1!=y2){
rotate(x1,y1,(x1+1)%n,y2,s[(x2+1)%n][y1]!=s[x1][y1]);
}
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
assert(s[i][j]==t[i][j]);
puts("Yes");
printf("%d\n",op.size());
for(auto [t,x]:op){
printf("%d %d\n",t,x+1);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3896kb
input:
3 .#. #.# .#. #.# ... #.#
output:
Yes 24 2 2 2 2 1 1 2 2 1 1 1 1 2 1 2 1 1 1 2 1 1 1 1 1 1 3 1 3 2 3 1 3 2 3 2 3 2 2 2 2 1 3 1 3 2 2 1 3
result:
ok AC
Test #2:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
3 .#. #.# .#. .#. #.# .#.
output:
Yes 0
result:
ok AC
Test #3:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
13 ............. ....#####.... ......#...... ......#...... ......#...... ......#...... ............. ....#...#.... ....#...#.... ....#...#.... ....#...#.... .....###..... ............. ....####..... ....#...#.... ....####..... ....#........ ....#........ ............. .....###..... ....#...#.... ......
output:
No
result:
ok AC
Test #4:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
3 #.# #.# ### #.# .#. ###
output:
No
result:
ok AC
Test #5:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
4 .#.. .#.. .... ...# .... ..#. #... ....
output:
No
result:
ok AC
Test #6:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
4 .... .... .... .#.. ..## ##.# #### ..##
output:
No
result:
ok AC
Test #7:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
2 .. .. .. ..
output:
Yes 0
result:
ok AC
Test #8:
score: -100
Runtime Error
input:
3 .## ##. .#. ##. ..# .##