QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#308140 | #6563. Four Square | Mizara# | AC ✓ | 2ms | 3856kb | C++14 | 4.0kb | 2024-01-19 16:30:59 | 2024-01-19 16:31:00 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <math.h>
const int OO = 0;
const int md = 998244353;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll gcd(ll x, ll y) {
x = max(x, y);
y = min(x, y);
ll z;
while (y > 0) {
z = x;
x = y;
y = z % y;
}
return x;
}
struct rect {
int xlo, xhi;
int ylo, yhi;
rect() {}
rect(int _xlo, int _xhi, int _ylo, int _yhi) {
xlo = _xlo;
xhi = _xhi;
ylo = _ylo;
yhi = _yhi;
}
bool operator < (const rect& a) const {
return ylo < a.ylo;
}
};
const int N = 2002;
int first[4][N];
bool intersect_range(int alo, int ahi, int blo, int bhi) {
if (ahi < blo || bhi < alo) return false;
return true;
}
bool intersect(const rect& a, const rect& b) {
return intersect_range(a.xlo, a.xhi, b.xlo, b.xhi) && intersect_range(a.ylo, a.yhi, b.ylo, b.yhi);
}
bool check(int sz, const rect& a, vector<rect> &build) {
if (!(0 <= a.xlo && a.xhi < sz && 0 <= a.ylo && a.yhi < sz)) return false;
for (int i = 0; i + 1 < build.size(); i++)
if (intersect(a, build[i])) return false;
return true;
}
bool work(int sz, int i, vector<pair<int, int>> &a, vector<rect> &build) {
if (i == 4) return true;
auto tmpbuild = build;
sort(build.begin(), build.end());
// get first for each row
for (int row = 0; row < sz; row++) {
int nxt = 0;
for (auto& b : build) {
if (b.xlo <= row && row <= b.xhi && nxt == b.ylo)
nxt = b.yhi + 1;
}
first[i][row] = nxt;
}
build = tmpbuild;
if (OO) {
cout << "build:\n";
for (auto& i : build) {
cout << i.xlo << " " << i.xhi << " " << i.ylo << " " << i.yhi << endl;
}
cout << "firsts:\n";
for (int row = 0; row < sz; row++)
cout << first[i][row] << endl;
cout << endl;
}
// try no rotation
if (first[i][0] < sz) {
build.push_back(rect(0, 0 + a[i].first - 1, first[i][0], first[i][0] + a[i].second - 1));
if (check(sz, build.back(), build) && work(sz, i + 1, a, build)) return true;
build.pop_back();
}
for (int row = 1; row < sz; row++) {
if (first[i][row - 1] > first[i][row]) {
build.push_back(rect(row, row + a[i].first - 1, first[i][row], first[i][row] + a[i].second - 1));
if (check(sz, build.back(), build) && work(sz, i + 1, a, build)) return true;
build.pop_back();
}
}
// try rotation
swap(a[i].first, a[i].second);
if (first[i][0] < sz) {
build.push_back(rect(0, 0 + a[i].first - 1, first[i][0], first[i][0] + a[i].second - 1));
if (check(sz, build.back(), build) && work(sz, i + 1, a, build)) return true;
build.pop_back();
}
for (int row = 1; row < sz; row++) {
if (first[i][row - 1] > first[i][row]) {
build.push_back(rect(row, row + a[i].first - 1, first[i][row], first[i][row] + a[i].second - 1));
if (check(sz, build.back(), build) && work(sz, i + 1, a, build)) return true;
build.pop_back();
}
}
return false;
}
void solve() {
vector<pair<int, int>> a(4);
for (int i = 0; i < 4; i++) {
cin >> a[i].first;
cin >> a[i].second;
}
int area = 0;
for (auto b: a) {
area += b.first * b.second;
}
int side = int(sqrt(area));
for (int i = max(1, side - 3); i <= side + 3; i++) {
if (i * i == area) {
side = i;
break;
}
}
if (side * side != area) {
cout << 0 << endl;
return;
}
sort(a.begin(), a.end());
do {
vector<rect> build;
if (work(side, 0, a, build)) {
if (OO) {
cout << "won with:" << endl;
cout << "a:" << endl;
for (const auto& i : a) cout << i.first << " " << i.second << endl;
cout << endl;
for (auto& i : build) {
cout << i.xlo << " " << i.xhi << " " << i.ylo << " " << i.yhi << endl;
}
}
cout << 1 << endl;
return;
}
} while (next_permutation(a.begin(), a.end()));
cout << 0 << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tests = 1;
//cin >> tests;
while (tests--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3644kb
input:
1 1 1 1 1 1 1 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
3 1 3 3 2 2 3 3
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
2 8 2 8 2 8 2 8
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
5 3 5 5 3 3 3 5
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
1 2 4 8 16 32 64 128
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
4 4 2 1 4 4 2 1
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
995 51 559 565 154 536 56 780
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3508kb
input:
391 694 540 42 240 937 691 246
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3848kb
input:
519 411 782 710 299 45 21 397
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
96 960 948 18 108 82 371 576
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
3 2 4 3 3 1 1 4
output:
0
result:
ok single line: '0'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
4 3 1 2 4 4 3 2
output:
0
result:
ok single line: '0'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
4 4 1 3 5 4 2 5
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
1000 1000 1000 1000 1000 1000 1000 1000
output:
1
result:
ok single line: '1'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
1000 999 998 1000 997 1000 997 997
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
1 3 3 3 3 3 4 7
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
2 5 5 4 7 1 6 2
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
12 2 12 7 7 12 16 4
output:
1
result:
ok single line: '1'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
7 2 2 14 5 14 7 12
output:
1
result:
ok single line: '1'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
32 36 5 1 1 37 35 5
output:
1
result:
ok single line: '1'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
28 30 30 1 31 1 2 30
output:
1
result:
ok single line: '1'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
66 68 9 11 7 66 9 64
output:
1
result:
ok single line: '1'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
59 44 25 44 40 32 40 52
output:
1
result:
ok single line: '1'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
4 4 2 3 4 2 3 2
output:
1
result:
ok single line: '1'