QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#643472 | #6563. Four Square | enze114514 | WA | 1ms | 3788kb | C++20 | 7.2kb | 2024-10-15 21:19:59 | 2024-10-15 21:20:00 |
Judging History
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'