QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#363149#6563. Four Squaredistant_yesterday#AC ✓0ms3884kbC++142.7kb2024-03-23 18:50:452024-03-23 18:50:45

Judging History

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

  • [2024-03-23 18:50:45]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3884kb
  • [2024-03-23 18:50:45]
  • 提交

answer

#include <bits/stdc++.h>
#ifdef LOCAL
// #define debug(...) 42
#include "cp_debug.h"
#else
#define debug(...) 42
#endif
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
using namespace std;
#define int long long

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

template<typename T> void read(T &x){
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
    read(first);
    read(args...);
}
template<typename T> void write(T x) {
    if(x > 9) write(x/10);
    putchar(x%10 + '0');
}

set<pii> combine(set<pii> r1, set<pii> r2) {
    set<pii> possible;
    auto add = [&](int x, int y) {
        possible.emplace(min(x, y), max(x, y));
    };
    for(auto [w1, h1]: r1) {
        for(auto [w2, h2]: r2) {
            if(w1 == w2) {
                add(w1, h1+h2);
            }
            if(w1 == h2) {
                add(w1, h1+w2);
            }
            if(h1 == w2) {
                add(h1, w1+h2);
            }
            if(h1 == h2) {
                add(h1, w1+w2);
            }
        }
    }
    return possible;
}
bool check(set<pii> possible) {
    for(auto [w, h]: possible) {
        if(w == h) {
            debug(w,h);
            return true;
        }
    }
    return false;
}
void solve() {
    int w[4] = {}, h[4] = {}, sum = 0;
    set<pii> r[4];
    rep(i,0,4) {
        read(w[i], h[i]);
        sum += w[i]*h[i];
        r[i].emplace(min(h[i], w[i]), max(h[i], w[i]));
    }
    int leng = sqrt(sum), ok = false;
    for(int i = max(1LL,leng-3); i <= leng+3; i++) if(i*i == sum) {
        ok = true;
    }
    if(!ok) {
        cout<<0<<endl;
        return;
    }
    auto r01 = combine(r[0], r[1]);
    auto r23 = combine(r[2], r[3]);
    if(check(combine(r01, r23))) {
        cout<<1<<'\n';
        return;
    }
    auto r02 = combine(r[0], r[2]);
    auto r13 = combine(r[1], r[3]);
    if(check(combine(r02, r13))) {
        cout<<1<<'\n';
        return;
    }
    vi perm = {0,1,2,3};
    do {
        debug(perm);
        auto c = r[perm[0]];
        rep(i,1,4) {
            c = combine(c, r[perm[i]]);
        }
        if(check(c)) {
            cout<<1<<'\n';
            return;
        }
    } while(next_permutation(all(perm)));
    cout<<0<<'\n';
}

// akt+kb==ct+d
signed main() {
    int T; T=1;
    while(T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

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

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: 3560kb

input:

1 2
4 8
16 32
64 128

output:

0

result:

ok single line: '0'

Test #6:

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

input:

4 4
2 1
4 4
2 1

output:

0

result:

ok single line: '0'

Test #7:

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

input:

995 51
559 565
154 536
56 780

output:

0

result:

ok single line: '0'

Test #8:

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

input:

391 694
540 42
240 937
691 246

output:

0

result:

ok single line: '0'

Test #9:

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

input:

519 411
782 710
299 45
21 397

output:

0

result:

ok single line: '0'

Test #10:

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

input:

96 960
948 18
108 82
371 576

output:

0

result:

ok single line: '0'

Test #11:

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

input:

3 2
4 3
3 1
1 4

output:

0

result:

ok single line: '0'

Test #12:

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

input:

4 3
1 2
4 4
3 2

output:

0

result:

ok single line: '0'

Test #13:

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

input:

4 4
1 3
5 4
2 5

output:

0

result:

ok single line: '0'

Test #14:

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

input:

1000 1000
1000 1000
1000 1000
1000 1000

output:

1

result:

ok single line: '1'

Test #15:

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

input:

1000 999
998 1000
997 1000
997 997

output:

1

result:

ok single line: '1'

Test #16:

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

input:

1 3
3 3
3 3
4 7

output:

1

result:

ok single line: '1'

Test #17:

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

input:

2 5
5 4
7 1
6 2

output:

1

result:

ok single line: '1'

Test #18:

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

input:

12 2
12 7
7 12
16 4

output:

1

result:

ok single line: '1'

Test #19:

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

input:

7 2
2 14
5 14
7 12

output:

1

result:

ok single line: '1'

Test #20:

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

input:

32 36
5 1
1 37
35 5

output:

1

result:

ok single line: '1'

Test #21:

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

input:

28 30
30 1
31 1
2 30

output:

1

result:

ok single line: '1'

Test #22:

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

input:

66 68
9 11
7 66
9 64

output:

1

result:

ok single line: '1'

Test #23:

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

input:

59 44
25 44
40 32
40 52

output:

1

result:

ok single line: '1'

Test #24:

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

input:

4 4
2 3
4 2
3 2

output:

1

result:

ok single line: '1'