QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#390587 | #6746. Merge the Rectangles | ucup-team1001 | TL | 1ms | 3816kb | C++23 | 6.1kb | 2024-04-15 17:28:11 | 2024-04-15 17:28:12 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#ifndef ONLINE_JUDGE
#include "test.h"
#else
#define debug(...) 42
#define debug_assert(...) 42
#endif
#define IOS ios::sync_with_stdio(0),cin.tie(0)
using ll = long long;
using ull = unsigned long long;
#define endl '\n'
#define int ll
using VI = vector<int>;
using VII = vector<VI>;
using PII = pair<int, int>;
const int inf = 1e18;
const int mod = 1e9 + 7;
template<typename T, typename Compare =less<>>
using pqinit = priority_queue<T, vector<T>, Compare>;
void init() {
}
void solve() {
int up = 1;
int down = 2;
int left = 4;
int right = 8;
int patten = ((1 << 4) - 1);
int upnode = patten ^ down;
int downnode = patten ^ up;
int leftnode = patten ^ right;
int rightnode = patten ^ left;
int n, m;
cin >> n >> m;
vector<vector<int>> arr(n + 3, vector<int>(m + 3));
for (int i = 1; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < m; j++) {
if (s[j] == '1') {
arr[i][j] |= right;
arr[i][j + 1] |= left;
}
}
}
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < m - 1; j++) {
if (s[j] == '1') {
// debug(i, j);
arr[i][j + 1] |= down;
arr[i + 1][j + 1] |= up;
}
}
}
vector<vector<int>> mp1(n + 3, vector<int>(m + 3)), mp2(n + 3, vector<int>(m + 3)),
du1(n + 3, vector<int>(m + 3)), du2(n + 3, vector<int>(m + 3));
for (int i = 1; i < n; i++) {
int lastRight = 0;
for (int j = 1; j < m; j++) {
if (arr[i][j] == rightnode) {
lastRight = j;
} else if (arr[i][j] == upnode && lastRight) {
// 链接一个边
mp2[i][j] = lastRight;
} else if (arr[i][j] == downnode && lastRight) {
mp1[i][j] = lastRight;
}else if(arr[i][j] == patten){
lastRight = 0;
}
}
int lastLeft = 0;
for (int j = m; j >= 1; j--) {
if (arr[i][j] == leftnode) {
lastLeft = j;
} else if (arr[i][j] == upnode && lastLeft) {
mp1[i][j] = lastLeft;
} else if (arr[i][j] == downnode && lastLeft) {
mp2[i][j] = lastLeft;
}else if(arr[i][j] == patten) {
lastLeft = 0;
}
}
}
for (int i = 1; i <= m; i++) {
int lastDown = 0;
for (int j = 1; j < n; j++) {
if (arr[j][i] == downnode) {
lastDown = j;
} else if (arr[j][i] == leftnode && lastDown) {
mp1[j][i] = lastDown;
} else if (arr[j][i] == rightnode && lastDown) {
mp2[j][i] = lastDown;
}else if(arr[j][i] == patten){
lastDown = 0;
}
}
int lastUp = 0;
for (int j = n - 1; j >= 1; j--) {
if (arr[j][i] == upnode) {
lastUp = j;
} else if (arr[j][i] == leftnode && lastUp) {
mp2[j][i] = lastUp;
} else if (arr[j][i] == rightnode && lastUp) {
mp1[j][i] = lastUp;
}else if(arr[j][i] == patten) {
lastUp = 0;
}
}
}
bool flag = false;
auto dfs = [&](int k, int f, int x, int y, int gx, int gy,
vector<vector<int>> &mp, auto self) -> bool {
// debug(x, y);
if (k == 0 && x == gx && y == gy) {
return true;
}
if (k == 0) {
return false;
}
if (f % 2 == 0) {
if (!mp[x][y]) {
return false;
}
return self(k - 1, f - 1, mp[x][y], y, gx, gy, mp, self);
} else {
if (!mp[x][y]) {
return false;
}
// debug(x, y, mp[x][y]);
return self(k - 1, f + 1, x, mp[x][y], gx, gy, mp, self);
}
};
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (arr[i][j] == leftnode || arr[i][j] == rightnode) {
if (mp1[i][j])
flag |= dfs(4, 0, i, j, i, j, mp1, dfs);
// cerr << endl;
if (mp2[i][j])
flag |= dfs(4, 0, i, j, i, j, mp2, dfs);
// cerr << endl;
} else if (arr[i][j] == upnode || arr[i][j] == downnode) {
if (mp1[i][j])
flag |= dfs(4, 1, i, j, i, j, mp1, dfs);
// cerr << endl;
if (mp2[i][j])
flag |= dfs(4, 1, i, j, i, j, mp2, dfs);
// cerr << endl;
}
}
}
// debug(upnode, downnode, leftnode, rightnode);
// debug(bitset<4>(upnode), bitset<4>(downnode), bitset<4>(leftnode), bitset<4>(rightnode));
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
cerr << mp1[i][j] << " ";
}
cerr << endl;
}
cerr << endl;
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
cerr << mp2[i][j] << " ";
}
cerr << endl;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// cout << bitset<4>(arr[i][j]) << " ";
if (arr[i][j] == upnode) {
cerr << "^";
} else if (arr[i][j] == downnode) {
cerr << "v";
} else if (arr[i][j] == leftnode) {
cerr << "<";
} else if (arr[i][j] == rightnode) {
cerr << ">";
} else {
cerr << "#";
}
}
cerr << endl;
}
if (!flag) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
signed main() {
IOS;
init();
// debug(1);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3684kb
input:
3 4 0000 0111 101 101 110
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
3 3 110 011 01 11 10
output:
No
result:
ok answer is NO
Test #3:
score: -100
Time Limit Exceeded
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...