QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#722025 | #5537. Storing Eggs | wjt | WA | 22ms | 3920kb | C++14 | 1.5kb | 2024-11-07 17:29:16 | 2024-11-07 17:29:16 |
Judging History
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;
}
詳細信息
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'