QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#106969#5070. Check Pattern is BadKostlinWA 13ms3696kbC++145.8kb2023-05-19 22:13:282023-05-19 22:13:32

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-19 22:13:32]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:3696kb
  • [2023-05-19 22:13:28]
  • 提交

answer

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define fi first
#define sc second
#define mkp make_pair
#define pii pair<int,int>
typedef long long ll;
const int N=105,M=10005,oo=1e9;
inline int read() {
    int x=0,flag=0;char ch=getchar();
    while(ch<'0'||ch>'9') {flag|=(ch=='-');ch=getchar();}
    while('0'<=ch&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return flag?-x:x;
}
inline int mx(int x,int y) {return x>y?x:y;}
inline int mn(int x,int y) {return x<y?x:y;}
inline void swp(int &x,int &y) {x^=y^=x^=y;}
inline int as(int x) {return x>0?x:-x;}

int n,m,a[N][N],tot,fr[N][N],D[N][N],lim;
char s[N];
int hd[M<<1],num,qwq[M];
struct node {
    int nxt,to;
}e[M<<2];
#define v e[i].to
inline void adde(int x,int y) {
    e[++num]=(node){hd[x],y};
    hd[x]=num;
}
pii q[M]; int l,r;
inline void sub(int x,int y) {
    if(x>1&&y>1) {
        ++D[x-1][y-1];
        if(D[x-1][y-1]==3) q[++r]=mkp(x-1,y-1);
    }
    if(x>1&&y<m) {
        ++D[x-1][y];
        if(D[x-1][y]==3) q[++r]=mkp(x-1,y);
    }
    if(y>1&&x<n) {
        ++D[x][y-1];
        if(D[x][y-1]==3) q[++r]=mkp(x,y-1);
    }
    if(x<n&&y<n) {
        ++D[x][y];
        if(D[x][y]==3) q[++r]=mkp(x,y);
    }
}
inline void work1(int x,int y) {
    if(a[x][y+1]&&a[x+1][y]&&a[x+1][y+1]) {
        if(a[x][y+1]==a[x+1][y]&&a[x][y+1]!=a[x+1][y+1]) {
            a[x][y]=3-a[x+1][y+1];
            sub(x,y);
        }
        return ;
    }
    if(a[x][y]&&a[x+1][y]&&a[x+1][y+1]) {
        if(a[x][y]==a[x+1][y+1]&&a[x][y]!=a[x+1][y]) {
            a[x][y+1]=3-a[x+1][y];
            sub(x,y+1);
        }
        return ;
    }
    if(a[x][y]&&a[x][y+1]&&a[x+1][y+1]) {
        if(a[x][y]==a[x+1][y+1]&&a[x][y]!=a[x][y+1]) {
            a[x+1][y]=3-a[x][y+1];
            sub(x+1,y);
        }
        return ;
    }
    if(a[x][y]&&a[x][y+1]&&a[x+1][y]) {
        if(a[x][y+1]==a[x+1][y]&&a[x][y+1]!=a[x][y]) {
            a[x+1][y+1]=3-a[x][y];
            sub(x,y);
        }
        return ;
    }
}
inline void prep() {
    l=1;r=0;
    for(int i=1;i<n;++i)
        for(int j=1;j<m;++j) {
            D[i][j]=(a[i][j]>0)+(a[i][j+1]>0)+(a[i+1][j]>0)+(a[i+1][j+1]>0);
            if(D[i][j]==3) q[++r]=mkp(i,j);
        }
    while(l<=r) {
        pii now=q[l++];
        if(D[now.fi][now.sc]!=3) continue;
        work1(now.fi,now.sc);
    }
}
inline bool chk(int x,int y) {
    return !(a[x][y]==a[x+1][y+1]&&a[x+1][y]==a[x][y+1]&&a[x][y]!=a[x][y+1]);
}
inline void work2(int x,int y) {
    if(a[x][y]&&a[x+1][y]&&a[x][y]!=a[x+1][y]) {
        if(a[x][y]==1) adde(fr[x+1][y+1],fr[x][y+1]),adde(fr[x][y+1]+tot,fr[x+1][y+1]+tot);
        else adde(fr[x+1][y+1]+tot,fr[x][y+1]+tot),adde(fr[x][y+1],fr[x+1][y+1]);
    }
    if(a[x][y]&&a[x+1][y+1]&&a[x][y]==a[x+1][y+1]) {
        if(a[x][y]==1) adde(fr[x+1][y]+tot,fr[x][y+1]),adde(fr[x][y+1]+tot,fr[x+1][y]);
        else adde(fr[x+1][y],fr[x][y+1]+tot),adde(fr[x][y+1],fr[x+1][y]+tot);
    }
    if(a[x][y+1]&&a[x+1][y]&&a[x][y+1]==a[x+1][y]) {
        if(a[x][y+1]==1) adde(fr[x][y]+tot,fr[x+1][y+1]),adde(fr[x+1][y+1]+tot,fr[x][y]);
        else adde(fr[x][y],fr[x+1][y+1]+tot),adde(fr[x+1][y+1],fr[x][y]+tot);
    }
    if(a[x][y+1]&&a[x+1][y+1]&&a[x][y+1]!=a[x+1][y+1]) {
        if(a[x][y+1]==1) adde(fr[x][y]+tot,fr[x+1][y]+tot),adde(fr[x+1][y],fr[x][y]);
        else adde(fr[x][y],fr[x+1][y]),adde(fr[x+1][y]+tot,fr[x][y]);
    }
}
int dfn[M<<1],low[M<<1],st[M<<1],top,col[M<<1],co;
bool inst[M<<1];
void tar(int x) {
    dfn[x]=low[x]=++dfn[0];
    st[++top]=x;inst[x]=1;
    for(int i=hd[x];i;i=e[i].nxt) 
        if(!dfn[v]) {
            tar(v);
            low[x]=mn(low[x],low[v]);
        } else if(inst[v]) low[x]=mn(low[x],dfn[v]);
    if(dfn[x]==low[x]) {
        ++co;
        do {
            col[st[top]]=co;
            inst[st[top]]=0;
        }while(st[top--]!=x);
    }
}
inline void print(int x) {printf("%c",(x==1?'B':'W'));}
inline void Clear() {
    for(int i=1;i<=2*tot;++i) dfn[i]=hd[i]=0;
    dfn[0]=co=num=0;
}
inline void solve() {
    n=read();m=read();
    for(int i=1;i<=n;++i) {
        scanf("%s",s+1);
        for(int j=1;j<=m;++j)
            if(s[j]=='B') a[i][j]=1;
            else if(s[j]=='W') a[i][j]=2;
            else a[i][j]=0;
    }
    prep();
    // for(int i=1;i<=n;++i) {
    //     for(int j=1;j<=m;++j)
    //         if(a[i][j]) print(a[i][j]);
    //         else printf("?");
    //     printf("\n");
    // }
    tot=0;
    for(int i=1;i<=n;++i) {
        if(a[i][1]==0) fr[i][1]=++tot;
        for(int j=2;j<=m;++j)
            if(a[i][j]==0) {
                if(a[i][j-1]==0) fr[i][j]=fr[i][j-1];
                else fr[i][j]=++tot;
            }
    }
    bool flag=1;
    for(int i=1;i<n;++i)
        for(int j=1;j<m;++j) {
            int cnt=(a[i][j]>0)+(a[i+1][j]>0)+(a[i][j+1]>0)+(a[i+1][j+1]>0);
            if(cnt==4) flag&=chk(i,j);
            if(cnt==2) work2(i,j);
        }
    for(int i=1;i<=tot*2;++i) if(!dfn[i]) tar(i);
    for(int i=1;flag&&i<=tot;++i)
        if(col[i]==col[i+tot]) flag=0;
        else qwq[i]=(col[i]<col[i+tot]?1:2);
    ++lim;
    if(lim==276) {
        printf("%d %d\n",n,m);
        for(int i=1;i<=n;++i) {
            for(int j=1;j<=m;++j)
                if(a[i][j]) print(a[i][j]);
                else printf("?");
            printf("\n");
        }
    }
    if(lim<=3) {
        if(!flag) {
            printf("NO\n");
        } else {
            printf("YES\n");
            for(int i=1;i<=n;++i) {
                for(int j=1;j<=m;++j)
                    if(a[i][j]) print(a[i][j]);
                    else print(qwq[fr[i][j]]);
                printf("\n");
            }
        }
    }
    Clear();
}
int main() {
    int TT=read();
    while(TT--) solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3696kb

input:

3
2 2
??
??
3 3
BW?
W?B
?BW
3 3
BW?
W?W
?W?

output:

YES
BB
BB
NO
YES
BWB
WWW
BWB

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 13ms
memory: 3632kb

input:

10000
9 2
BB
BW
WW
WW
?W
?B
B?
W?
BB
6 2
??
?B
B?
BW
WW
??
10 7
WBBBW??
???BWWW
???BWWB
??WWBW?
BBWBBWB
WWB?WW?
BWBW???
WWWWBBW
BBWBB?W
B?W?W?B
4 7
??WBWWB
?BBWWWB
?W?BBB?
BBBWBBB
10 1
B
W
?
B
B
W
W
W
B
?
10 4
??WW
W?W?
WWW?
???W
?W??
?W?W
W?W?
?W?W
???W
???W
8 3
WBW
W??
???
???
W?W
W?W
???
?W?
4 1
...

output:

YES
BB
BW
WW
WW
BW
BB
BB
WB
BB
YES
BB
BB
BB
BW
WW
BB
NO
9 8
?BWW?W?B
B???B??B
?B???W?B
?BB?W?B?
??BWWW??
B?WWB?B?
B?B?WW??
W??B?B??
W????B??

result:

wrong answer Token parameter [name=yesno] equals to "9", doesn't correspond to pattern "YES|NO" (test case 4)