QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#134530#6563. Four SquareNoobie_99#AC ✓104ms13376kbC++201.5kb2023-08-03 22:28:102023-08-03 22:28:10

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 22:28:10]
  • 评测
  • 测评结果:AC
  • 用时:104ms
  • 内存:13376kb
  • [2023-08-03 22:28:10]
  • 提交

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

	for (auto& [x, y] : a) {
		if (max(x, y) > dim) answer(false);
	}

	vector dp(1<<4, vector(dim+1, vector<bool>(dim+1)));
	for (int i=0; i<4; i++) {
		dp[1<<i][a[i].first][a[i].second] = true;
		dp[1<<i][a[i].second][a[i].first] = true;
	}

	for (int i=0; i<dim+1; i++) {
		for (int j=0; j<dim+1; j++) {
			for (int k=0; k<(1<<4); k++) {
				if (!dp[k][i][j]) continue;

				for (int l=0; l<=i && i+l<=dim; l++) {
					for (int k2=0; k2<(1<<4); k2++) {
						if ((k & k2) & k) continue;
						if (dp[k2][l][j]) dp[k | k2][i+l][j] = true;
					}			
				}

				for (int l=0; l<=j && j+l<=dim; l++) {
					for (int k2=0; k2<(1<<4); k2++) {
						if ((k & k2) & k) continue;
						if (dp[k2][i][l]) dp[k | k2][i][j+l] = true;
					}			
				} 
			}
		}
	}

	cout << dp[(1<<4)-1][dim][dim] << '\n';
}
 
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: 0ms
memory: 3456kb

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

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

input:

2 8
2 8
2 8
2 8

output:

1

result:

ok single line: '1'

Test #4:

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

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: 3536kb

input:

4 4
2 1
4 4
2 1

output:

0

result:

ok single line: '0'

Test #7:

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

input:

995 51
559 565
154 536
56 780

output:

0

result:

ok single line: '0'

Test #8:

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

input:

391 694
540 42
240 937
691 246

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 23ms
memory: 5952kb

input:

519 411
782 710
299 45
21 397

output:

0

result:

ok single line: '0'

Test #10:

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

input:

96 960
948 18
108 82
371 576

output:

0

result:

ok single line: '0'

Test #11:

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

input:

3 2
4 3
3 1
1 4

output:

0

result:

ok single line: '0'

Test #12:

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

input:

4 3
1 2
4 4
3 2

output:

0

result:

ok single line: '0'

Test #13:

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

input:

4 4
1 3
5 4
2 5

output:

0

result:

ok single line: '0'

Test #14:

score: 0
Accepted
time: 97ms
memory: 13288kb

input:

1000 1000
1000 1000
1000 1000
1000 1000

output:

1

result:

ok single line: '1'

Test #15:

score: 0
Accepted
time: 104ms
memory: 13376kb

input:

1000 999
998 1000
997 1000
997 997

output:

1

result:

ok single line: '1'

Test #16:

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

input:

1 3
3 3
3 3
4 7

output:

1

result:

ok single line: '1'

Test #17:

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

input:

2 5
5 4
7 1
6 2

output:

1

result:

ok single line: '1'

Test #18:

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

input:

12 2
12 7
7 12
16 4

output:

1

result:

ok single line: '1'

Test #19:

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

input:

7 2
2 14
5 14
7 12

output:

1

result:

ok single line: '1'

Test #20:

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

input:

32 36
5 1
1 37
35 5

output:

1

result:

ok single line: '1'

Test #21:

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

input:

28 30
30 1
31 1
2 30

output:

1

result:

ok single line: '1'

Test #22:

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

input:

66 68
9 11
7 66
9 64

output:

1

result:

ok single line: '1'

Test #23:

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

input:

59 44
25 44
40 32
40 52

output:

1

result:

ok single line: '1'

Test #24:

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

input:

4 4
2 3
4 2
3 2

output:

1

result:

ok single line: '1'