QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#415639#6563. Four Squareskittles1412#RE 0ms3852kbC++174.4kb2024-05-21 07:51:402024-05-21 07:51:40

Judging History

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

  • [2024-05-21 07:51:40]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3852kb
  • [2024-05-21 07:51:40]
  • 提交

answer

#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

bool on(int mask, int bit) {
    return (mask >> bit) & 1;
}

vector<vector<int>> rotate(const vector<vector<int>>& arr) {
    int n = sz(arr);
    vector ans(n, vector(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans[n - j - 1][i] = arr[i][j];
        }
    }
    return ans;
}

bool check(int m, const array<pair<int, int>, 4>& arr) {
    vector cans(m, vector(m, 0));

    for (int i = 0; i < 4; i++) {
        auto& [x, y] = arr[i];
        for (int cx = 0; cx < x; cx++) {
            for (int cy = 0; cy < y; cy++) {
                cans[cx][cy] |= 1 << i;
            }
        }

        cans = rotate(cans);
    }

    for (auto& a : cans) {
        for (auto& b : a) {
            if (__builtin_popcount(b) != 1) {
                return false;
            }
        }
    }
    return true;
}

bool check2(int n, int m, const vector<pair<int, int>>& arr) {
    auto go = [&](int x0, int y0, int x1, int y1) -> bool {
        if (n == x0 && n == x1) {
            assert(y0 + y1 == m);
            return true;
        } else if (m == x0 && m == y1) {
            assert(y0 + y1 == n);
            return true;
        }
        return false;
    };

    for (int mask = 0; mask < (1 << 2); mask++) {
        auto [x0, y0] = arr[0];
        auto [x1, y1] = arr[1];
        if (on(mask, 0)) {
            swap(x0, y0);
        }
        if (on(mask, 1)) {
            swap(x1, y1);
        }
        if (go(x0, y0, x1, y1)) {
            return true;
        }
    }
    return false;
}

bool check3(int n, int m, const vector<pair<int, int>>& arr) {
    for (int i = 0; i < 3; i++) {
        auto go = [&](int cx, int cy) -> bool {
            if (cx != n) {
                return false;
            }

            auto carr = arr;
            carr.erase(begin(carr) + i);
            return check2(n, m - cy, carr);
        };

        auto [cx, cy] = arr[i];
        if (go(cx, cy) || go(cy, cx)) {
            return true;
        }
    }

    return false;
}

void solve() {
    array<pair<int, int>, 4> arr;
    for (auto& [x, y] : arr) {
        cin >> x >> y;
    }

    int area = 0;
    for (auto& [x, y] : arr) {
        area += x * y;
    }
    int x;
    for (x = 0; x * x < area; x++)
        ;
    if (x * x != area) {
        cout << 0 << endl;
        return;
    }

    int perm[4] {};
    iota(begin(perm), end(perm), 0);

    do {
        if (perm[0]) {
            continue;
        }

        for (int mask = 0; mask < (1 << 4); mask++) {
            if (on(mask, 0)) {
                continue;
            }

            auto carr = arr;
            for (int i = 0; i < 4; i++) {
                carr[i] = arr[perm[i]];
                if (on(mask, i)) {
                    swap(carr[i].first, carr[i].second);
                }
            }

            if (check(x, carr)) {
                cout << 1 << endl;
                return;
            }
        }
    } while (next_permutation(begin(perm), end(perm)));

    for (int i = 0; i < 4; i++) {
        if (arr[i].first == x || arr[i].second == x) {
            int cn = x, cm = x - min(arr[i].first, arr[i].second);

            vector<pair<int, int>> narr;
            for (int j = 0; j < 4; j++) {
                if (i == j) {
                    continue;
                }
                narr.push_back(arr[j]);
            }

            dbg("HI", cn, cm);
            if (check3(cn, cm, narr) || check3(cm, cn, narr)) {
                cout << 1 << endl;
                return;
            }
            break;
        }
    }

    cout << 0 << endl;
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3544kb

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

2 8
2 8
2 8
2 8

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3512kb

input:

5 3
5 5
3 3
3 5

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

1 2
4 8
16 32
64 128

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

4 4
2 1
4 4
2 1

output:

0

result:

ok single line: '0'

Test #7:

score: -100
Runtime Error

input:

995 51
559 565
154 536
56 780

output:


result: