QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#201905 | #6398. Puzzle: Tapa | ucup-team870# | WA | 0ms | 3800kb | C++14 | 2.9kb | 2023-10-05 17:34:05 | 2023-10-05 17:34:07 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;
typedef pair<int,int> P;
const int N=200;
int v[N][N],bad[N][N];
char s[N][N];
int f2(int x){return 2*x-1;}
P q[N*N]; int ok[N*N]; P q1[N*10];
int main() {
// IOS
int n,m; cin>>n>>m;
rep(i,1,n*2-1)cin>>s[i]+1;
rep(j,1,m)v[1][f2(j)]=v[f2(n)][f2(j)]=5;
rep(i,1,n)v[f2(i)][1]=v[f2(i)][f2(m)]=5;
v[1][1]=3; v[1][f2(m)]=3;
v[f2(n)][1]=3; v[f2(n)][f2(m)]=3;
rep(i,1,n){
rep(j,1,m){
int x=f2(i),y=f2(j);
// cout<<x<<' '<<y<<'\n';
if(v[x][y]){
if(v[x][y]!=s[x][y]-'0')bad[x][y]=1;
continue;
}
if(s[x][y]!='8'){
cout<<"NO\n"; return 0;
}
}
}
rep(i,1,2*n-1){
rep(j,1,2*m-1){
if(s[i][j]=='.')s[i][j]='#';
}
}
int cnt=0;
rep(i,1,n-1){
q[++cnt]={f2(i),1}; ok[cnt]=bad[f2(i)][1];
}
rep(j,1,m-1){
q[++cnt]={f2(n),f2(j)}; ok[cnt]=bad[f2(n)][f2(j)];
}
per(i,n,2){
q[++cnt]={f2(i),f2(m)}; ok[cnt]=bad[f2(i)][f2(m)];
}
per(j,m,2){
q[++cnt]={1,f2(j)}; ok[cnt]=bad[1][f2(j)];
}
assert(cnt%2==0);
// rep(i,1,cnt){
// cout<<q[i].first<<' '<<q[i].second<<' '<<ok[i]<< '\n';
// }
// return 0;
if(*min_element(ok+1,ok+cnt+1)==1){
for(int i=1;i<cnt;i+=2){
int x=q[i].first+q[i+1].first, y=q[i].second+q[i+1].second; x/=2; y/=2;
s[x][y]='.';
}
}
else{
vector<P>vec;
int l=1;
while(l<=cnt){
if(!ok[l]){
++l; continue;
}
int r=l;
while(r<=cnt && ok[r])++r;
vec.push_back({l,r-1}); l=r;
}
if(ok[1] && ok[cnt]){
auto [v1,_]=vec.back(); auto [__,v2]=*vec.begin();
vec.pop_back();
vec.erase(vec.begin());
vec.push_back({v1,v2});
}
for(auto [l,r]:vec){
// cout<<l<<' '<<r<<"hhh\n";
int top=0;
while(1){
if(l==r){
q1[++top]=q[l];
++l; if(l>cnt)l-=cnt;
break;
}
q1[++top]=q[l];
++l; if(l>cnt)l-=cnt;
}
if(top&1){
cout<<"NO\n"; return 0;
}
for(int i=1;i<top;i+=2){
int x=q1[i].first+q1[i+1].first, y=q1[i].second+q1[i+1].second; x/=2; y/=2;
s[x][y]='.';
}
}
}
cout<<"YES\n";
rep(i,1,2*n-1){
rep(j,1,2*m-1)cout<<s[i][j]; cout<<'\n';
}
}
/*
1 1
3 1
3 1
3 3
5 3
3 3
1 5
1 3
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3588kb
input:
3 3 2.4.3 ..... 5.8.5 ..... 3.5.3
output:
YES 2.4#3 ##### 5#8#5 ##### 3#5#3
result:
ok Correct.
Test #2:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
3 3 3.4.3 ..... 5.7.5 ..... 3.5.3
output:
NO
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
2 2 2.2 ... 2.2
output:
YES 2#2 .#. 2#2
result:
ok Correct.
Test #4:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
2 50 2.4.4.4.4.5.5.5.5.5.5.5.5.4.5.5.4.4.5.5.5.5.4.5.5.5.5.5.4.4.5.4.5.5.5.5.5.5.5.5.5.5.5.4.4.5.5.4.5.3 ................................................................................................... 2.5.5.4.4.5.5.5.4.4.5.5.5.4.5.5.5.5.5.5.5.5.4.4.4.5.5.5.5.5.5.4.4.4.5.5.5.5.5.5.5.4.4.5.5.5.5.4...
output:
NO
result:
ok Correct.
Test #5:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
2 50 2.4.4.5.5.5.5.5.5.5.5.5.4.4.5.5.5.5.4.4.5.5.4.4.5.5.5.4.5.4.4.4.5.4.4.5.4.4.5.5.5.5.4.4.5.5.5.5.5.2 ................................................................................................... 3.5.4.5.5.5.5.5.5.5.5.5.5.5.4.5.5.5.5.4.5.5.5.5.4.4.5.4.5.4.5.5.5.5.5.4.4.5.5.5.4.4.5.5.5.5.5.4...
output:
NO
result:
ok Correct.
Test #6:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
50 2 3.2 ... 5.4 ... 5.5 ... 4.4 ... 5.5 ... 5.5 ... 5.5 ... 5.5 ... 5.5 ... 5.5 ... 5.5 ... 5.4 ... 5.4 ... 5.5 ... 5.5 ... 5.5 ... 5.5 ... 5.5 ... 5.4 ... 5.4 ... 5.4 ... 5.4 ... 4.4 ... 5.5 ... 5.5 ... 4.4 ... 5.4 ... 5.4 ... 5.5 ... 4.5 ... 4.5 ... 5.5 ... 5.5 ... 5.5 ... 5.5 ... 5.5 ... 5.5 ......
output:
NO
result:
ok Correct.
Test #7:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
50 2 3.3 ... 5.4 ... 5.4 ... 5.4 ... 5.4 ... 5.5 ... 4.4 ... 4.4 ... 5.5 ... 4.4 ... 5.5 ... 5.5 ... 5.5 ... 5.5 ... 4.5 ... 5.5 ... 5.5 ... 5.4 ... 5.4 ... 5.5 ... 5.4 ... 5.5 ... 5.4 ... 5.4 ... 5.5 ... 5.5 ... 4.5 ... 4.5 ... 4.5 ... 4.5 ... 5.5 ... 5.4 ... 5.4 ... 5.5 ... 5.5 ... 4.4 ... 4.4 ......
output:
NO
result:
ok Correct.
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 3616kb
input:
3 50 3.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.4.4.5.5.5.5.4.4.5.5.5.5.5.5.5.5.4.4.5.5.4.4.5.4.4.5.3 ................................................................................................... 4.8.8.8.8.8.8.8.8.8.8.8.8.8.8.7.7.7.7.7.7.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.7.7.8...
output:
NO
result:
wrong answer Jury has answer but participant has not.