QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#373376 | #6746. Merge the Rectangles | team129 | TL | 1481ms | 197472kb | C++14 | 2.4kb | 2024-04-01 15:35:11 | 2024-04-01 15:35:12 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<map>
#include<string>
#include<iomanip>
#include<climits>
#include <sstream>
#include<functional>
#include <unordered_map>
#include<array>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
ll t, n, k, a, b,m;
char c;
const ll N = 1.5e3+10;
const ll MOD = 998244353;
const int B = 0, T = 3, L = 2, R = 1;
int arr[N][N][4],pres[N][N][2];
set<pair<pii, pii>> recs;
bool TL(pii dot) {
return arr[dot.first][dot.second][T] == 1 && arr[dot.first][dot.second][L] == 1;
}
int al1 = 1;
void ini() {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m; j++) {
cin >> c;
a = c - 48;
if (a != 1)
al1 = 0;
if (a) {
arr[i][j][B] = arr[i + 1][j][T] = 1;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m - 1; j++) {
cin >> c;
a = c - 48;
if (a != 1)
al1 = 0;
if (a) {
arr[i][j][R] = arr[i][j + 1][L] = 1;
}
}
}
for (int i = 0; i < m; i++) {
arr[0][i][T] = arr[n - 1][i][B] = 1;
}
for (int i = 0; i < n; i++) {
arr[i][0][L] = arr[i][m - 1][R] = 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (TL({ i,j })) {
int r = j, b = i;
while (!arr[i][r][R])
r++;
while (!arr[b][j][B])
b++;
recs.insert({ {i,j},{b,r} });
}
}
}
for (int j = m - 2; j >= 0; j--) {
for (int i = n - 1; i >= 0; i--) {
if(arr[i][j][R] == 1)
pres[i][j][R] = pres[i + 1][j][R] + arr[i][j][R];
}
}
for (int i = n - 2; i >= 0; i--)
for (int j = m - 1; j >= 0; j--) {
if (arr[i][j][B] == 1)
pres[i][j][B] = pres[i][j + 1][B] + arr[i][j][B];
}
}
int f = 1;
bool solve(pii tl, pii br) {
if (f == 0)
return 0;
if (recs.count({ tl,br }))
return 1;
int t = tl.first, b = br.first, l = tl.second, r = br.second;
for (int i = l; i < r; i++) {
if (pres[t][i][R] >= (int)abs(b - t) + 1) {
return solve(tl, { b,i }) && solve({ t,i + 1 }, br);
}
}
for (int i = t; i < b; i++) {
if (pres[i][l][B] >= (int)abs(r - l) + 1) {
return solve(tl, { i,r }) && solve({ i + 1,l }, br);
}
}
f = 0;
return 0;
}
int main()
{
cin >> n >> m;
ini();
if (al1) {
cout << "YES";
}
else
cout << ((solve({ 0,0 }, { n - 1,m - 1 }) == 1) ? "YES" : "NO");
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5668kb
input:
3 4 0000 0111 101 101 110
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 1ms
memory: 5664kb
input:
3 3 110 011 01 11 10
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 140ms
memory: 38600kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #4:
score: 0
Accepted
time: 701ms
memory: 197380kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #5:
score: 0
Accepted
time: 145ms
memory: 57008kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #6:
score: 0
Accepted
time: 149ms
memory: 56964kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #7:
score: 0
Accepted
time: 1481ms
memory: 197472kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #8:
score: 0
Accepted
time: 698ms
memory: 197300kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #9:
score: 0
Accepted
time: 681ms
memory: 197136kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #10:
score: -100
Time Limit Exceeded
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...