QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#310411 | #6398. Puzzle: Tapa | PlentyOfPenalty# | TL | 1ms | 3836kb | C++20 | 3.4kb | 2024-01-21 13:00:06 | 2024-01-21 13:00:06 |
Judging History
answer
#include<bits/stdc++.h>
#define all(x) begin(x),end(x)
using namespace std;
const int N=55;
int n,m,a[N][N];
string str;
char mp[N<<1][N<<1];
struct atom{
int x,y;
};
void giveup(){
cout<<"NO"<<endl;
exit(0);
}
bool empty(){
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(a[i][j])return false;
return true;
}
void setup(const atom &a,const atom &b){
// fprintf(stderr,"setup %d %d : %d %d\n",a.x,a.y,b.x,b.y);
assert(a.x==b.x||a.y==b.y);
if(a.x==b.x){
mp[a.x<<1][min(a.y,b.y)<<1|1]='.';
}else{
mp[min(a.x,b.x)<<1|1][a.y<<1]='.';
}
}
bool solve_border(vector<pair<int,atom>> &b){
for(int i=0;i<b.size();i++)
if(b[i].first){
if(i+1<b.size()&&b[i+1].first){
b[i+1].first=0;
}else{
return false;
}
}
for(int i=0;i<b.size();i++)
if(b[i].first){
setup(b[i].second,b[i+1].second);
}
return true;
}
vector<pair<vector<vector<int>>,pair<int,int>>> posture={{{
{0,0,-1},
{0,1,1},
{0,0,-1}
},{0,1}},{{
{-1,0,0},
{1,1,0},
{-1,0,0}
},{0,-1}},{{
{0,0,0},
{0,1,0},
{-1,1,-1}
},{1,0}},{{
{-1,1,-1},
{0,1,0},
{0,0,0}
},{-1,0}},{{
{0,0,-1},
{0,1,-1},
{0,1,-1},
{0,0,-1},
},{1,0}},{{
{-1,0,0},
{-1,1,0},
{-1,1,0},
{-1,0,0},
},{1,0}},{{
{0,0,0,0},
{0,1,1,0},
{-1,-1,-1,-1},
},{0,1}},{{
{-1,-1,-1,-1},
{0,1,1,0},
{0,0,0,0},
},{0,-1}}
};
int main(){
#ifdef memset0
freopen("E.in","r",stdin);
#endif
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m;
for(int i=0;i<n*2-1;i++){
cin>>str;
for(int j=0;j<m*2-1;j++)mp[i][j]=str[j]=='.'?'#':str[j];
}
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
a[i][j]=mp[i<<1][j<<1]-'0';
a[i][j]=a[i][j]==2||a[i][j]==4||a[i][j]==7;
// cerr<<a[i][j]<<" \n"[j+1==m];
}
bool fl=false;
for(int op=0;op<4;op++){
vector<pair<int,atom>> b;
for(int i=0;i<n;i++)b.emplace_back(a[i][0],atom{i,0});
for(int i=1;i<m;i++)b.emplace_back(a[n-1][i],atom{n-1,i});
for(int i=n-2;i>=0;i--)b.emplace_back(a[i][m-1],atom{i,m-1});
for(int i=m-2;i>=1;i--)b.emplace_back(a[0][i],atom{0,i});
if(op&2)reverse(all(b));
if(op&1)b.insert(b.end(),b.front()),b.erase(b.begin());
if(solve_border(b)){
fl=true;
break;
}
}
if(!fl)giveup();
for(int i=0;i<n;i++)a[i][0]=a[i][m-1]=0;
for(int i=0;i<m;i++)a[0][i]=a[n-1][i]=0;
#define pt p.first
while(!empty()){
// for(int i=0;i<n;i++)for(int j=0;j<m;j++)cout<<a[i][j]<<" \n"[j+1==m];
// for(int i=0;i<n*2-1;i++){
// for(int j=0;j<m*2-1;j++)cout<<mp[i][j];
// cout<<endl;
// }
for(int i=1;i<n-1;i++)
for(int j=1;j<m-1;j++)
if(a[i][j]&&!a[i-1][j]&&!a[i+1][j]&&!a[i][j-1]&&!a[i][j+1]){
giveup();
}
bool skip=false;
for(int i=1;!skip&&i<n-1;i++)
for(int j=1;j<m-1;j++)
if(a[i][j]){
for(const auto &p:posture){
bool ok=true;
for(int x=0;ok&&x<pt.size();x++)
for(int y=0;y<pt[x].size();y++)
if(pt[x][y]!=-1&&a[i+x-1][j+y-1]!=pt[x][y]){
ok=false;
break;
}
if(ok){
// cerr<<"! "<<p.second.first<<" "<<p.second.second<<endl;
a[i][j]=a[i+p.second.first][j+p.second.second]=0;
setup({i,j},{i+p.second.first,j+p.second.second});
skip=true;
break;
}
}
}
}
cout<<"YES"<<endl;
for(int i=0;i<n*2-1;i++){
for(int j=0;j<m*2-1;j++)cout<<mp[i][j];
cout<<endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3756kb
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: 3548kb
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: 3548kb
input:
2 2 2.2 ... 2.2
output:
YES 2#2 .#. 2#2
result:
ok Correct.
Test #4:
score: 0
Accepted
time: 0ms
memory: 3564kb
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: 3780kb
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: 1ms
memory: 3628kb
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: 3836kb
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: 0
Accepted
time: 0ms
memory: 3628kb
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:
YES 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#...
result:
ok Correct.
Test #9:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
3 50 2.4.4.4.5.4.4.4.4.4.4.5.5.4.4.5.5.4.4.5.5.5.4.4.5.5.5.4.4.5.5.4.4.4.4.5.5.5.5.5.5.4.4.5.5.5.5.4.4.3 ................................................................................................... 5.7.7.8.7.7.7.7.8.8.8.8.7.7.8.7.7.8.8.8.8.7.7.8.8.8.7.7.8.7.7.8.8.8.8.7.7.8.8.7.7.8.8.8.7.7.8.8...
output:
YES 2.4#4.4#5#4.4#4.4#4.4#5#5#4.4#5#5#4.4#5#5#5#4.4#5#5#5#4.4#5#5#4.4#4.4#5#5#5#5#5#5#4.4#5#5#5#5#4.4#3 ################################################################################################### 5#7.7#8#7.7#7.7#8#8#8#8#7.7#8#7.7#8#8#8#8#7.7#8#8#8#7.7#8#7.7#8#8#8#8#7.7#8#8#7.7#8#8#8#7.7#8#8#...
result:
ok Correct.
Test #10:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
50 3 3.5.3 ..... 5.8.5 ..... 5.8.5 ..... 5.8.5 ..... 5.8.5 ..... 5.8.5 ..... 5.8.4 ..... 5.8.4 ..... 4.8.5 ..... 4.7.5 ..... 5.7.5 ..... 5.8.5 ..... 5.8.4 ..... 5.8.4 ..... 5.8.5 ..... 5.8.5 ..... 5.8.5 ..... 5.8.5 ..... 5.8.5 ..... 4.8.5 ..... 4.7.5 ..... 5.7.5 ..... 5.8.5 ..... 5.8.5 ..... 5.8.5 ....
output:
YES 3#5#3 ##### 5#8#5 ##### 5#8#5 ##### 5#8#5 ##### 5#8#5 ##### 5#8#5 ##### 5#8#4 ####. 5#8#4 ##### 4#8#5 .#### 4#7#5 ##.## 5#7#5 ##### 5#8#5 ##### 5#8#4 ####. 5#8#4 ##### 5#8#5 ##### 5#8#5 ##### 5#8#5 ##### 5#8#5 ##### 5#8#5 ##### 4#8#5 .#### 4#7#5 ##.## 5#7#5 ##### 5#8#5 ##### 5#8#5 ##### 5#8#5 ##...
result:
ok Correct.
Test #11:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
50 3 2.4.3 ..... 4.8.5 ..... 4.8.5 ..... 5.8.5 ..... 4.7.4 ..... 4.7.4 ..... 4.8.5 ..... 4.8.4 ..... 5.8.4 ..... 4.7.5 ..... 4.7.5 ..... 5.8.5 ..... 5.8.5 ..... 5.8.4 ..... 5.8.4 ..... 5.8.5 ..... 5.8.5 ..... 5.7.5 ..... 5.7.5 ..... 5.8.5 ..... 5.8.5 ..... 5.8.5 ..... 4.8.5 ..... 4.7.5 ..... 4.7.4 ....
output:
YES 2.4#3 ##### 4#8#5 .#### 4#8#5 ##### 5#8#5 ##### 4#7#4 .#.#. 4#7#4 ##### 4#8#5 .#### 4#8#4 ####. 5#8#4 ##### 4#7#5 .#.## 4#7#5 ##### 5#8#5 ##### 5#8#5 ##### 5#8#4 ####. 5#8#4 ##### 5#8#5 ##### 5#8#5 ##### 5#7#5 ##.## 5#7#5 ##### 5#8#5 ##### 5#8#5 ##### 5#8#5 ##### 4#8#5 .#### 4#7#5 ##.## 4#7#4 .#...
result:
ok Correct.
Test #12:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
10 10 2.4.4.4.5.5.4.4.5.2 ................... 5.7.8.8.7.8.7.7.8.4 ................... 4.7.8.8.7.8.8.8.8.5 ................... 4.8.8.8.7.7.8.8.8.4 ................... 5.8.7.7.7.7.8.8.7.4 ................... 4.7.7.8.8.8.8.8.7.4 ................... 4.8.7.8.8.7.7.7.8.4 ................... 5.8.7.8.8.7.8....
output:
YES 2.4#4.4#5#5#4.4#5#2 ##################. 5#7#8#8#7#8#7.7#8#4 ##.#####.########## 4#7#8#8#7#8#8#8#8#5 .################## 4#8#8#8#7.7#8#8#8#4 ##################. 5#8#7.7#7.7#8#8#7#4 ################.## 4#7.7#8#8#8#8#8#7#4 .#################. 4#8#7#8#8#7#7.7#8#4 ####.#####.######## 5#8#7#8#8#7#8#8#...
result:
ok Correct.
Test #13:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
10 10 3.5.5.5.5.5.5.4.4.3 ................... 5.7.7.8.8.7.8.7.7.4 ................... 5.8.8.7.7.7.7.7.8.4 ................... 5.8.7.7.8.8.8.7.7.5 ................... 5.8.8.7.7.7.7.7.7.5 ................... 4.7.7.8.8.7.8.8.7.4 ................... 4.7.7.7.7.7.7.8.7.4 ................... 5.8.7.8.7.7.7....
output:
NO
result:
ok Correct.
Test #14:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
10 10 2.4.5.4.4.5.5.5.5.3 ................... 4.8.7.7.8.8.8.7.8.4 ................... 4.8.7.8.7.8.8.7.8.4 ................... 5.7.7.8.7.7.7.8.7.5 ................... 5.7.8.8.8.8.8.8.7.5 ................... 4.7.8.7.7.7.8.8.8.5 ................... 4.7.7.7.8.7.7.8.8.5 ................... 4.7.8.7.8.8.7....
output:
YES 2.4#5#4.4#5#5#5#5#3 ################### 4#8#7.7#8#8#8#7#8#4 .#############.###. 4#8#7#8#7#8#8#7#8#4 ####.###.########## 5#7#7#8#7#7.7#8#7#5 ##.#############.## 5#7#8#8#8#8#8#8#7#5 ################### 4#7#8#7.7#7#8#8#8#5 .#.#######.######## 4#7#7.7#8#7#7#8#8#5 ############.###### 4#7#8#7#8#8#7#8#...
result:
ok Correct.
Test #15:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
10 10 2.4.4.4.5.5.4.4.5.3 ................... 5.7.8.8.7.7.7.7.7.5 ................... 5.7.7.7.8.7.7.8.7.5 ................... 4.8.7.7.8.8.8.7.8.4 ................... 4.8.8.8.7.8.8.7.8.4 ................... 4.8.8.8.7.8.8.8.8.5 ................... 4.8.7.8.7.7.7.8.8.4 ................... 5.8.7.8.7.8.8....
output:
YES 2.4#4.4#5#5#4.4#5#3 ################### 5#7#8#8#7.7#7.7#7#5 ##.#############.## 5#7#7#7#8#7.7#8#7#5 ####.#.############ 4#8#7#7#8#8#8#7#8#4 .#############.###. 4#8#8#8#7#8#8#7#8#4 ########.########## 4#8#8#8#7#8#8#8#8#5 .################## 4#8#7#8#7#7.7#8#8#4 ####.###.#########. 5#8#7#8#7#8#8#8#...
result:
ok Correct.
Test #16:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
10 10 3.5.4.4.5.5.4.4.5.3 ................... 5.7.8.8.7.8.8.8.8.5 ................... 5.7.8.8.7.7.7.8.8.5 ................... 5.8.7.7.8.8.7.8.8.5 ................... 5.8.8.8.8.8.7.8.8.4 ................... 5.7.7.8.8.7.8.7.8.4 ................... 5.7.8.8.8.7.7.7.8.5 ................... 5.7.8.8.8.8.7....
output:
YES 3#5#4.4#5#5#4.4#5#3 ################### 5#7#8#8#7#8#8#8#8#5 ##.#####.########## 5#7#8#8#7#7.7#8#8#5 ################### 5#8#7.7#8#8#7#8#8#5 ############.###### 5#8#8#8#8#8#7#8#8#4 ##################. 5#7.7#8#8#7#8#7#8#4 ##########.###.#### 5#7#8#8#8#7#7#7#8#5 ##.#########.###### 5#7#8#8#8#8#7#8#...
result:
ok Correct.
Test #17:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
10 10 3.5.5.4.4.5.5.4.4.3 ................... 5.7.7.7.7.8.8.7.7.5 ................... 5.8.7.7.8.8.8.8.8.5 ................... 5.7.8.8.8.7.7.8.8.4 ................... 5.7.7.7.8.7.7.8.7.4 ................... 5.8.8.8.7.7.8.8.7.5 ................... 4.7.7.8.8.8.7.7.8.5 ................... 4.8.8.8.7.7.8....
output:
YES 3#5#5#4.4#5#5#4.4#3 ################### 5#7.7#7.7#8#8#7.7#5 ################### 5#8#7.7#8#8#8#8#8#5 ################### 5#7#8#8#8#7.7#8#8#4 ##.###############. 5#7#7.7#8#7.7#8#7#4 ################.## 5#8#8#8#7.7#8#8#7#5 ################### 4#7.7#8#8#8#7.7#8#5 .################## 4#8#8#8#7.7#8#7#...
result:
ok Correct.
Test #18:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
10 10 2.4.4.5.4.4.4.4.4.2 ................... 4.8.7.8.8.7.8.8.8.4 ................... 4.8.7.8.7.7.7.7.7.4 ................... 4.7.7.8.7.8.7.7.7.4 ................... 5.8.7.8.7.7.8.8.8.4 ................... 4.8.7.8.7.7.7.7.7.5 ................... 4.8.7.7.8.8.7.7.7.5 ................... 4.7.7.8.8.7.8....
output:
YES 2#4.4#5#4.4#4.4#4.2 .################## 4#8#7#8#8#7#8#8#8#4 ####.#####.#######. 4#8#7#8#7#7#7.7#7#4 .#######.#######.## 4#7.7#8#7#8#7.7#7#4 ##################. 5#8#7#8#7.7#8#8#8#4 ####.############## 4#8#7#8#7.7#7#7#7#5 .###########.#.#.## 4#8#7.7#8#8#7#7#7#5 ################### 4#7#7#8#8#7#8#8#...
result:
ok Correct.
Test #19:
score: -100
Time Limit Exceeded
input:
10 10 2.4.4.4.4.4.4.4.4.2 ................... 4.8.8.7.7.7.7.8.8.5 ................... 4.7.8.7.8.8.7.8.7.4 ................... 4.7.8.7.7.8.7.7.7.4 ................... 4.8.7.8.7.7.7.7.8.4 ................... 4.8.7.8.7.7.7.7.7.4 ................... 4.7.8.7.8.7.7.7.7.4 ................... 4.7.7.7.7.7.7....