QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#643477 | #6563. Four Square | enze114514 | AC ✓ | 0ms | 3852kb | C++20 | 13.1kb | 2024-10-15 21:21:20 | 2024-10-15 21:21:21 |
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;
}
// 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'