QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#239090#6563. Four SquareFyind#AC ✓1ms3828kbC++172.4kb2023-11-04 18:26:452023-11-04 18:26:45

Judging History

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

  • [2023-11-04 18:26:45]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3828kb
  • [2023-11-04 18:26:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define _ <<" "<<
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 5e5 + 5;


int n, m;

bool solve(int x,int y, vector<pii> A) {
    if (x <= 0 || y <= 0) return false;
    if (sz(A) == 1) {
        pii s = A[0];
        return s.first == x && s.second == y || s.second == x && s.first == y;
    }
    for (int k = 0;k < sz(A); ++k) if (A[k].first <= x && A[k].second <= y) {
        vector<pii> rest;
        for (int i = 0;i < sz(A); ++i) if (i != k) rest.push_back(A[i]);

        auto distri = [&](pii na,pii nb) {
            if (nb.first == 0 || nb.second == 0) {
                return solve(na.first,na.second,rest);
            }
            if (na.first == 0 || na.second == 0) {
                return solve(nb.first,nb.second,rest);
            }
            for (int t = 0;t < sz(rest); ++t) {
                vector<pii> ra, rb;
                ra.push_back(rest[t]);
                for (int j = 0;j < sz(rest); ++j) if (j != t) {
                    rb.push_back(rest[j]);
                }
                if (solve(na.first,na.second,ra) && solve(nb.first,nb.second,rb)) return true;
            }
            return false;
        };
        pii na = {x-A[k].second, A[k].first}, nb = {y-A[k].first,x};
        if (distri(na,nb)) return true;
        na = {x-A[k].second,y}; nb = {A[k].second,y-A[k].first};
        if (distri(na,nb)) return true;
        na = {x-A[k].first,A[k].second}; nb = {y-A[k].second,x};
        if (distri(na,nb)) return true;
        na = {x-A[k].first,y}; nb = {y-A[k].second,A[k].first};
        if (distri(na,nb)) return true;
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    vector<pii> sq;
    vector<int> val;
    for (int i = 1;i <= 4; ++i) {
        int x,y; cin >> x >> y;
        sq.push_back({x,y});
        val.push_back(x); val.push_back(y);
    }
    int len = sz(val);
    for (int i = 0;i < len; ++i) {
        for (int j = i+1;j < len; ++j) {
            val.push_back(val[i]+val[j]);
        }
    }
    sort(val.begin(),val.end());
    val.erase(unique(val.begin(),val.end()),val.end());
    for (auto x : val) {
        if (solve(x,x,sq)) {
            cout << "1" << '\n';
            return 0;
        }
    }
    cout << '0' << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

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

input:

2 8
2 8
2 8
2 8

output:

1

result:

ok single line: '1'

Test #4:

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

input:

5 3
5 5
3 3
3 5

output:

1

result:

ok single line: '1'

Test #5:

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

input:

1 2
4 8
16 32
64 128

output:

0

result:

ok single line: '0'

Test #6:

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

input:

4 4
2 1
4 4
2 1

output:

0

result:

ok single line: '0'

Test #7:

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

input:

995 51
559 565
154 536
56 780

output:

0

result:

ok single line: '0'

Test #8:

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

input:

391 694
540 42
240 937
691 246

output:

0

result:

ok single line: '0'

Test #9:

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

input:

519 411
782 710
299 45
21 397

output:

0

result:

ok single line: '0'

Test #10:

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

input:

96 960
948 18
108 82
371 576

output:

0

result:

ok single line: '0'

Test #11:

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

input:

3 2
4 3
3 1
1 4

output:

0

result:

ok single line: '0'

Test #12:

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

input:

4 3
1 2
4 4
3 2

output:

0

result:

ok single line: '0'

Test #13:

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

input:

4 4
1 3
5 4
2 5

output:

0

result:

ok single line: '0'

Test #14:

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

input:

1000 1000
1000 1000
1000 1000
1000 1000

output:

1

result:

ok single line: '1'

Test #15:

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

input:

1000 999
998 1000
997 1000
997 997

output:

1

result:

ok single line: '1'

Test #16:

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

input:

1 3
3 3
3 3
4 7

output:

1

result:

ok single line: '1'

Test #17:

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

input:

2 5
5 4
7 1
6 2

output:

1

result:

ok single line: '1'

Test #18:

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

input:

12 2
12 7
7 12
16 4

output:

1

result:

ok single line: '1'

Test #19:

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

input:

7 2
2 14
5 14
7 12

output:

1

result:

ok single line: '1'

Test #20:

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

input:

32 36
5 1
1 37
35 5

output:

1

result:

ok single line: '1'

Test #21:

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

input:

28 30
30 1
31 1
2 30

output:

1

result:

ok single line: '1'

Test #22:

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

input:

66 68
9 11
7 66
9 64

output:

1

result:

ok single line: '1'

Test #23:

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

input:

59 44
25 44
40 32
40 52

output:

1

result:

ok single line: '1'

Test #24:

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

input:

4 4
2 3
4 2
3 2

output:

1

result:

ok single line: '1'