QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#234693#5537. Storing Eggsdmmm#WA 7ms3764kbC++141.9kb2023-11-01 20:54:112023-11-01 20:54:12

Judging History

This is the latest submission verdict.

  • [2023-11-01 20:54:12]
  • Judged
  • Verdict: WA
  • Time: 7ms
  • Memory: 3764kb
  • [2023-11-01 20:54:11]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e9;
const int maxN = 1e2 + 6.9;
int n, k;
char a[4][maxN];
bool ok(int i, int j, int j2, int d2) {
	if (j == 3 && j2 == 3) return i * i >= d2 && 4 >= d2;
	if (j < 3 && j2 < 3) return i * i + (j - j2) * (j - j2) >= d2;
	if (j < 3) swap(j, j2);
	int dj = min(j2, 3 - j2);
	return i * i + dj * dj >= d2;
}
bool check(int d2) {
	vector<vector<int>> dp(n + 1, vector<int>(4, 0));
	for (int i = 1; i <= n; i++)
	for (int j = 0; j < 5; j++) {
		if (j < 3 && a[j][i] == '#') continue;
		if (j == 3 && (a[0][i] == '#' || a[2][i] == '#' || d2 > 4)) continue;
		int num = j == 3 ? 2 : 1;
		dp[i][j] = num;

		for (int i2 = i - 1; i2 >= 0; i2--)
		for (int j2 = 0; j2 < 4; j2++) {
			if (d2 == 5) {
				if (i2 == i - 1) continue;
				if (!ok(i - i2, j, j2, d2)) continue;
				int good = 0;
				for (int j3 = 0; j3 < 3; j3++)
				if (ok(1, j, j3, d2) && ok(i - 1 - i2, j2, j3, d2) && a[j3][i - 1] == '.') good = 1;
				dp[i][j] = max(dp[i][j], dp[i2][j2] + num + good);
			}
			else if (ok(i - i2, j, j2, d2)) {
				if (dp[i2][j2] + num > dp[i][j])
					dp[i][j] = dp[i2][j2] + num;
			}
		}
		
		if (dp[i][j] >= k) return 1;
	}
	// for (int j = 0; j < 4; j++) {
	// 	for (int i = 1; i <= n; i++) cout << dp[i][j] << ' ';
	// 	cout << '\n';
	// }
	return 0;
}
int bin(int l, int r) {
	while (l < r) {
		int mid = (r - l) / 2 + l + 1;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	return l;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> k;
	int num = 0;
	for (int i = 0; i < 3; i++) {
		string s;
		cin >> s;
		for (int j = 1; j <= n; j++) {
			a[i][j] = s[j - 1];
			if (s[j - 1] == '.') num++;
		}
	}

	if (num < k) return cout << -1, 0;
	double ans = 1;
	// cout << check(21);
	int res = bin(2, INF);
	if (check(res)) ans = sqrt(res);
	cout << fixed << setprecision(7) << ans;
}

详细

Test #1:

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

input:

5 2
#....
.....
....#

output:

4.4721360

result:

ok found '4.4721360', expected '4.4721360', error '0.0000000'

Test #2:

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

input:

5 6
##.##
#####
.....

output:

1.0000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #3:

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

input:

3 4
..#
...
...

output:

1.4142136

result:

ok found '1.4142136', expected '1.4142140', error '0.0000003'

Test #4:

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

input:

2 6
..
.#
..

output:

-1

result:

ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'

Test #5:

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

input:

1 2
.
.
.

output:

2.0000000

result:

ok found '2.0000000', expected '2.0000000', error '0.0000000'

Test #6:

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

input:

100 2
....................................................................................................
....................................................................................................
...............................................................................................

output:

99.0202000

result:

ok found '99.0202000', expected '99.0202000', error '0.0000000'

Test #7:

score: 0
Accepted
time: 6ms
memory: 3764kb

input:

100 3
....................................................................................................
....................................................................................................
...............................................................................................

output:

49.0407993

result:

ok found '49.0407993', expected '49.0407990', error '0.0000000'

Test #8:

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

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

2.0000000

result:

ok found '2.0000000', expected '2.0000000', error '0.0000000'

Test #9:

score: 0
Accepted
time: 6ms
memory: 3760kb

input:

100 150
....................................................................................................
....................................................................................................
.............................................................................................

output:

1.4142136

result:

ok found '1.4142136', expected '1.4142140', error '0.0000003'

Test #10:

score: 0
Accepted
time: 6ms
memory: 3592kb

input:

100 151
....................................................................................................
....................................................................................................
.............................................................................................

output:

1.0000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #11:

score: 0
Accepted
time: 6ms
memory: 3676kb

input:

100 200
....................................................................................................
....................................................................................................
.............................................................................................

output:

1.0000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #12:

score: 0
Accepted
time: 7ms
memory: 3636kb

input:

100 201
....................................................................................................
....................................................................................................
.............................................................................................

output:

1.0000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #13:

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

input:

60 130
............................................................
............................................................
............................................................

output:

1.0000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #14:

score: 0
Accepted
time: 2ms
memory: 3708kb

input:

100 100
....................................................................................................
####################################################################################################
.............................................................................................

output:

2.0000000

result:

ok found '2.0000000', expected '2.0000000', error '0.0000000'

Test #15:

score: -100
Wrong Answer
time: 3ms
memory: 3624kb

input:

100 51
####################################################################################################
....................................................................................................
###########################################################################################...

output:

1.4142136

result:

wrong answer 1st numbers differ - expected: '1.0000000', found: '1.4142136', error = '0.4142136'