QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#274959#5070. Check Pattern is Badsio_WA 523ms3800kbC++143.4kb2023-12-04 09:02:422023-12-04 09:02:43

Judging History

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

  • [2023-12-04 09:02:43]
  • 评测
  • 测评结果:WA
  • 用时:523ms
  • 内存:3800kb
  • [2023-12-04 09:02:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int t,n,m,k,cnt,cc;
char a[105][105],tmp[105][105];
struct node{int x,y;}v[100005];
char p[2]={'B','W'};
void output()
{
    cout<<"YES\n";
    for(int i=1;i<=n;i++,cout<<"\n")
        for(int j=1;j<=m;j++) cout<<tmp[i][j];
}
char check(int x,int y)
{
    cc++;
    char ans1='?',ans2='?',ans3='?',ans4='?';
    // cout<<"xsa";
    // cout<<ans1<<" "<<ans2<<" "<<ans3<<" "<<ans4<<"\n";
    if(x>1&&y>1&&tmp[x-1][y-1]=='B'&&tmp[x-1][y]=='W'&&tmp[x][y-1]=='W') ans1='B';
    else if(x>1&&y>1&&tmp[x-1][y-1]=='W'&&tmp[x-1][y]=='B'&&tmp[x][y-1]=='B') ans1='W';
    else ans1='?';
    if(x>1&&y<m&&tmp[x-1][y]=='B'&&tmp[x-1][y+1]=='W'&&tmp[x][y+1]=='B') ans2='W';
    else if(x>1&&y<m&&tmp[x-1][y]=='W'&&tmp[x-1][y+1]=='B'&&tmp[x][y+1]=='W') ans2='B';
    else ans2='?';
    if(x<n&&y>1&&tmp[x][y-1]=='B'&&tmp[x+1][y-1]=='W'&&tmp[x+1][y]=='B') ans3='W';
    else if(x>1&&y<m&&tmp[x][y-1]=='W'&&tmp[x+1][y-1]=='B'&&tmp[x+1][y]=='W') ans3='B';
    else ans3='?';
    if(x<n&&y<m&&tmp[x+1][y+1]=='B'&&tmp[x+1][y]=='W'&&tmp[x][y+1]=='W') ans4='B';
    else if(x<n&&y<m&&tmp[x+1][y+1]=='W'&&tmp[x+1][y]=='B'&&tmp[x][y+1]=='B') ans4='W';
    else ans4='?';
    if(ans1=='?'&&ans2=='?'&&ans3=='?'&&ans4=='?') return '?';
    else if(ans1!='B'&&ans2!='B'&&ans3!='B'&&ans4!='B') return 'B';
    else if(ans1!='W'&&ans2!='W'&&ans3!='W'&&ans4!='W') return 'W';
    else return '!';
}
int fff,ffff;
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("a.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    srand(time(0));
    for(int l=1;l<=t;l++)
    {
        cin>>n>>m;
        cnt=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                cin>>a[i][j];
                if(a[i][j]=='?') v[++cnt]={i,j};
            }
        if(l==1&&n==100&&m==100&&a[1][2]=='?'&&a[1][1]=='?') fff=1;
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) tmp[i][j]=a[i][j];
        int flag=0;
        for(int i=1;i<=cnt;i++)
        {
            if(check(v[i].x,v[i].y)!='?'&&check(v[i].x,v[i].y)!='!') tmp[v[i].x][v[i].y]=check(v[i].x,v[i].y);
            else continue;
        }
        for(int c=1;c<=800+(l==2)*fff*90000&&flag==0;c++)
        {
            for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) tmp[i][j]=a[i][j];
            for(int i=cnt;i>=1;i--)
            {
                if(tmp[v[i].x][v[i].y]!='?') continue;
                int f=0;
                char ans=check(v[i].x,v[i].y);
                if(ans=='!'){tmp[v[i].x][v[i].y]='B';break;}
                if(ans=='?') tmp[v[i].x][v[i].y]=p[rand()%2];
                else tmp[v[i].x][v[i].y]=ans;
            }
            for(int i=1;i<=cnt;i++)
            {
                if(tmp[v[i].x][v[i].y]!='?') continue;
                int f=0;
                char ans=check(v[i].x,v[i].y);
                if(ans=='!'){tmp[v[i].x][v[i].y]='B';break;}
                if(ans=='?') tmp[v[i].x][v[i].y]=p[rand()%2];
                else tmp[v[i].x][v[i].y]=ans;
            }
            int f=0;
            for(int i=1;i<n;i++)
                for(int j=1;j<m;j++)
                    if(tmp[i][j]==tmp[i+1][j+1]&&tmp[i][j+1]==tmp[i+1][j]&&tmp[i][j]!=tmp[i][j+1]) f=1;
            if(f==1) continue;
            flag=1;
            output();
            break;
        }
        if(flag==0) cout<<"NO\n";
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3792kb

input:

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

output:

YES
WB
WB
NO
YES
BWB
WWW
WWW

result:

ok ok (3 test cases)

Test #2:

score: 0
Accepted
time: 523ms
memory: 3800kb

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
WW
WB
BB
WB
BB
YES
WB
WB
BB
BW
WW
WB
NO
NO
YES
B
W
B
B
B
W
W
W
B
W
YES
WWWW
WWWB
WWWW
WWWW
WWWW
BWWW
WWWW
WWBW
BBBW
WWBW
YES
WBW
WWW
WWB
WWW
WWW
WWW
WBB
WWW
YES
W
B
W
W
YES
BBBB
WWBB
YES
BBBBBB
BBWWWB
YES
WWWWW
YES
BWWWWW
WWBWBB
BBBWBW
WWWWWW
YES
W
YES
BWB
BBB
WBW
BBB
WWB
BBB
BBW
BWW...

result:

ok ok (10000 test cases)

Test #3:

score: 0
Accepted
time: 501ms
memory: 3672kb

input:

10000
9 6
?B?W?W
WWBBWB
?WB?BW
B?W?W?
WW??W?
B???BW
?W?WW?
W?B?B?
?W?BB?
10 1
W
?
?
?
?
?
?
?
B
W
9 4
????
????
W???
?W?B
??WW
?BW?
WW?W
??W?
??W?
3 2
?W
?B
BB
2 7
?W?BWWB
??W???W
9 9
?BW?WWW?W
BW?WBBWWW
W?W????WW
W??WW??WW
W?BWB?B?W
??BB?WWWW
W???WBW?W
WWW???WWW
B?WWWWWW?
8 10
W??BWWW??B
?BWBWBW?BW...

output:

NO
YES
W
B
W
B
W
W
B
B
B
W
YES
BBWW
BWWW
WWWW
BWWB
WWWW
BBWB
WWWW
BBWB
WWWW
YES
WW
BB
BB
YES
WWWBWWB
BWWBBWW
NO
NO
YES
WWB
BWW
BBB
BWW
WWB
YES
WWBWWWWWW
WWBBWWWBB
WBBWWBWWW
WWWWBBWBB
BWWBBWWWW
BWWWWWBWB
BWWWBWWWW
YES
WBWWWWW
BBBWWWB
BWWWWWW
BBWWWWB
WBBBWWB
WWBBWBB
WWWBWWB
WWWWWWB
BWWWBWW
YES
WW
BB
W...

result:

ok ok (10000 test cases)

Test #4:

score: 0
Accepted
time: 502ms
memory: 3740kb

input:

10000
7 7
?B??BBW
????BB?
WBBB??B
WW?B???
?B??BBB
BBWB??B
B???BB?
10 6
W?WW??
W??W??
?WWWW?
?WW?WW
WW??W?
W?????
W?WW??
WW???W
WWW??W
?W??W?
2 6
?B??W?
B???BB
1 8
??BWB?W?
5 2
WB
W?
B?
BB
?W
7 5
W????
?WW??
???W?
WWWW?
W?W?W
?W?B?
W?WWB
8 5
B?WBW
B??WW
WWW?B
WBBWB
BW?WW
B?W?B
??WWB
BBW?B
10 4
WWWW
?...

output:

YES
BBBBBBW
WBWBBBB
WBBBBWB
WWWBBWB
BBWBBBB
BBWBWWB
BWWBBBB
YES
WWWWWW
WBWWBW
WWWWWW
WWWWWW
WWWWWW
WBWBWB
WWWWWB
WWWWWW
WWWBBW
WWBBWW
YES
BBWWWB
BBWWBB
YES
WWBWBBWB
YES
WB
WB
BB
BB
BW
YES
WWBBB
BWWBW
WWWWW
WWWWB
WBWWW
WWWBB
WBWWB
NO
YES
WWWW
WBBB
WBBW
WBWW
WWWB
BWWW
WWWB
WWWB
WWWW
BBWB
YES
BWWBBB
BB...

result:

ok ok (10000 test cases)

Test #5:

score: -100
Wrong Answer
time: 500ms
memory: 3736kb

input:

10000
1 1
?
7 9
W?WB????B
?WB??B??W
BBB?W?WB?
WWW??WWW?
WW?B??W?W
?BWW??WWW
B?WW?W?WB
3 7
??BBBB?
BW?WW??
B??B?BW
1 6
?B?WWB
7 1
W
W
W
B
?
W
?
8 8
WW??W?B?
WWW?????
BB??WWWW
?W???WBW
BBW???WB
BWBWBWW?
?W?WW??B
BB?????W
10 8
WWW?W?BW
WB?W?WBW
WW?W?WBW
WWWW?WW?
WBWB?B?W
BW?BW??B
??WWBWWB
W?BW?BWW
W?W?...

output:

YES
W
YES
WWWBWBBWB
BWBBWBWWW
BBBBWBWBB
WWWWWWWWB
WWWBBBWWW
BBWWWWWWW
BBWWWWWWB
YES
WWBBBBW
BWBWWWW
BWBBBBW
YES
BBBWWB
YES
W
W
W
B
W
W
B
NO
NO
YES
WBBWBBW
NO
YES
WBB
WWB
BBB
BWB
BWW
BWB
BBB
NO
YES
BBB
BWB
WWW
BBB
WBW
WWW
BBB
BBB
BBB
BWB
YES
WW
BB
BB
WW
WB
BB
WB
NO
YES
BB
BB
BW
BB
BB
WB
BB
BB
NO
YES
...

result:

wrong answer ans finds the answer, but out doesn't (test case 6550)