QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#370869#6398. Puzzle: Taparicofx#WA 1ms3852kbC++173.4kb2024-03-29 18:11:372024-03-29 18:11:38

Judging History

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

  • [2024-03-29 18:11:38]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3852kb
  • [2024-03-29 18:11:37]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define enl putchar('\n')
const int MAXN = 55;
int n,m;
char c;
int a[MAXN][MAXN],b[MAXN][MAXN];
int id[MAXN][MAXN],idtot=0;
struct EG{
    int to,nxt;
}e[MAXN*MAXN*2];
int head[MAXN*MAXN],etot;
inline void add(int u,int v){
    int x=(u-1)/m+1,y=(u-1)%m+1;
    // printf("%d %d\n",x,y);
    if((x+y)&1)swap(u,v);
    // printf("%d %d\n",u,v);
    e[etot]={v,head[u]};
    head[u]=etot++;
}

int vis[MAXN*MAXN],mat[MAXN*MAXN];
vector<int>path;
bool dfs(int u){
    for(int i=head[u];~i;i=e[i].nxt){
        int v=e[i].to;
        if(!vis[v]){
            path.push_back(v);
            vis[v]=1;
            if(mat[v]==0||dfs(mat[v])){
                mat[v]=u;
                return true;
            }
        }
    }
    return false;
}

void clear(){
    for(auto &pos:path)vis[pos]=0;
    path.clear();
}

char op[MAXN<<1][MAXN<<1];
int main() {
    ios::sync_with_stdio(0);cin.tie(0);
    memset(head,-1,sizeof(head));
    int ans=0,sum=0;
    cin >> n >> m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            int bas=3;
            if(i!=1&&i!=n)bas+=2;
            if(j!=1&&j!=m)bas+=2;
            if(bas==7)++bas;
            cin>>b[i][j];
            a[i][j]=bas-b[i][j];
            sum+=a[i][j];
            id[i][j]=++idtot;
            if(j!=m)cin>>c;
        }
        if(i!=n)for(int j=1;j<m<<1;++j)cin>>c;
    }
    // printf("sum = %d\n",sum);
    // for(int i=1;i<=n;++i,enl)
    //     for(int j=1;j<=m;++j)
    //         printf("%d ",a[i][j]);
    
    
    if(sum & 1)return !printf("NO\n");
    
    for(int i=1;i<n;++i){
        if(a[i][1] && a[i+1][1])
            add(id[i][1],id[i+1][1]);
        if(a[i][m] && a[i+1][m])
            add(id[i][m],id[i+1][m]);
    }
    for(int i=1;i<m;++i){
        if(a[1][i] && a[1][i+1])
            add(id[1][i],id[1][i+1]);
        // printf("a[%d][%d]=%d check = %d \n",n,i,a[n][i],a[n][i] && a[n][i+1]);
        if(a[n][i] && a[n][i+1])
            add(id[n][i],id[n][i+1]);
    }
    for(int i=1;i<=n;++i){
        ans+=dfs(id[i][1]);clear();
        ans+=dfs(id[i][m]);clear();
    }
    for(int i=1;i<=m;i+=2){
        ans+=dfs(id[1][i]);clear();
        ans+=dfs(id[n][i]);clear();
    }
    // printf("ans = %d\n",ans);
    for(int i=2;i<n;++i)
        for(int j=2;j<m;++j){
            if(i+1!=n && a[i][j] && a[i+1][j])
                add(id[i][j],id[i+1][j]);
            if(j+1!=m && a[i][j] && a[i][j+1])
                add(id[i][j],id[i][j+1]);
        }
    for(int i=2;i<n;++i)
        for(int j=2;j<m;++j){
            if((i+j)&1)continue;
            ans+=dfs(id[i][j]);
            clear();
        }
    if(ans*2!=sum)return !printf("NO\n");
    printf("YES\n");
    for(int i=1;i<n<<1;++i)
        for(int j=1;j<m<<1;++j)
            op[i][j]='#';
    for(int i=1;i<=idtot;++i)
        if(mat[i]){
            // printf("conn %d %d\n",i,mat[i]);
            int x1=(i-1)/m+1,y1=(i-1)%m+1;
            int x2=(mat[i]-1)/m+1,y2=(mat[i]-1)%m+1;
            x1=x1*2-1;
            x2=x2*2-1;
            y1=y1*2-1;
            y2=y2*2-1;
            op[(x1+x2)/2][(y1+y2)/2]='.';
        }
    for(int i=1;i<n<<1;++i,enl)
        for(int j=1;j<m<<1;++j)
            if( (i&1) && (j&1) ){
                printf("%d",b[(i+1)/2][(j+1)/2]);
            }else{
                printf("%c",op[i][j]);
            }
        
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3852kb

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: 3676kb

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: 3808kb

input:

2 2
2.2
...
2.2

output:

YES
2.2
###
2.2

result:

ok Correct.

Test #4:

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

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: 1ms
memory: 3680kb

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: 3760kb

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: 3824kb

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: 3812kb

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:

wrong answer Clue not satisfied at (5,1)