QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#643477#6563. Four Squareenze114514AC ✓0ms3852kbC++2013.1kb2024-10-15 21:21:202024-10-15 21:21:21

Judging History

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

  • [2024-10-15 21:21:21]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3852kb
  • [2024-10-15 21:21:20]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

// Function to check if a number is a perfect square
bool isPerfectSquare(long long x, long long &S) {
    S = sqrt((double)x);
    return S * S == x;
}

// Function to check if three panes can fill a given rectangle
bool canFillRemaining(int W, int H, vector<pair<int, int>> panes) {
    if (panes.empty()) return (W == 0 && H == 0);
    if (panes.size() == 1) {
        return ( (panes[0].first == W && panes[0].second == H) ||
                 (panes[0].second == W && panes[0].first == H) );
    }
    // If two panes
    if (panes.size() == 2) {
        // Try all possible splits
        // Horizontal split
        for(int i=0;i<2;i++) {
            for(int j=0;j<2;j++) {
                // Pane1: panes[0] as is or rotated
                int w1 = panes[0].first, h1 = panes[0].second;
                if(i) swap(w1, h1);
                // Pane2: panes[1] as is or rotated
                int w2 = panes[1].first, h2 = panes[1].second;
                if(j) swap(w2, h2);
                // Horizontal split
                if(h1 == h2 && h1 <= H && w1 + w2 == W)
                    return true;
                // Vertical split
                if(w1 == w2 && w1 <= W && h1 + h2 == H)
                    return true;
            }
        }
        return false;
    }
    // If three panes
    if (panes.size() == 3) {
        // Try all permutations and rotations
        vector<vector<pair<int, int>>> perms;
        // Generate all permutations
        vector<int> indices = {0,1,2};
        do {
            vector<pair<int, int>> perm;
            for(auto idx: indices) perm.push_back(panes[idx]);
            perms.push_back(perm);
        } while(next_permutation(indices.begin(), indices.end()));
        
        // For each permutation, try all rotation combinations
        for(auto &perm: perms){
            // There are 2^3 =8 rotation combinations
            for(int mask=0; mask<(1<<3); mask++){
                vector<pair<int, int>> rotated = perm;
                for(int i=0;i<3;i++) {
                    if(mask & (1<<i)) swap(rotated[i].first, rotated[i].second);
                }
                // Try all possible first splits
                // Split first pane horizontally
                if(rotated[0].second <= H){
                    // Remaining area: W x (H - rotated[0].second)
                    if(canFillRemaining(W, H - rotated[0].second, {rotated[1], rotated[2]}))
                        return true;
                }
                // Split first pane vertically
                if(rotated[0].first <= W){
                    // Remaining area: (W - rotated[0].first) x H
                    if(canFillRemaining(W - rotated[0].first, H, {rotated[1], rotated[2]}))
                        return true;
                }
            }
        }
        return false;
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    // Read the four panes
    vector<pair<int, int>> panes(4);
    for(int i=0;i<4;i++){
        cin >> panes[i].first >> panes[i].second;
    }
    
    // Calculate total area
    long long total_area =0;
    for(auto &p: panes){
        total_area += (long long)p.first * p.second;
    }
    
    // Check if total_area is a perfect square
    long long S;
    if(!isPerfectSquare(total_area, S)){
        cout << "0";
        return 0;
    }
    
    // Generate all 16 orientation combinations
    // Each pane can be in original or rotated state
    bool possible = false;
    for(int mask=0; mask<(1<<4); mask++){
        // Get the oriented panes
        vector<pair<int, int>> oriented(4);
        for(int i=0;i<4;i++){
            if(mask & (1<<i)){
                // Rotate the pane
                oriented[i] = {panes[i].second, panes[i].first};
            }
            else{
                // Original orientation
                oriented[i] = {panes[i].first, panes[i].second};
            }
        }
        
        // Check all possible arrangements
        
        // 1. All in one row
        long long sum_width =0;
        bool all_height_S = true;
        for(int i=0;i<4;i++){
            sum_width += oriented[i].first;
            if(oriented[i].second != S){
                all_height_S = false;
                break;
            }
        }
        if(all_height_S && sum_width == S){
            possible = true;
            break;
        }
        
        // 2. All in one column
        long long sum_height =0;
        bool all_width_S = true;
        for(int i=0;i<4;i++){
            sum_height += oriented[i].second;
            if(oriented[i].first != S){
                all_width_S = false;
                break;
            }
        }
        if(all_width_S && sum_height == S){
            possible = true;
            break;
        }
        
        // 3. Two rows
        // Generate all combinations of splitting into two groups of two
        // There are C(4,2) =6 combinations
        // To avoid duplicate groupings, use bitmasking
        for(int msk=1; msk<(1<<4)-1; msk++){
            if(__builtin_popcount(msk)!=2) continue;
            // Group1: panes with bits set in msk
            // Group2: remaining panes
            vector<pair<int, int>> group1, group2;
            for(int i=0;i<4;i++){
                if(msk & (1<<i)){
                    group1.push_back(oriented[i]);
                }
                else{
                    group2.push_back(oriented[i]);
                }
            }
            // Check if both groups can form rows
            // Each group should have sum_width == S and heights are consistent
            // Additionally, sum of heights of both rows should be S
            // For group1
            // All panes in a group should have the same height
            bool group1_same_height = true;
            int height1 = group1[0].second;
            for(auto &p: group1){
                if(p.second != height1){
                    group1_same_height = false;
                    break;
                }
            }
            if(!group1_same_height) continue;
            long long group1_sum_width =0;
            for(auto &p: group1){
                group1_sum_width += p.first;
            }
            if(group1_sum_width != S) continue;
            
            // Similarly for group2
            bool group2_same_height = true;
            int height2 = group2[0].second;
            for(auto &p: group2){
                if(p.second != height2){
                    group2_same_height = false;
                    break;
                }
            }
            if(!group2_same_height) continue;
            long long group2_sum_width =0;
            for(auto &p: group2){
                group2_sum_width += p.first;
            }
            if(group2_sum_width != S) continue;
            
            // Now, sum of heights should be S
            if((long long)height1 + (long long)height2 == S){
                possible = true;
                break;
            }
        }
        if(possible) break;
        
        // 4. Two columns
        // Similar to two rows, but swap width and height
        for(int msk=1; msk<(1<<4)-1; msk++){
            if(__builtin_popcount(msk)!=2) continue;
            vector<pair<int, int>> group1, group2;
            for(int i=0;i<4;i++){
                if(msk & (1<<i)){
                    group1.push_back(oriented[i]);
                }
                else{
                    group2.push_back(oriented[i]);
                }
            }
            // Check if both groups can form columns
            // Each group should have sum_height == S and widths are consistent
            // Additionally, sum of widths of both columns should be S
            // For group1
            bool group1_same_width = true;
            int width1 = group1[0].first;
            for(auto &p: group1){
                if(p.first != width1){
                    group1_same_width = false;
                    break;
                }
            }
            if(!group1_same_width) continue;
            long long group1_sum_height =0;
            for(auto &p: group1){
                group1_sum_height += p.second;
            }
            if(group1_sum_height != S) continue;
            
            // Similarly for group2
            bool group2_same_width = true;
            int width2 = group2[0].first;
            for(auto &p: group2){
                if(p.first != width2){
                    group2_same_width = false;
                    break;
                }
            }
            if(!group2_same_width) continue;
            long long group2_sum_height =0;
            for(auto &p: group2){
                group2_sum_height += p.second;
            }
            if(group2_sum_height != S) continue;
            
            // Now, sum of widths should be S
            if((long long)width1 + (long long)width2 == S){
                possible = true;
                break;
            }
        }
        if(possible) break;
        
        // 5. 2x2 Grid
        // Assign two panes to top row and two panes to bottom row
        // Check if both rows have sum of widths == S and heights of top and bottom rows == S
        for(int msk=1; msk<(1<<4)-1; msk++){
            if(__builtin_popcount(msk)!=2) continue;
            vector<pair<int, int>> top, bottom;
            for(int i=0;i<4;i++){
                if(msk & (1<<i)){
                    top.push_back(oriented[i]);
                }
                else{
                    bottom.push_back(oriented[i]);
                }
            }
            // Check if top row can form a row
            // Sum of widths == S and heights are same
            bool top_same_height = true;
            int top_height = top[0].second;
            for(auto &p: top){
                if(p.second != top_height){
                    top_same_height = false;
                    break;
                }
            }
            if(!top_same_height) continue;
            long long top_sum_width =0;
            for(auto &p: top){
                top_sum_width += p.first;
            }
            if(top_sum_width != S) continue;
            
            // Similarly for bottom row
            bool bottom_same_height = true;
            int bottom_height = bottom[0].second;
            for(auto &p: bottom){
                if(p.second != bottom_height){
                    bottom_same_height = false;
                    break;
                }
            }
            if(!bottom_same_height) continue;
            long long bottom_sum_width =0;
            for(auto &p: bottom){
                bottom_sum_width += p.first;
            }
            if(bottom_sum_width != S) continue;
            
            // Now, sum of heights should be S
            if( (long long)top_height + (long long)bottom_height == S ){
                possible = true;
                break;
            }
        }
        if(possible) break;
        
        // 6. One pane occupies an entire side (additional arrangement)
        // Iterate through each pane to see if it can occupy a full side
        for(int i=0;i<4;i++){
            // Current pane
            pair<int, int> pane = oriented[i];
            // Check if width == S
            if(pane.first == S){
                // Place it horizontally, occupying width=S and height=pane.second
                // Remaining area: S x (S - pane.second)
                int remaining_width = S;
                int remaining_height = S - pane.second;
                if(remaining_height <0) continue;
                // Get remaining panes
                vector<pair<int, int>> remaining_panes;
                for(int j=0;j<4;j++) if(j!=i) remaining_panes.push_back(oriented[j]);
                // Now, check if remaining_panes can fill S x (S - pane.second)
                if(canFillRemaining(remaining_width, remaining_height, remaining_panes)){
                    possible = true;
                    break;
                }
            }
            // Check if height == S
            if(pane.second == S){
                // Place it vertically, occupying width=pane.first and height=S
                // Remaining area: (S - pane.first) x S
                int remaining_width = S - pane.first;
                int remaining_height = S;
                if(remaining_width <0) continue;
                // Get remaining panes
                vector<pair<int, int>> remaining_panes;
                for(int j=0;j<4;j++) if(j!=i) remaining_panes.push_back(oriented[j]);
                // Now, check if remaining_panes can fill (S - pane.first) x S
                if(canFillRemaining(remaining_width, remaining_height, remaining_panes)){
                    possible = true;
                    break;
                }
            }
        }
        if(possible) break;
    }
    
    // Output the result
    cout << (possible ? "1" : "0");
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

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

input:

2 8
2 8
2 8
2 8

output:

1

result:

ok single line: '1'

Test #4:

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

input:

5 3
5 5
3 3
3 5

output:

1

result:

ok single line: '1'

Test #5:

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

input:

1 2
4 8
16 32
64 128

output:

0

result:

ok single line: '0'

Test #6:

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

input:

4 4
2 1
4 4
2 1

output:

0

result:

ok single line: '0'

Test #7:

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

input:

995 51
559 565
154 536
56 780

output:

0

result:

ok single line: '0'

Test #8:

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

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

input:

96 960
948 18
108 82
371 576

output:

0

result:

ok single line: '0'

Test #11:

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

input:

3 2
4 3
3 1
1 4

output:

0

result:

ok single line: '0'

Test #12:

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

input:

4 3
1 2
4 4
3 2

output:

0

result:

ok single line: '0'

Test #13:

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

input:

4 4
1 3
5 4
2 5

output:

0

result:

ok single line: '0'

Test #14:

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

input:

1000 1000
1000 1000
1000 1000
1000 1000

output:

1

result:

ok single line: '1'

Test #15:

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

input:

1000 999
998 1000
997 1000
997 997

output:

1

result:

ok single line: '1'

Test #16:

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

input:

1 3
3 3
3 3
4 7

output:

1

result:

ok single line: '1'

Test #17:

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

input:

2 5
5 4
7 1
6 2

output:

1

result:

ok single line: '1'

Test #18:

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

input:

12 2
12 7
7 12
16 4

output:

1

result:

ok single line: '1'

Test #19:

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

input:

7 2
2 14
5 14
7 12

output:

1

result:

ok single line: '1'

Test #20:

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

input:

32 36
5 1
1 37
35 5

output:

1

result:

ok single line: '1'

Test #21:

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

input:

28 30
30 1
31 1
2 30

output:

1

result:

ok single line: '1'

Test #22:

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

input:

66 68
9 11
7 66
9 64

output:

1

result:

ok single line: '1'

Test #23:

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

input:

59 44
25 44
40 32
40 52

output:

1

result:

ok single line: '1'

Test #24:

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

input:

4 4
2 3
4 2
3 2

output:

1

result:

ok single line: '1'