QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#152691 | #6563. Four Square | BUET_POISSON# | AC ✓ | 3916ms | 3776kb | C++20 | 2.3kb | 2023-08-28 17:25:26 | 2023-08-28 17:25:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define getbit(n, i) (((n) & (1LL << (i))) != 0)
#define setbit0(n, i) ((n) & (~(1LL << (i))))
#define setbit1(n, i) ((n) | (1LL << (i)))
#define togglebit(n, i) ((n) ^ (1LL << (i)))
#define lastone(n) ((n) & (-(n)))
char gap = 32;
#define int long long
#define ii pair<int, int>
#define ll long long
#define lll __int128_t
#define pb push_back
bool put(vector<vector<bool>> &grid, int w, int h) {
int n = grid.size();
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if ( grid[i][j] == 0 and i+w-1 < n and j+h-1 < n ) {
//cout << "Placing at " << i << " " << j << endl;
for (int k=0; k<w; k++) for (int m=0; m<h; m++) grid[i+k][j+m] = 1;
return true;
}
}
}
return false;
}
void solve() {
vector<ii> planes;
int tot_area = 0;
for (int i=0; i<4; i++) {
int a, b;
cin >> a >> b;
planes.pb({a, b});
tot_area += a*b;
}
int s = sqrt(tot_area);
if ((s+1)*(s+1) == tot_area) s++;
if (s * s!= tot_area) {
cout << 0 << endl;
return;
}
vector<int> order = {0, 1, 2, 3};
int possible = 0;
int loop = 0;
do {
for (int i=0; i<(1<<4); i++) {
vector<ii> a;
for (int x: order) a.push_back(planes[x]);
for (int j=0; j<4; j++) if ( (i>>j) & 1) {
swap(a[j].first, a[j].second);
}
vector< vector<bool> > arr(s, vector<bool> (s));
int pos = 1;
for (int j=0; j<4; j++) if (!put(arr, a[j].first, a[j].second)) {
//cout << "Couldnt place " << j << " " << a[j].first << " " << a[j].second << endl;
pos = 0;
}
for (int i=0; i<s; i++) for (int j=0; j<s; j++) if (arr[i][j] == false) pos = 0;
if (pos) possible = 1;
//return ;
}
} while(next_permutation(order.begin(), order.end()));
cout << possible << endl;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3436kb
input:
1 1 1 1 1 1 1 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3424kb
input:
3 1 3 3 2 2 3 3
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3448kb
input:
2 8 2 8 2 8 2 8
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3400kb
input:
5 3 5 5 3 3 3 5
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
1 2 4 8 16 32 64 128
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3480kb
input:
4 4 2 1 4 4 2 1
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 427ms
memory: 3516kb
input:
995 51 559 565 154 536 56 780
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 535ms
memory: 3664kb
input:
391 694 540 42 240 937 691 246
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 593ms
memory: 3556kb
input:
519 411 782 710 299 45 21 397
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 297ms
memory: 3544kb
input:
96 960 948 18 108 82 371 576
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
3 2 4 3 3 1 1 4
output:
0
result:
ok single line: '0'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3484kb
input:
4 3 1 2 4 4 3 2
output:
0
result:
ok single line: '0'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
4 4 1 3 5 4 2 5
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 3916ms
memory: 3776kb
input:
1000 1000 1000 1000 1000 1000 1000 1000
output:
1
result:
ok single line: '1'
Test #15:
score: 0
Accepted
time: 3553ms
memory: 3760kb
input:
1000 999 998 1000 997 1000 997 997
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3400kb
input:
1 3 3 3 3 3 4 7
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3428kb
input:
2 5 5 4 7 1 6 2
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
12 2 12 7 7 12 16 4
output:
1
result:
ok single line: '1'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3404kb
input:
7 2 2 14 5 14 7 12
output:
1
result:
ok single line: '1'
Test #20:
score: 0
Accepted
time: 3ms
memory: 3404kb
input:
32 36 5 1 1 37 35 5
output:
1
result:
ok single line: '1'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3400kb
input:
28 30 30 1 31 1 2 30
output:
1
result:
ok single line: '1'
Test #22:
score: 0
Accepted
time: 6ms
memory: 3436kb
input:
66 68 9 11 7 66 9 64
output:
1
result:
ok single line: '1'
Test #23:
score: 0
Accepted
time: 6ms
memory: 3496kb
input:
59 44 25 44 40 32 40 52
output:
1
result:
ok single line: '1'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3424kb
input:
4 4 2 3 4 2 3 2
output:
1
result:
ok single line: '1'