QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#134448#6563. Four SquareNoobie_99#WA 639ms4124kbC++201.7kb2023-08-03 20:05:482023-08-03 20:05:51

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-03 20:05:51]
  • 评测
  • 测评结果:WA
  • 用时:639ms
  • 内存:4124kb
  • [2023-08-03 20:05:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define tsolve int t; cin >> t; while(t--) solve
#define debug(x) cerr << __LINE__ << ": "#x" = " << (x) << endl
#define nl '\n'
#define all(x) ::begin(x), ::end(x)
#define sz(x) (int)::size(x)
using ll = long long;
using ld = long double;

ll _sqrt(ll x) {
	ll ans = max(0.0L, sqrtl(x) - 5);
	while (ans * ans < x) ans++;
	return ans;
}

void answer(bool ans) {
	cout << ans << '\n';
	exit(0);
}

void solve() {
    vector<pair<int, int>> a(4);
	int sm = 0;
	for (auto& [x, y] : a) cin >> x >> y, sm += x * y;

	int dim = _sqrt(sm);
	if (dim * dim != sm) answer(false);

	int idk = dim;
	for (auto& [x, y] : a) {
		if (x > y) swap(x, y);

		if (y > dim) answer(false);
		if (y == dim) idk -= x, x = 0, y = 0;
	}

	sort(all(a));
	do {
		vector<pair<int, int>> ta(4);
		for (int mask=0; mask<(1<<4); mask++) {
			for (int i=0; i<4; i++) {
				ta[i] = a[i];
				if (mask & (1<<i)) swap(ta[i].first, ta[i].second);
			}

			vector<vector<bool>> b(dim, vector<bool>(idk));
			int cur = 0;
			auto f = [&](int i, int j, int i2, int j2) {
				//debug(i), debug(j), debug(i2), debug(j2);
				for (int x=i; x<i2; x++) for (int y=j; y<j2; y++) {
					cur += 1 - b[x][y];
					b[x][y] = true;
				}
			};
			f(0, 0, ta[0].first, ta[0].second);
			f(0, idk - ta[1].second, ta[1].first, idk);
			f(dim - ta[2].first, 0, dim, ta[2].second);
			f(dim - ta[3].first, idk - ta[3].second, dim, idk);
			//debug(cur);
			if (cur == dim * idk) answer(true);
		}
	} while (next_permutation(all(a)));
	answer(false);
}
 
int main() {
	cin.tie(0)->sync_with_stdio(false);
	cout << setprecision(16);
	solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3468kb

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3536kb

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3536kb

input:

2 8
2 8
2 8
2 8

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3464kb

input:

5 3
5 5
3 3
3 5

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3472kb

input:

1 2
4 8
16 32
64 128

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

4 4
2 1
4 4
2 1

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3456kb

input:

995 51
559 565
154 536
56 780

output:

0

result:

ok single line: '0'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3536kb

input:

391 694
540 42
240 937
691 246

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 639ms
memory: 3608kb

input:

519 411
782 710
299 45
21 397

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3448kb

input:

96 960
948 18
108 82
371 576

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3524kb

input:

3 2
4 3
3 1
1 4

output:

0

result:

ok single line: '0'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3520kb

input:

4 3
1 2
4 4
3 2

output:

0

result:

ok single line: '0'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3520kb

input:

4 4
1 3
5 4
2 5

output:

0

result:

ok single line: '0'

Test #14:

score: 0
Accepted
time: 9ms
memory: 4064kb

input:

1000 1000
1000 1000
1000 1000
1000 1000

output:

1

result:

ok single line: '1'

Test #15:

score: 0
Accepted
time: 102ms
memory: 4124kb

input:

1000 999
998 1000
997 1000
997 997

output:

1

result:

ok single line: '1'

Test #16:

score: -100
Wrong Answer
time: 1ms
memory: 3476kb

input:

1 3
3 3
3 3
4 7

output:

0

result:

wrong answer 1st lines differ - expected: '1', found: '0'