QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#722025#5537. Storing EggswjtWA 22ms3920kbC++141.5kb2024-11-07 17:29:162024-11-07 17:29:16

Judging History

This is the latest submission verdict.

  • [2024-11-07 17:29:16]
  • Judged
  • Verdict: WA
  • Time: 22ms
  • Memory: 3920kb
  • [2024-11-07 17:29:16]
  • Submitted

answer

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <iomanip>
using namespace std;
const int N = 105;
const double eps = 1e-8;
int n, k;
char c[5][N];
bool p[5][N];

bool is_ok(int x, int y, double num) {
	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= n; j++) {
			if (!p[i][j] || c[i][j] == '#') continue;
			if ( (x - i) * (x - i) + (y - j) * (y - j) < num ) return 0;
		}
	}
	return 1;
}

bool check(int s, double num, int d) {
	for (int i = s; i <= n; i += d) {
		p[1][i] = 1;
	}
	for (int i = 2; i <= 3; i++) {
		for (int j = 1; j <= n; j++) {
			if (is_ok(i, j, num)) {
				p[i][j] = 1;
			}
		}
	}
	int cnt = 0;
	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= n; j++) {
			if (p[i][j] && c[i][j] == '.') {
				++cnt;
			}
		}
	}
	return (cnt >= k);
}

bool Check(double num) {
	int d = int(ceil(num));
	for (int i = 1; i <= n; i++) {
		memset(p, 0, sizeof(p));
		if (check(i, num, d)) return 1;
	}
	return 0;
}

int main() {
	cin >> n >> k;
	int tot = 0;
	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> c[i][j];
			if (c[i][j] == '.') ++tot;
		}
	}
	if (tot < k) {
		cout << -1 << endl;
		return 0;
	}
	int l = 1.0, r = (n-1) * (n-1) + 4.0;
	double ans = 1.0;
	while ( l <= r) {
		int mid = (l + r) / 2.0;
		if (Check(mid)) {
			ans = sqrt(mid);
			l = mid+1;
		}
		else {
			r = mid-1;
		}
	}
	cout << fixed << setprecision(10) << ans << endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3920kb

input:

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

output:

4.4721359550

result:

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

Test #2:

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

input:

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

output:

1.0000000000

result:

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

Test #3:

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

input:

3 4
..#
...
...

output:

1.4142135624

result:

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

Test #4:

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

input:

2 6
..
.#
..

output:

-1

result:

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

Test #5:

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

input:

1 2
.
.
.

output:

2.0000000000

result:

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

Test #6:

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

input:

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

output:

99.0201999594

result:

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

Test #7:

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

input:

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

output:

49.0407993410

result:

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

Test #8:

score: -100
Wrong Answer
time: 22ms
memory: 3828kb

input:

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

output:

1.4142135624

result:

wrong answer 1st numbers differ - expected: '2.0000000', found: '1.4142136', error = '0.2928932'