QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#722010#5537. Storing Eggswjt#WA 134ms3944kbC++141.5kb2024-11-07 17:26:562024-11-07 17:26:57

Judging History

This is the latest submission verdict.

  • [2024-11-07 17:26:57]
  • Judged
  • Verdict: WA
  • Time: 134ms
  • Memory: 3944kb
  • [2024-11-07 17:26:56]
  • 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*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;
	}
	double l = 1.0, r = sqrt((n-1) * (n-1) + 4.0);
	double ans = 1.0;
	while (r - l > eps) {
		double mid = (l + r) / 2.0;
		if (Check(mid)) {
			ans = mid;
			l = mid;
		}
		else {
			r = mid;
		}
	}
	cout << fixed << setprecision(10) << ans << endl;
	return 0;
}

詳細信息

Test #1:

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

input:

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

output:

4.4721359485

result:

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

Test #2:

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

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

input:

3 4
..#
...
...

output:

1.4142135619

result:

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

Test #4:

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

input:

2 6
..
.#
..

output:

-1

result:

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

Test #5:

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

input:

1 2
.
.
.

output:

1.9999999925

result:

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

Test #6:

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

input:

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

output:

99.0201999537

result:

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

Test #7:

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

input:

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

output:

49.0407993405

result:

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

Test #8:

score: 0
Accepted
time: 49ms
memory: 3900kb

input:

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

output:

1.9999999951

result:

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

Test #9:

score: 0
Accepted
time: 66ms
memory: 3944kb

input:

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

output:

1.4142135602

result:

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

Test #10:

score: 0
Accepted
time: 111ms
memory: 3900kb

input:

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

output:

1.0000000000

result:

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

Test #11:

score: 0
Accepted
time: 111ms
memory: 3932kb

input:

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

output:

1.0000000000

result:

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

Test #12:

score: 0
Accepted
time: 111ms
memory: 3744kb

input:

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

output:

1.0000000000

result:

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

Test #13:

score: 0
Accepted
time: 26ms
memory: 3756kb

input:

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

output:

1.0000000000

result:

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

Test #14:

score: 0
Accepted
time: 67ms
memory: 3844kb

input:

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

output:

1.9999999951

result:

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

Test #15:

score: 0
Accepted
time: 134ms
memory: 3888kb

input:

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

output:

1.0000000000

result:

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

Test #16:

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

input:

1 2
#
#
#

output:

-1

result:

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

Test #17:

score: 0
Accepted
time: 54ms
memory: 3880kb

input:

99 50
###################################################################################################
...................................................................................................
##############################################################################################...

output:

1.9999999947

result:

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

Test #18:

score: -100
Wrong Answer
time: 60ms
memory: 3832kb

input:

100 47
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...

output:

1.9999999951

result:

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