QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#175440#6563. Four SquareNadimAC ✓1ms3852kbC++204.7kb2023-09-10 18:11:032023-09-10 18:11:03

Judging History

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

  • [2023-09-10 18:11:03]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3852kb
  • [2023-09-10 18:11:03]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<"["<<#x<<": "<<x<<"]\n"
#define debug2(x, y) cout<<"["<<#x<<": "<<x<<"]"<<"  ["<<#y<<": "<<y<<"]\n"
#define debug3(x, y, z) cout<<"["<<#x<<": "<<x<<"]"<<"  ["<<#y<<": "<<y<<"]"<<"  ["<<#z<<": "<<z<<"]\n"
#define debug4(x, y, z, k) cout<<"["<<#x<<": "<<x<<"]"<<"  ["<<#y<<": "<<y<<"]"<<"  ["<<#z<<": "<<z<<"]"<<"  ["<<#k<<": "<<k<<"]\n"
#define debug5(x, y, z, k, m) cout<<"["<<#x<<": "<<x<<"]"<<"  ["<<#y<<": "<<y<<"]"<<"  ["<<#z<<": "<<z<<"]"<<"  ["<<#k<<": "<<k<<"]"<<"  ["<<#m<<": "<<m<<"]\n"
#define debug6(x, y, z, k, m, n) cout<<"["<<#x<<": "<<x<<"]"<<"  ["<<#y<<": "<<y<<"]"<<"  ["<<#z<<": "<<z<<"]"<<"  ["<<#k<<": "<<k<<"]"<<"  ["<<#m<<": "<<m<<"]"<<"  ["<<#n<<": "<<n<<"]\n"

const int n = 4;

int poss1(vector<pair<int,int>> now, int w, int h) {
    assert(now.size() == 1);
    if(w <= 0 || h <= 0) return 0;
    if(now[0].first == w && now[0].second == h) return 1;
    if(now[0].second == w && now[0].first == h) return 1;
    return 0;
}

int poss2(vector<pair<int,int>> now, int w, int h) {
    assert(now.size() == 2);
    if(w <= 0 || h <= 0) return 0;
    for(int i=0; i<2; i++) {
        vector<pair<int,int>> pass;
        for(int j=0; j<2; j++) if(j != i) {
            pass.push_back(now[j]);
        }
        if(now[i].first == w) return poss1(pass, w, h - now[i].second);
        if(now[i].second == w) return poss1(pass, w, h - now[i].first);
        if(now[i].first == h) return poss1(pass, w-now[i].second, h);
        if(now[i].second == h) return poss1(pass, w-now[i].first, h);
    }
    return 0;
}

int poss3(vector<pair<int,int>> now, int w, int h) {
    assert(now.size() == 3);
    //debug2(w, h);
    if(w <= 0 || h <= 0) return 0;
    for(int i=0; i<3; i++) {
        vector<pair<int,int>> pass;
        for(int j=0; j<3; j++) if(j != i) {
            pass.push_back(now[j]);
        }
        if(now[i].first == w) return poss2(pass, w, h - now[i].second);
        if(now[i].second == w) return poss2(pass, w, h - now[i].first);
        if(now[i].first == h) return poss2(pass, w-now[i].second, h);
        if(now[i].second == h) return poss2(pass, w-now[i].first, h);
    }
    return 0;
}

int poss4(vector<pair<int,int>> a, int len) {
    assert(a.size() == 4);
    for(int i=0; i<n; i++) {
        vector<pair<int,int>> pass;
        for(int j=0; j<n; j++) if(j != i) {
            pass.push_back(a[j]);
        }
        if(a[i].first == len) return poss3(pass, len, len - a[i].second);
        if(a[i].second == len) return poss3(pass, len, len - a[i].first);
    }
    //debug(33);
    int ok = 0;
    //check the cases where above 2 block form a rectangle
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) if(j != i) {
            vector<pair<int,int>> pass;
            for(int k=0; k<n; k++) {
                if(k == i || k==j) continue;
                pass.push_back(a[k]);
            }

            for(int mask=0; mask<4; mask++) {
                vector<pair<int,int>> now = {a[i], a[j]};
                for(int at = 0; at < 2; at++) {
                    if((mask&(1<<at))) swap(now[at].first, now[at].second);
                }
                if(now[0].first + now[1].first == len && now[0].second == now[1].second) ok |= poss2(pass, len, len - now[0].second);
            }
        }
    }
    //above 2 doesnt form a rectangle
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) if(j != i) {
            for(int k=0; k<n; k++) if(k != i && k != j) {
                for(int l=0; l<n; l++) if(l != i && l !=j && l != k) {
                    for(int mask=0; mask < 16; mask++) {
                        vector<pair<int,int>> now = {a[i], a[j], a[k], a[l]};
                        for(int at = 0; at < n; at++) if((mask&(1<<at))) {
                            swap(now[at].first, now[at].second);
                        }
                        if(now[0].first + now[1].first == len
                            && now[0].first == now[2].first
                            && now[1].first == now[3].first
                            && now[0].second + now[2].second == len
                            && now[1].second + now[3].second == len) return 1;
                    }
                }
            }
        }
    }
    return ok;
}

int main() {
    vector<pair<int,int>> a(n);
    int area = 0;
    for(int i=0; i<n; i++) {
        cin>> a[i].first >> a[i].second;
        area += a[i].first * a[i].second;
    }
    int len = sqrt(area);
    while(len * len < area) len++;
    if(len*len > area) {
        cout<< 0 << endl;
        return 0;
    }
    //debug(len);
    if(poss4(a, len)) cout<< 1 << endl;
    else cout<< 0 << endl;

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3552kb

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

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

input:

2 8
2 8
2 8
2 8

output:

1

result:

ok single line: '1'

Test #4:

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

input:

5 3
5 5
3 3
3 5

output:

1

result:

ok single line: '1'

Test #5:

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

input:

1 2
4 8
16 32
64 128

output:

0

result:

ok single line: '0'

Test #6:

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

input:

4 4
2 1
4 4
2 1

output:

0

result:

ok single line: '0'

Test #7:

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

input:

995 51
559 565
154 536
56 780

output:

0

result:

ok single line: '0'

Test #8:

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

input:

391 694
540 42
240 937
691 246

output:

0

result:

ok single line: '0'

Test #9:

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

input:

519 411
782 710
299 45
21 397

output:

0

result:

ok single line: '0'

Test #10:

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

input:

96 960
948 18
108 82
371 576

output:

0

result:

ok single line: '0'

Test #11:

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

input:

3 2
4 3
3 1
1 4

output:

0

result:

ok single line: '0'

Test #12:

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

input:

4 3
1 2
4 4
3 2

output:

0

result:

ok single line: '0'

Test #13:

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

input:

4 4
1 3
5 4
2 5

output:

0

result:

ok single line: '0'

Test #14:

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

input:

1000 1000
1000 1000
1000 1000
1000 1000

output:

1

result:

ok single line: '1'

Test #15:

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

input:

1000 999
998 1000
997 1000
997 997

output:

1

result:

ok single line: '1'

Test #16:

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

input:

1 3
3 3
3 3
4 7

output:

1

result:

ok single line: '1'

Test #17:

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

input:

2 5
5 4
7 1
6 2

output:

1

result:

ok single line: '1'

Test #18:

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

input:

12 2
12 7
7 12
16 4

output:

1

result:

ok single line: '1'

Test #19:

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

input:

7 2
2 14
5 14
7 12

output:

1

result:

ok single line: '1'

Test #20:

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

input:

32 36
5 1
1 37
35 5

output:

1

result:

ok single line: '1'

Test #21:

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

input:

28 30
30 1
31 1
2 30

output:

1

result:

ok single line: '1'

Test #22:

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

input:

66 68
9 11
7 66
9 64

output:

1

result:

ok single line: '1'

Test #23:

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

input:

59 44
25 44
40 32
40 52

output:

1

result:

ok single line: '1'

Test #24:

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

input:

4 4
2 3
4 2
3 2

output:

1

result:

ok single line: '1'