QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#386977#6746. Merge the Rectanglesk1nsomWA 15ms117560kbC++173.2kb2024-04-11 22:12:062024-04-11 22:12:06

Judging History

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

  • [2024-04-11 22:12:06]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:117560kb
  • [2024-04-11 22:12:06]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define N 300005
#define ednl '\n'
#define int long long
int n, m, maxn = 0, a[1510][1510] = {0}, b[1510][1510] = {0}, cnt[1510][1510] = {0};
bool vis[1510][1510] = {0};
struct ra
{
    int space, sx, sy, tx, ty;
} tmp;
vector<ra> v[N], s1[1510][1510], s2[1510][1510];
signed main()
{
    cin >> n >> m;
    for (int i = 1; i < n; i++)
        for (int j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            a[i][j] = c - '0';
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < m; j++)
        {
            char c;
            cin >> c;
            b[i][j] = c - '0';
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (!vis[i][j])
            {
                vis[i][j] = 1;
                int sx = i, sy = j, tx = i, ty = j;
                while (tx <= n && !a[tx][j])
                {
                    tx++;
                    if (tx > n)
                    {
                        tx--;
                        break;
                    }
                }
                while (ty <= m && !b[i][ty])
                {
                    ty++;
                    if (ty > m)
                    {
                        ty--;
                        break;
                    }
                }
                ra tmp = {(ty - sy + 1) * (tx - sx + 1), sx, sy, tx, ty};
                for (int t = i; t <= tx; t++)
                    for (int k = j; k <= ty; k++)
                        vis[t][k] = 1;
                if (!s1[tmp.sx][tmp.tx].empty())
                {
                    ra u = s1[tmp.sx][tmp.tx][0];
                    s1[tmp.sx][tmp.tx].pop_back();
                    ra tmp2;
                    tmp2.sx = min(u.sx, tmp.sx);
                    tmp2.sy = min(tmp.sy, u.sy);
                    tmp2.tx = max(u.tx, tmp.tx);
                    tmp2.ty = max(u.ty, tmp.ty);
                    tmp2.space = (tmp2.ty - tmp2.sy + 1) * (tmp2.tx - tmp2.sx + 1);
                    s1[tmp2.sx][tmp2.tx].push_back(tmp2);
                    s2[tmp2.sy][tmp2.ty].push_back(tmp2);
                    s2[u.sy][u.ty].pop_back();
                }
                else if (!s2[tmp.sy][tmp.ty].empty())
                {
                    ra u = s2[tmp.sy][tmp.ty][0];
                    s2[tmp.sy][tmp.ty].pop_back();
                    ra tmp2;
                    tmp2.sx = min(u.sx, tmp.sx);
                    tmp2.sy = min(tmp.sy, u.sy);
                    tmp2.tx = max(u.tx, tmp.tx);
                    tmp2.ty = max(u.ty, tmp.ty);
                    tmp2.space = (tmp2.ty - tmp2.sy + 1) * (tmp2.tx - tmp2.sx + 1);
                    s1[tmp2.sx][tmp2.tx].push_back(tmp2);
                    s2[tmp2.sy][tmp2.ty].push_back(tmp2);
                    s1[u.sx][u.tx].pop_back();
                }
                else
                {
                    s2[tmp.sy][tmp.ty].push_back(tmp);
                    s1[tmp.sx][tmp.tx].push_back(tmp);
                }
                maxn = max(tmp.space, maxn);
            }
    if (!s1[n][m].empty())
        cout << "YES";
    else
        cout << "NO";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 15ms
memory: 117560kb

input:

3 4
0000
0111
101
101
110

output:

NO

result:

wrong answer expected YES, found NO