QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #712967 | #5537. Storing Eggs | MeatInTheMiddle | WA | 20ms | 8840kb | C++17 | 4.6kb | 2024-11-05 17:39:45 | 2024-11-05 17:39:55 |
Judging History
answer
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll mod = 1e9 + 7;
const double inf = 50000;
double d[101][1 << 3][101][1 << 3];
double dd[1 << 3] = {inf, inf, inf, 1, inf, 2, 1, 1};
int dp[101][1 << 3];
int n, k;
bool valid(double x) {
for (int i = 0; i <= n; i++)
for (int is = 1; is < (1 << 3); is++) dp[i][is] = 0;
for (int i = 0; i <= n; i++) {
for (int is = 0; is < (1 << 3); is++) {
for (int j = i + 1; j <= n; j++) {
for (int js = 1; js < (1 << 3); js++) {
if (i + 1 == j && i >= 2 && is) {
for (int ks = 1; ks < (1 << 3); ks++) {
double mn = min({d[i][is][j][js], d[i - 1][ks][j][js], d[i - 1][ks][i][is]});
// cout << i << " " << is << " " << j << " " << js << " " << ks << "\n";
// cout << "mn: " << d[i][is][j][js] << " " << d[i - 1][ks][j][js] << " " << d[i - 1][ks][i][is] << " - " << mn << "\n";
if (mn >= x) {
dp[j][js] = max(dp[j][js], dp[i - 1][ks] + __builtin_popcount(is) + __builtin_popcount(js));
// cout << "!!: " << dp[i - 1][ks] << "\n";
// cout << j << " " << js << " is now " << dp[j][js] << "\n";
}
}
} else {
if (d[i][is][j][js] >= x) dp[j][js] = max(dp[j][js], dp[i][is] + __builtin_popcount(js));
}
}
}
}
}
int mx = 0;
for (int i = 0; i <= n; i++)
for (int is = 1; is < (1 << 3); is++) {
mx = max(mx, dp[i][is]);
}
if (mx >= k) return true;
else return false;
}
void solve() {
cin >> n >> k;
vector<string> s(3);
int scnt = 0;
for (auto& si : s) {
cin >> si;
si = '0' + si;
for (auto& sij : si)
if (sij == '#') scnt += 1;
}
if (3 * n - scnt < k) {
cout << "-1\n";
return;
}
for (int j = 1; j <= n; j++)
for (int js = 1; js < (1 << 3); js++) {
bool tmp = false;
for (int jj = 0; jj < 3; jj++) {
if ((js & (1 << jj)) && s[jj][j] == '#') {
d[0][0][j][js] = 0;
tmp = true;
break;
}
}
if (!tmp) d[0][0][j][js] = dd[js];
// cout << 0 << " " << 0 << " " << j << " " << js << " : " << d[0][0][j][js] << "\n";
}
for (int i = 1; i <= n; i++) {
for (int is = 1; is < (1 << 3); is++) {
bool can = true;
for (int ii = 0; ii < 3; ii++) {
if ((is & (1 << ii)) && s[ii][i] == '#') {
can = false;
break;
}
}
if (!can) continue;
for (int j = i + 1; j <= n; j++) {
for (int js = 1; js < (1 << 3); js++) {
bool ccan = true;
for (int jj = 0; jj < 3; jj++) {
if ((js & (1 << jj)) && s[jj][j] == '#') {
ccan = false;
break;
}
}
if (!ccan) continue;
d[i][is][j][js] = dd[js];
for (int ii = 0; ii < 3; ii++) {
if ((is & (1 << ii)) == 0) continue;
for (int jj = 0; jj < 3; jj++) {
if ((js & (1 << jj)) == 0) continue;
d[i][is][j][js] = min(d[i][is][j][js], sqrt(double((i - j) * (i - j) + (ii - jj) * (ii - jj))));
}
}
if (d[i][is][j][js] == inf) d[i][is][j][js] = 0;
// cout << i << " " << is << " " << j << " " << js << " : " << d[i][is][j][js] << "\n";
}
}
}
}
double lo = 0, hi = 1000;
for (int i = 0; i < 60; i++) {
double mid = (lo + hi) / 2;
if (valid(mid)) lo = mid;
else hi = mid;
}
cout << fixed;
cout.precision(8);
cout << hi << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int T = 1;
// cin >> T;
while (T--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4016kb
input:
5 2 #.... ..... ....#
output:
4.47213595
result:
ok found '4.4721360', expected '4.4721360', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
5 6 ##.## ##### .....
output:
1.00000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
3 4 ..# ... ...
output:
1.41421356
result:
ok found '1.4142136', expected '1.4142140', error '0.0000003'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
2 6 .. .# ..
output:
-1
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4044kb
input:
1 2 . . .
output:
2.00000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 12ms
memory: 8780kb
input:
100 2 .................................................................................................... .................................................................................................... ...............................................................................................
output:
99.02019996
result:
ok found '99.0202000', expected '99.0202000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 12ms
memory: 8496kb
input:
100 3 .................................................................................................... .................................................................................................... ...............................................................................................
output:
49.04079934
result:
ok found '49.0407993', expected '49.0407990', error '0.0000000'
Test #8:
score: 0
Accepted
time: 14ms
memory: 8740kb
input:
100 100 .................................................................................................... .................................................................................................... .............................................................................................
output:
2.00000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 16ms
memory: 8180kb
input:
100 150 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.41421356
result:
ok found '1.4142136', expected '1.4142140', error '0.0000003'
Test #10:
score: 0
Accepted
time: 20ms
memory: 8632kb
input:
100 151 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.00000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 20ms
memory: 8644kb
input:
100 200 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.00000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 20ms
memory: 8840kb
input:
100 201 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.00000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #13:
score: 0
Accepted
time: 6ms
memory: 8276kb
input:
60 130 ............................................................ ............................................................ ............................................................
output:
1.00000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #14:
score: 0
Accepted
time: 13ms
memory: 7012kb
input:
100 100 .................................................................................................... #################################################################################################### .............................................................................................
output:
2.00000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #15:
score: 0
Accepted
time: 11ms
memory: 8024kb
input:
100 51 #################################################################################################### .................................................................................................... ###########################################################################################...
output:
1.00000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
1 2 # # #
output:
-1
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #17:
score: 0
Accepted
time: 7ms
memory: 6216kb
input:
99 50 ################################################################################################### ................................................................................................... ##############################################################################################...
output:
2.00000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #18:
score: 0
Accepted
time: 8ms
memory: 6684kb
input:
100 47 #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#. .#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...
output:
2.82842712
result:
ok found '2.8284271', expected '2.8284270', error '0.0000000'
Test #19:
score: 0
Accepted
time: 13ms
memory: 8092kb
input:
100 43 .#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#. .#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#....
output:
2.82842712
result:
ok found '2.8284271', expected '2.8284270', error '0.0000000'
Test #20:
score: 0
Accepted
time: 13ms
memory: 7952kb
input:
99 2 #........#............#.#.#...................................#................##..............#... ............................##...#......#...##.............#.........#..#...#............#...#..... #...............................................#..............#.....#.........#.........#........
output:
98.00510191
result:
ok found '98.0051019', expected '98.0051020', error '0.0000000'
Test #21:
score: 0
Accepted
time: 8ms
memory: 6072kb
input:
90 2 #############..######.###.##.#########.###.###########.####.############################## #...##########.#.#################.############.########################.################# ###################.###.##.####.#######..##.########.#############################.#######
output:
81.00617260
result:
ok found '81.0061726', expected '81.0061730', error '0.0000000'
Test #22:
score: 0
Accepted
time: 9ms
memory: 7664kb
input:
95 3 #.#..............#.............#.......#..##.....#.#............#....#..................##..... .....#.#........#...#...........#......................#...#.....#.........#.....#...........#. #.......#.#....#.......#.......#.......#..#.#.#.#....#.#...#..#......#........#..........#....#
output:
47.01063709
result:
ok found '47.0106371', expected '47.0106370', error '0.0000000'
Test #23:
score: 0
Accepted
time: 9ms
memory: 5952kb
input:
92 3 #########################.###########################.####################################.# #######.##############.#.#################.#########.########.#############################. ###.##.####.###.####.#####.########.#########.########.##.#######.##########################
output:
42.00000000
result:
ok found '42.0000000', expected '42.0000000', error '0.0000000'
Test #24:
score: 0
Accepted
time: 6ms
memory: 7624kb
input:
93 4 ##..#.......................#.....#.#.#..............#.....#........#.....................#.. ......#...................#..##...................#...............###.....#....#..........#.# #......#.........#....#.................#......#...#......##..........#.........#.#..#.#..#.#
output:
30.06659276
result:
ok found '30.0665928', expected '30.0665930', error '0.0000000'
Test #25:
score: 0
Accepted
time: 8ms
memory: 6140kb
input:
92 4 ###.###############.######.##.#########################.######.###.#####.################### #.##..#####################.###########################.########..###############.#######... #######################.###.############.##..####.#################.#.#..####.##############
output:
28.01785145
result:
ok found '28.0178514', expected '28.0178510', error '0.0000000'
Test #26:
score: 0
Accepted
time: 8ms
memory: 7836kb
input:
94 5 #........#....#.................................................#.....................#....... #................#...............#..##..................#........#.......#...#................ ##..................................................##................#.......#...............
output:
23.02172887
result:
ok found '23.0217289', expected '23.0217290', error '0.0000000'
Test #27:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
1 2 # . .
output:
1.00000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #28:
score: 0
Accepted
time: 9ms
memory: 5956kb
input:
94 5 ##..#.######.##.########.#####.#####.############..##.##############################..######## #######.########.##########.#..################.####.#.###...######..##.###################### ######.############.######.#####################.################.##.##############.##########
output:
18.02775638
result:
ok found '18.0277564', expected '18.0277560', error '0.0000000'
Test #29:
score: 0
Accepted
time: 8ms
memory: 8596kb
input:
90 6 #.................#....................#................#.#.........###................... ....................................#........#...................#...##...##....#.....#... #.#...........#...#........#..#....#.#....................#.........#.....................
output:
17.11724277
result:
ok found '17.1172428', expected '17.1172430', error '0.0000000'
Test #30:
score: 0
Accepted
time: 8ms
memory: 8048kb
input:
100 6 ##########.##.##################.###########.###########.##.######################.####.##.######### ##########...#########.#.########.#################.#.###########.#.##########.#.##.################ ##############.#####..#######..##################.#######################.########.#########...
output:
16.03121954
result:
ok found '16.0312195', expected '16.0312200', error '0.0000000'
Test #31:
score: 0
Accepted
time: 8ms
memory: 8296kb
input:
92 7 #.#....#..#...#.......#.........................................#.......#...#.............#. ...............#......#............#...#.........................#.....#..............#..... #..#......#...............#.................#....#............................#.............
output:
15.13274595
result:
ok found '15.1327460', expected '15.1327460', error '0.0000000'
Test #32:
score: 0
Accepted
time: 3ms
memory: 7956kb
input:
92 7 ##.###########..######.###############.#.##.#################.##.#############.######.###.## #############.###############.##..#####################.######.#..#########.###.############ .###.########.###################.########.###################..#######...#########.#####.##
output:
14.03566885
result:
ok found '14.0356689', expected '14.0356690', error '0.0000000'
Test #33:
score: 0
Accepted
time: 7ms
memory: 8272kb
input:
91 8 #..................#..#..............#......................#.......#..........#...#..#.... #....#.#.....#..#......#.....#.................#..#...........................#.........#.. #.......#......#..........#............#.....#...................#..............#.....#....
output:
12.16552506
result:
ok found '12.1655251', expected '12.1655250', error '0.0000000'
Test #34:
score: 0
Accepted
time: 8ms
memory: 5956kb
input:
93 8 ############.###########.#######################.############.##.###.######################.# ############.####.###########.#######.####.##########.#######.####.###################.####.. #####.#######.###########.#####.#############.#.##################.##########################
output:
8.06225775
result:
ok found '8.0622578', expected '8.0622580', error '0.0000000'
Test #35:
score: 0
Accepted
time: 15ms
memory: 7876kb
input:
100 109 ..#.....#..............#....................#..#.......#.............#................#.#........... #............##.........#..........#.#....#...............#...#.......#................#...........# .....#..#......#................................................................#............
output:
1.41421356
result:
ok found '1.4142136', expected '1.4142140', error '0.0000003'
Test #36:
score: 0
Accepted
time: 12ms
memory: 7696kb
input:
97 13 ..##...#..........#.........##....##......#............#..........###........#.....#.........#... ##..#....#.............#....#...#.##............#........#.#.#.....................#.......#..#.. ........#..#....##.........#.#....#.....#.......#.#...................#......#.......#......##...
output:
8.06225775
result:
ok found '8.0622578', expected '8.0622580', error '0.0000000'
Test #37:
score: 0
Accepted
time: 10ms
memory: 8520kb
input:
100 50 ....#......#..................#.......#..#.....#........#.........#......#....#............##....... #.....##........#.#...........##..#....##....#.#.........##....#.##...........#..................... ......##........#...#....#...#...#............#.......##.#..........##......##....##..#...#...
output:
2.23606798
result:
ok found '2.2360680', expected '2.2360680', error '0.0000000'
Test #38:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
1 3 # . .
output:
-1
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #39:
score: 0
Accepted
time: 8ms
memory: 8300kb
input:
92 107 ..#........#...#...#.....#....#........#...#.......#.........#..#.........#...##.......##.#. ..##.......#..#....##.#..##.#.##........#............#..#.......#..##..............#....#... #...#.....#..........#........#.....##.#.................#....##...........#............#...
output:
1.41421356
result:
ok found '1.4142136', expected '1.4142140', error '0.0000003'
Test #40:
score: 0
Accepted
time: 14ms
memory: 8420kb
input:
95 125 ...##.......#..#.#.............#..##...#..................#......#...##..#.....##....#.......#. .........#.....#.#....#....#..##.....#...#...#......#...........##..#........#.#...#.#........# .#..#....................##.........#...#...........#...........#...#...#..........##.....#.##.
output:
1.00000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #41:
score: 0
Accepted
time: 6ms
memory: 6836kb
input:
93 20 ############################################################################################# .#.....#.......###.#..#.###....#...............##...#.....#..#...#...........#.....#....#..#. ....##.....#....#.#......#......#...........#.....#................#......#...#.##........#..
output:
4.12310563
result:
ok found '4.1231056', expected '4.1231060', error '0.0000001'
Test #42:
score: 0
Accepted
time: 10ms
memory: 8056kb
input:
97 21 ################################################################################################# ################################################################################################# ......###........#.....#...#.#.........##.#......#.####.##......#....#........#...##....#......#.
output:
4.00000000
result:
ok found '4.0000000', expected '4.0000000', error '0.0000000'
Test #43:
score: 0
Accepted
time: 6ms
memory: 6844kb
input:
93 7 #...#..##..#..#....#...#......#...####.###..##.##.#..#.#.###.##......#..###....#.#..#.#.#...# .#.#....##..##.##.#...##..##.#..............####.....##.#.#.#.#.#..##....#...#.#.#.......#... ###.###......#.#.#.#...###....#.#.##..#..#...#...#.##.#..##...#.####.#..##.#.###....#.#...#.#
output:
15.13274595
result:
ok found '15.1327460', expected '15.1327460', error '0.0000000'
Test #44:
score: 0
Accepted
time: 6ms
memory: 6592kb
input:
91 15 .##.#..#......#.#####..###....##..#.#...#..##..#.##.....#....#.######.#.#.#......##..##..#. ..#..########....#..#...#.###.#............#.#.#..#..#..#.#.##...##....###.#...#.###..####. ...#.##..####..#.#.#.....#.#..#.#...##.##.#....#....#..#..##.......#####..###.#.#.#.##...#.
output:
6.32455532
result:
ok found '6.3245553', expected '6.3245550', error '0.0000001'
Test #45:
score: -100
Wrong Answer
time: 11ms
memory: 6984kb
input:
98 58 .#..##.....#............###.#####.##.....#.#..#.#.....####..##.##.#.......##...##..#..#....#..#..# #.#.##.#.#...#.....###...#....##..#..#...#####.##.#.#..#.#.##.#...####.##.#.....###.##.###.#....#. ....#..##..##.##..##...#..#....#.......###...#....#.##..#...#..#.....#....#.#.......####.#.#..#.#.
output:
2.00000000
result:
wrong answer 1st numbers differ - expected: '2.2360680', found: '2.0000000', error = '0.1055728'