QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#415641#6563. Four Squareskittles1412#AC ✓267ms34636kbC++174.5kb2024-05-21 07:53:162024-05-21 07:53:17

Judging History

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

  • [2024-05-21 07:53:17]
  • 评测
  • 测评结果:AC
  • 用时:267ms
  • 内存:34636kb
  • [2024-05-21 07:53:16]
  • 提交

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 == x1) {
            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;
    }

    for (auto& [cx, cy] : arr) {
        if (cx > x || cy > x) {
            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: 3556kb

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

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

input:

2 8
2 8
2 8
2 8

output:

1

result:

ok single line: '1'

Test #4:

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

input:

5 3
5 5
3 3
3 5

output:

1

result:

ok single line: '1'

Test #5:

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

input:

1 2
4 8
16 32
64 128

output:

0

result:

ok single line: '0'

Test #6:

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

input:

4 4
2 1
4 4
2 1

output:

0

result:

ok single line: '0'

Test #7:

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

input:

995 51
559 565
154 536
56 780

output:

0

result:

ok single line: '0'

Test #8:

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

input:

391 694
540 42
240 937
691 246

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 267ms
memory: 9420kb

input:

519 411
782 710
299 45
21 397

output:

0

result:

ok single line: '0'

Test #10:

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

input:

96 960
948 18
108 82
371 576

output:

0

result:

ok single line: '0'

Test #11:

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

input:

3 2
4 3
3 1
1 4

output:

0

result:

ok single line: '0'

Test #12:

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

input:

4 3
1 2
4 4
3 2

output:

0

result:

ok single line: '0'

Test #13:

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

input:

4 4
1 3
5 4
2 5

output:

0

result:

ok single line: '0'

Test #14:

score: 0
Accepted
time: 63ms
memory: 34636kb

input:

1000 1000
1000 1000
1000 1000
1000 1000

output:

1

result:

ok single line: '1'

Test #15:

score: 0
Accepted
time: 59ms
memory: 34512kb

input:

1000 999
998 1000
997 1000
997 997

output:

1

result:

ok single line: '1'

Test #16:

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

input:

1 3
3 3
3 3
4 7

output:

1

result:

ok single line: '1'

Test #17:

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

input:

2 5
5 4
7 1
6 2

output:

1

result:

ok single line: '1'

Test #18:

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

input:

12 2
12 7
7 12
16 4

output:

1

result:

ok single line: '1'

Test #19:

score: 0
Accepted
time: 1ms
memory: 3620kb

input:

7 2
2 14
5 14
7 12

output:

1

result:

ok single line: '1'

Test #20:

score: 0
Accepted
time: 1ms
memory: 3820kb

input:

32 36
5 1
1 37
35 5

output:

1

result:

ok single line: '1'

Test #21:

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

input:

28 30
30 1
31 1
2 30

output:

1

result:

ok single line: '1'

Test #22:

score: 0
Accepted
time: 1ms
memory: 3612kb

input:

66 68
9 11
7 66
9 64

output:

1

result:

ok single line: '1'

Test #23:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

59 44
25 44
40 32
40 52

output:

1

result:

ok single line: '1'

Test #24:

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

input:

4 4
2 3
4 2
3 2

output:

1

result:

ok single line: '1'