QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#308140#6563. Four SquareMizara#AC ✓2ms3856kbC++144.0kb2024-01-19 16:30:592024-01-19 16:31:00

Judging History

你现在查看的是最新测评结果

  • [2024-01-19 16:31:00]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:3856kb
  • [2024-01-19 16:30:59]
  • 提交

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();
}

详细

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'