QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#390587#6746. Merge the Rectanglesucup-team1001TL 1ms3816kbC++236.1kb2024-04-15 17:28:112024-04-15 17:28:12

Judging History

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

  • [2024-04-15 17:28:12]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3816kb
  • [2024-04-15 17:28:11]
  • 提交

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();
    }
}

详细

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...

output:


result: