QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#112166#6563. Four Squaremaomao90#RE 8ms66652kbC++172.7kb2023-06-10 14:15:022023-06-10 14:15:05

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-10 14:15:05]
  • 评测
  • 测评结果:RE
  • 用时:8ms
  • 内存:66652kb
  • [2023-06-10 14:15:02]
  • 提交

answer


// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 1005;

ii wh[4];

int memo[1 << 4][MAXN][MAXN];
bool solve(int msk, int n, int m) {
    if (msk == 0) {
        if (n == 0 || m == 0) {
            return 1;
        } else {
            return 0;
        }
    }
    if (memo[msk][n][m] != -1) {
        return memo[msk][n][m];
    }
    /*
    if (SZ(wh) == 1) {
        auto [w, h] = wh[0];
        if (min(w, h) == min(n, m) && max(w, h) == max(n, m)) {
            return 1;
        } else {
            return 0;
        }
    }
    */
        cerr << bitset<4>(msk) << ' ' << n << ' ' << m << '\n';
    REP (i, 0, 4) {
        if (msk >> i & 1 ^ 1) {
            continue;
        }
        auto [w, h] = wh[i];
        REP (z, 0, 2) {
            swap(w, h);
            if (w > n || h > m) {
                continue;
            }
            int nmsk = msk ^ (1 << i);
            for (int k = nmsk; ; k = (k - 1) & nmsk) {
                bool res = (solve(k, n - w, m) && solve(nmsk ^ k, w, m - h)) ||
                    (solve(k, n - w, h) && solve(nmsk ^ k, n, m - h));
                if (res) {
                    return memo[msk][n][m] = 1;
                }
                if (k == 0) {
                    break;
                }
            }
        }
    }
    return memo[msk][n][m] = 0;
}

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    int area = 0;
    REP (i, 0, 4) {
        int w, h; cin >> w >> h;
        wh[i] = {w, h};
        area += w * h;
    }
    int sq = -1;
    REP (i, 1, area + 1) {
        if ((ll) i * i == area) {
            sq = i;
            break;
        }
    }
    if (sq == -1) {
        cout << 0 << '\n';
        return 0;
    }
    memset(memo, -1, sizeof memo);
    cout << solve((1 << 4) - 1, sq, sq) << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 66524kb

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 3ms
memory: 66592kb

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 3ms
memory: 66532kb

input:

2 8
2 8
2 8
2 8

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 8ms
memory: 66392kb

input:

5 3
5 5
3 3
3 5

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3404kb

input:

1 2
4 8
16 32
64 128

output:

0

result:

ok single line: '0'

Test #6:

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

input:

4 4
2 1
4 4
2 1

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 8ms
memory: 66492kb

input:

995 51
559 565
154 536
56 780

output:

0

result:

ok single line: '0'

Test #8:

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

input:

391 694
540 42
240 937
691 246

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 2ms
memory: 66636kb

input:

519 411
782 710
299 45
21 397

output:

0

result:

ok single line: '0'

Test #10:

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

input:

96 960
948 18
108 82
371 576

output:

0

result:

ok single line: '0'

Test #11:

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

input:

3 2
4 3
3 1
1 4

output:

0

result:

ok single line: '0'

Test #12:

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

input:

4 3
1 2
4 4
3 2

output:

0

result:

ok single line: '0'

Test #13:

score: 0
Accepted
time: 4ms
memory: 66536kb

input:

4 4
1 3
5 4
2 5

output:

0

result:

ok single line: '0'

Test #14:

score: -100
Runtime Error

input:

1000 1000
1000 1000
1000 1000
1000 1000

output:


result: