QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#419288#6746. Merge the RectanglesAndevikingWA 48ms25820kbC++202.2kb2024-05-23 19:57:212024-05-23 19:57:21

Judging History

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

  • [2024-05-23 19:57:21]
  • 评测
  • 测评结果:WA
  • 用时:48ms
  • 内存:25820kb
  • [2024-05-23 19:57:21]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define range(x) (x).begin(),(x).end()
const int dir[][2]={1,0,-1,0,0,1,0,-1};

const int N=1505;
char r[N][N],c[N][N];
int tagr[N][N],tagc[N][N];
void solve()
{
    int n,m;
    cin>>n>>m;

    for(int i=1;i<n;++i){
        for(int j=1;j<=m;++j)
            cin>>r[i][j];
    }

    for(int j=1;j<=m;++j)
        r[n][j]='1';

    for(int i=1;i<=n;++i)
        for(int j=1;j<m;++j)
            cin>>c[i][j];

    for(int i=1;i<=n;++i)
        c[i][m]='1';

    for(int i=1;i<=n;++i){
        if(r[i][m]=='0')
            tagr[i][m]=m;
        else
            tagr[i][m]=m+1;
        for(int j=m-1;j;--j){
            if(r[i][j]=='0')
                tagr[i][j]=j;
            else
                tagr[i][j]=tagr[i][j+1];
        }
    }
    for(int j=1;j<=m;++j){
        if(c[n][j]=='0')
            tagc[n][j]=n;
        else
            tagc[n][j]=n+1;
        for(int i=n-1;i;--i){
            if(c[i][j]=='0')
                tagc[i][j]=i;
            else
                tagc[i][j]=tagc[i+1][j];
        }
    }


    for(int i=1;i<n;++i)
        for(int j=1;j<m;++j){
            bool flag=false;
            int tarr=tagr[i][j+1]-1;
            if(tarr==j)
                continue;

            int tarc=tagc[i+1][j]-1;
            int tarrc=tagc[i+1][tarr]-1;
            int hight=min(tarc,tarrc);

            if(hight==i)
                continue;

            
            if(c[i][j]=='1'&&c[i][tarr]=='1')
                flag=true;
            if(c[hight+1][j]=='1'&&c[hight+1][tarr]=='1')
                flag=true;
            if(r[i][j]=='1'&&r[hight][j]=='1')
                flag=true;
            if(r[i][tarr+1]=='1'&&r[hight][tarr+1]=='1')
                flag=true;
            if(!flag){
            // cout<<i<<' '<<j<<' '<<tarr<<' '<<hight<<'\n';

                cout<<"NO\n";
                return;
            }
        }

    cout<<"YES\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 4
0000
0111
101
101
110

output:

YES

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 1ms
memory: 9788kb

input:

3 3
110
011
01
11
10

output:

NO

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 39ms
memory: 25676kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #4:

score: 0
Accepted
time: 48ms
memory: 25692kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #5:

score: 0
Accepted
time: 40ms
memory: 25816kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #6:

score: 0
Accepted
time: 41ms
memory: 25668kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #7:

score: -100
Wrong Answer
time: 34ms
memory: 25820kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

wrong answer expected NO, found YES