QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#791070 | #9621. 连方 | xbzxzn# | AC ✓ | 23ms | 6296kb | C++20 | 4.2kb | 2024-11-28 16:41:20 | 2024-11-28 16:41:20 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define Pa pair<int,int>
using namespace std;
const int N=2e6+10,mod=1e9+7;
void solve(){
int n;cin>>n;
string a,b;cin>>a>>b;
a=' '+a;
b=' '+b;
vector<Pa>line;
vector<Pa>line2;
for(int i=1;i<=n;i++){
if(a[i]=='#'){
int j=i;
while(j<n&&a[j+1]=='#')j++;
line.push_back({i,j});
i=j;
}
}
for(int i=1;i<=n;i++){
if(b[i]=='#'){
int j=i;
while(j<n&&b[j+1]=='#')j++;
line2.push_back({i,j});
i=j;
}
}
int sz=line.size();
vector<int>flag(n+1);
int id=-1;
for(int i=0;i<sz;i++){
if(i==sz-1){
if(line[i].second!=n){
flag[line[i].second+1]=1;
// id=line[i].second+1;
}
if(i==0){
if(line[i].first!=1){
flag[line[i].first-1]=1;
// id=line[i].first-1;
}
}
continue;
}
if(i==0){
if(line[i].first!=1){
flag[line[i].first-1]=1;
// id=line[i].first-1;
}
}
for(int k=line[i].second+1;k<line[i+1].first;k++){
// cout<<k<<'\n';
flag[k]=1;
}
}
int sz2=line2.size();
vector<int>flag2(n+1);
int id2=-1;
for(int i=0;i<sz2;i++){
if(i==sz2-1){
if(line2[i].second!=n){
flag2[line2[i].second+1]=1;
}
if(i==0){
if(line2[i].first!=1){
flag2[line2[i].first-1]=1;
}
}
continue;
}
if(i==0){
if(line2[i].first!=1){
flag2[line2[i].first-1]=1;
}
}
for(int k=line2[i].second+1;k<line2[i+1].first;k++)flag2[k]=1;
}
// for(auto [s,e]:line){
// cout<<s<<' '<<e<<'\n';
// }
// for(auto [s,e]:line2){
// cout<<s<<' '<<e<<'\n';
// }
// for(int i=1;i<=n;i++){
// cout<<flag[i]<<' ';
// }
// cout<<'\n';
// for(int i=1;i<=n;i++){
// cout<<flag2[i]<<' ';
// }
// cout<<'\n';
for(int i=1;i<n;i++){
if(flag[i]==0&&flag[i+1]==1){
if(id==-1)id=i;
else id=min(id,i);
}
}
for(int i=2;i<=n;i++){
if(flag[i-1]==1&&flag[i]==0){
if(id==-1)id=i;
else id=min(id,i);
}
}
for(int i=1;i<n;i++){
if(flag2[i]==0&&flag2[i+1]==1){
id2=max(id2,i);
}
}
for(int i=2;i<=n;i++){
if(flag2[i-1]==1&&flag2[i]==0){
id2=max(id2,i);
}
}
if(id==-1&&id2==-1){
cout<<"Yes\n";
for(int i=1;i<=7;i++){
cout<<a<<'\n';
}
return;
}
if(id==-1||id2==-1){
cout<<"No\n";
return;
}
cout<<"Yes\n";
cout<<a.substr(1)<<'\n';
for(int i=1;i<=n;i++) {
if(flag[i]==1)cout<<'#';
else cout<<".";
}
cout<<'\n';
for(int i=1;i<=n;i++){
if(i==id)cout<<'#';
else cout<<'.';
}
cout<<'\n';
if(id==id2){
for(int i=1;i<=n;i++){
if(i>=min(id,id2)&&i<=max(id,id2))cout<<'#';
else cout<<'.';
}
}
else if(abs(id-id2)==1){
for(int i=1;i<=n;i++){
if(i>min(id,id2)&&i<=max(id,id2))cout<<'#';
else cout<<'.';
}
}
else{
for(int i=1;i<=n;i++){
if(i>min(id,id2)&&i<max(id,id2))cout<<'#';
else cout<<'.';
}
}
cout<<'\n';
for(int i=1;i<=n;i++){
if(i==id2)cout<<'#';
else cout<<'.';
}
cout<<'\n';
for(int i=1;i<=n;i++) {
if(flag2[i]==1)cout<<'#';
else cout<<".";
}
cout<<'\n';
cout<<b.substr(1)<<'\n';
// if(id==-1)
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T=1;cin>>T;
while(T--)solve();
}
//4
//4
//#..#
//.##.
//5
//##.#.
//.#.##
//6
//######
//.####.
//27
//.######.######.####.#.#####
//.####...####..#.......#####
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3612kb
input:
5 4 #..# .##. 5 ##.#. .#.## 6 ###### .####. 27 .######.######.####.#.##### .####...####..#.......##### 10 ########## ##########
output:
Yes #..# .##. #... .#.. ..#. #..# .##. Yes ##.#. ..#.# .#... ..#.. ...#. #.#.. .#.## No Yes .######.######.####.#.##### #......#......#....#.#..... .#......................... ..####################..... ......................#.... #....###....##.#######..... .####...####..#.......##### Yes #######...
result:
ok Correct.
Test #2:
score: 0
Accepted
time: 23ms
memory: 3696kb
input:
10000 6 .#..## ..#... 5 #..#. ##... 6 .###.# ...### 17 .####..#######..# ###########.##### 6 ..##.# #.##.# 25 #.##.##############.####. ####################.##.# 9 ##.#..##. ##..##### 6 .###.# ##.### 6 ###..# #.#### 25 #####################.#.# ######.################## 6 .#.### .##..# 6 ..#### #......
output:
Yes .#..## #.##.. .#.... ..##.. ....#. .#.#.. ..#... Yes #..#. .##.# #.... .##.. ...#. ..#.. ##... Yes .###.# #...#. .#.... ..#... ...#.. ..#... ...### Yes .####..#######..# #....##.......##. .#............... ..##########..... ............#.... ...........#..... ###########.##### Yes ..##.# .#..#. ...
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 15ms
memory: 3988kb
input:
10000 41 #######.#######.######################### ################.###.#######.############ 6 ..#..# #..##. 6 #.#... #...#. 6 .#.##. ....## 6 ...#.# ##..#. 33 #####.########################### ###########.##################### 6 .##.## .##.#. 5 ..##. ####. 17 #.###.##########. ####.##.#####.##. 5 ....
output:
Yes #######.#######.######################### .......#.......#......................... ......#.................................. .......######################............ .............................#........... ................#...#.......#............ ################.###.#######.############ Ye...
result:
ok Correct.
Test #4:
score: 0
Accepted
time: 18ms
memory: 3688kb
input:
10000 6 ..#### .#.... 6 ...#.# #..##. 9 ..####.## ######..# 33 #######################.#####..## ######.######.###########.####### 6 ####.# #..##. 6 ...### ##.### 25 ######.#.#.############## .#########.##########.### 17 ############.#### ###############.# 6 #..#.# #####. 6 .#.### ..#... 49 ########...
output:
Yes ..#### .#.... #..... .##... ...#.. #.#... .#.... Yes ...#.# ..#.#. .#.... ..##.. ....#. .##..# #..##. Yes ..####.## .#....#.. #........ .#######. ........# ......##. ######..# Yes #######################.#####..## .......................#.....##.. ......................#.......... .................
result:
ok Correct.
Test #5:
score: 0
Accepted
time: 11ms
memory: 3952kb
input:
10000 5 ...#. ##### 6 ###... ##..#. 9 .#.###### #.#..#### 49 ######.########################################## ########.#############.########################## 41 ###########.#######.##################### ##############.########################## 6 ###..# ###.## 49 #################################...
output:
No Yes ###... ...#.. ..#... ...#.. ....#. ..##.# ##..#. Yes .#.###### #.#...... .#....... ..###.... .....#... .#.##.... #.#..#### Yes ######.########################################## ......#.......................................... .....#........................................... ......##########...
result:
ok Correct.
Test #6:
score: 0
Accepted
time: 14ms
memory: 6268kb
input:
2 100000 ###.#...#..####...#####..####.#.######.##.##..#..#..####...###.#..##.#.##.####.#.#.###...#.##...####.#.#.####...####.#..##.##.#.#.....####..####..#...#..#.##..#.##.#.....#..#.#.###.#....####...####..##.#.#####..####.##.#.###.#.#....#.##.##...#.######.#..##..##...#.....#....#.####...#...##.#...
output:
Yes ###.#...#..####...#####..####.#.######.##.##..#..#..####...###.#..##.#.##.####.#.#.###...#.##...####.#.#.####...####.#..##.##.#.#.....####..####..#...#..#.##..#.##.#.....#..#.#.###.#....####...####..##.#.#####..####.##.#.###.#.#....#.##.##...#.######.#..##..##...#.....#....#.####...#...##.##.#.....
result:
ok Correct.
Test #7:
score: 0
Accepted
time: 16ms
memory: 6296kb
input:
2 100000 ##.####.#..#..#.##..#.#..###..##..#####.....#..##.##.#...#.###..##..#...##...####..#...##...##.......#.#..##.##..###.#.###.##.#########..#...###.####.##...#..#.....#####.....#.####.#####..#.#....#..###.#.##..#..#.##.......#.###.##...####.....######..#.##....#.#.###.#.###.#..#.....####....##...
output:
Yes ##.####.#..#..#.##..#.#..###..##..#####.....#..##.##.#...#.###..##..#...##...####..#...##...##.......#.#..##.##..###.#.###.##.#########..#...###.####.##...#..#.....#####.....#.####.#####..#.#....#..###.#.##..#..#.##.......#.###.##...####.....######..#.##....#.#.###.#.###.#..#.....####....##........
result:
ok Correct.