QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#415595 | #6563. Four Square | ngpin04# | AC ✓ | 64ms | 19384kb | C++14 | 2.4kb | 2024-05-21 03:45:42 | 2024-05-21 03:45:43 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define bit(n) (1LL << (n))
#define getbit(x, i) (((x) >> (i)) & 1)
#define pii pair <int, int>
#define ALL(x) x.begin(), x.end()
using namespace std;
const int oo = 1e9;
const long long ooo = 1e18;
template<typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {
a = b;
return true;
}
return false;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
vector <pair <int, int>> dims(4);
int sum = 0;
for (auto &[w, h] : dims) {
cin >> w >> h;
sum += w * h;
}
int n = sqrt(sum);
if (n * n != sum) {
cout << "0\n";
return 0;
}
vector <vector <int>> a(n + 1, vector <int> (n + 1, 0));
for (int i = 0; i <= n; i++) {
a[0][i] = a[i][0] = 1;
}
vector <bool> flag(4);
function <void(int)> brute = [&](int cur) {
if (cur == 4) {
cout << "1\n";
exit(0);
}
int rx = -1, ry = -1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) if (!a[i][j] && a[i - 1][j] && a[i][j - 1]) {
tie(rx, ry) = mp(i, j);
}
for (int ind = 0; ind < 4; ind++) if (!flag[ind]) {
auto [w, h] = dims[ind];
flag[ind] = true;
for (int rep = 0; rep < 2; rep++) {
bool ok = true;
for (int i = rx; i < rx + h; i++)
for (int j = ry; j < ry + w; j++) {
if (i > n || j > n || a[i][j]) {
ok = false;
break;
}
}
if (ok) {
for (int i = rx; i < rx + h; i++)
for (int j = ry; j < ry + w; j++) {
a[i][j] = 1;
}
brute(cur + 1);
for (int i = rx; i < rx + h; i++)
for (int j = ry; j < ry + w; j++) {
a[i][j] = 0;
}
}
swap(h, w);
}
flag[ind] = false;
}
};
brute(0);
cout << "0\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3664kb
input:
1 1 1 1 1 1 1 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3444kb
input:
3 1 3 3 2 2 3 3
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3448kb
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: 1ms
memory: 3520kb
input:
1 2 4 8 16 32 64 128
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
4 4 2 1 4 4 2 1
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 2ms
memory: 5012kb
input:
995 51 559 565 154 536 56 780
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 20ms
memory: 5900kb
input:
391 694 540 42 240 937 691 246
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 64ms
memory: 6160kb
input:
519 411 782 710 299 45 21 397
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 5ms
memory: 4256kb
input:
96 960 948 18 108 82 371 576
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
3 2 4 3 3 1 1 4
output:
0
result:
ok single line: '0'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
4 3 1 2 4 4 3 2
output:
0
result:
ok single line: '0'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
4 4 1 3 5 4 2 5
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 16ms
memory: 19384kb
input:
1000 1000 1000 1000 1000 1000 1000 1000
output:
1
result:
ok single line: '1'
Test #15:
score: 0
Accepted
time: 12ms
memory: 19124kb
input:
1000 999 998 1000 997 1000 997 997
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3524kb
input:
1 3 3 3 3 3 4 7
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
2 5 5 4 7 1 6 2
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
12 2 12 7 7 12 16 4
output:
1
result:
ok single line: '1'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
7 2 2 14 5 14 7 12
output:
1
result:
ok single line: '1'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3428kb
input:
32 36 5 1 1 37 35 5
output:
1
result:
ok single line: '1'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
28 30 30 1 31 1 2 30
output:
1
result:
ok single line: '1'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
66 68 9 11 7 66 9 64
output:
1
result:
ok single line: '1'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
59 44 25 44 40 32 40 52
output:
1
result:
ok single line: '1'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
4 4 2 3 4 2 3 2
output:
1
result:
ok single line: '1'