QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#643472#6563. Four Squareenze114514WA 1ms3788kbC++207.2kb2024-10-15 21:19:592024-10-15 21:20:00

Judging History

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

  • [2024-10-15 21:20:00]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3788kb
  • [2024-10-15 21:19:59]
  • 提交

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;
}

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
    // Use bitmasking: for i from 0 to 15, each bit represents rotation of a pane
    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
        // List of combinations:
        vector<vector<int>> combinations = {
            {0,1,2,3},
            {0,2,1,3},
            {0,3,1,2},
            {1,2,0,3},
            {1,3,0,2},
            {2,3,0,1}
        };
        // To avoid duplicate groupings, use indices where first pane in group1 is less than group2
        // Alternatively, use binary masks
        for(int msk=1; msk<(1<<4)-1; msk++){
            // Check if msk represents a group of two panes
            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 group1 can form a row
            // Group1: sum of widths == S and heights equal to some h1
            long long g1_width = group1[0].first + group1[1].first;
            long long g1_height = max(group1[0].second, group1[1].second);
            // Alternatively, both heights must be equal and sum to S when combined with group2
            // For simplicity, consider if heights are equal
            if(group1[0].second == group1[1].second){
                // Similarly for group2
                if(group2[0].second == group2[1].second){
                    // Check if both groups have heights such that sum equals S
                    if(g1_width == S){
                        long long g2_width = group2[0].first + group2[1].first;
                        if(g2_width == S){
                            long long total_height = group1[0].second + group2[0].second;
                            if(total_height == S){
                                possible = true;
                                break;
                            }
                        }
                    }
                }
            }
            if(possible) 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 group1 can form a column
            // Group1: sum of heights == S and widths equal
            if(group1[0].first == group1[1].first){
                if(group2[0].first == group2[1].first){
                    long long g1_height = group1[0].second + group1[1].second;
                    long long g2_height = group2[0].second + group2[1].second;
                    if(g1_height == S && g2_height == S){
                        long long total_width = group1[0].first + group2[0].first;
                        if(total_width == 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
        // Iterate through all combinations of two panes for the top row
        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
            if(top[0].first + top[1].first != S) continue;
            // Heights of top row must match heights of bottom row
            if(top[0].second != top[1].second) continue;
            // Similarly for bottom row
            if(bottom[0].first + bottom[1].first != S) continue;
            if(bottom[0].second != bottom[1].second) continue;
            // Sum of heights of top and bottom rows must be S
            long long total_height = top[0].second + bottom[0].second;
            if(total_height != S) continue;
            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: 1ms
memory: 3556kb

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

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

input:

2 8
2 8
2 8
2 8

output:

1

result:

ok single line: '1'

Test #4:

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

input:

5 3
5 5
3 3
3 5

output:

1

result:

ok single line: '1'

Test #5:

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

input:

1 2
4 8
16 32
64 128

output:

0

result:

ok single line: '0'

Test #6:

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

input:

4 4
2 1
4 4
2 1

output:

0

result:

ok single line: '0'

Test #7:

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

input:

995 51
559 565
154 536
56 780

output:

0

result:

ok single line: '0'

Test #8:

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

input:

391 694
540 42
240 937
691 246

output:

0

result:

ok single line: '0'

Test #9:

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

input:

519 411
782 710
299 45
21 397

output:

0

result:

ok single line: '0'

Test #10:

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

input:

96 960
948 18
108 82
371 576

output:

0

result:

ok single line: '0'

Test #11:

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

input:

3 2
4 3
3 1
1 4

output:

0

result:

ok single line: '0'

Test #12:

score: 0
Accepted
time: 1ms
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: 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: 3724kb

input:

1000 1000
1000 1000
1000 1000
1000 1000

output:

1

result:

ok single line: '1'

Test #15:

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

input:

1000 999
998 1000
997 1000
997 997

output:

1

result:

ok single line: '1'

Test #16:

score: -100
Wrong Answer
time: 0ms
memory: 3580kb

input:

1 3
3 3
3 3
4 7

output:

0

result:

wrong answer 1st lines differ - expected: '1', found: '0'