QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #713866 | #5537. Storing Eggs | MeatInTheMiddle | WA | 107ms | 8780kb | C++17 | 4.9kb | 2024-11-05 20:45:08 | 2024-11-05 20:45:08 |
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;
vector<string> s(3);
bool valid(double x) {
for (int i = 1; i <= n; i++)
for (int is = 1; is < (1 << 3); is++) dp[i][is] = (dd[is] >= x ? __builtin_popcount(is) : 0);
for (int i = 0; i <= n; i++) {
for (int is = 0; 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 + 2; 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 (s[0][j] == '#' && s[1][j] == '#' && s[2][j] == '#') ccan = false;
if (!ccan) continue;
if (d[i][is][j][js] >= x) {
dp[j][js] = max(dp[j][js], dp[i][is] + __builtin_popcount(js));
for (int ks = 1; ks < (1 << 3); ks++) {
if (min(d[j - 1][ks][j][js], d[i][is][j - 1][ks]) >= x) {
dp[j][js] = max(dp[j][js], dp[i][is] + __builtin_popcount(js) + __builtin_popcount(ks));
}
}
}
}
}
}
}
int mx = 0;
for (int i = 0; i <= n; i++)
for (int is = 1; is < (1 << 3); is++) {
mx = max(mx, dp[i][is]);
// cout << "dp: " << i << " " << is << " - " << dp[i][is] << "\n";
}
// cout << "x: " << x << " mx: " << mx << "\n";
if (mx >= k) return true;
else return false;
}
void solve() {
cin >> n >> k;
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";
}
}
}
}
// valid(1.414);
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3868kb
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: 3948kb
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: 3884kb
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: 3604kb
input:
2 6 .. .# ..
output:
-1
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3984kb
input:
1 2 . . .
output:
2.00000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 37ms
memory: 8280kb
input:
100 2 .................................................................................................... .................................................................................................... ...............................................................................................
output:
99.02019996
result:
ok found '99.0202000', expected '99.0202000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 47ms
memory: 8228kb
input:
100 3 .................................................................................................... .................................................................................................... ...............................................................................................
output:
49.04079934
result:
ok found '49.0407993', expected '49.0407990', error '0.0000000'
Test #8:
score: 0
Accepted
time: 74ms
memory: 8672kb
input:
100 100 .................................................................................................... .................................................................................................... .............................................................................................
output:
2.00000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 81ms
memory: 8508kb
input:
100 150 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.41421356
result:
ok found '1.4142136', expected '1.4142140', error '0.0000003'
Test #10:
score: 0
Accepted
time: 105ms
memory: 8780kb
input:
100 151 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.00000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 107ms
memory: 8624kb
input:
100 200 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.00000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 106ms
memory: 8592kb
input:
100 201 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.00000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #13:
score: 0
Accepted
time: 38ms
memory: 7976kb
input:
60 130 ............................................................ ............................................................ ............................................................
output:
1.00000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #14:
score: 0
Accepted
time: 30ms
memory: 8392kb
input:
100 100 .................................................................................................... #################################################################################################### .............................................................................................
output:
2.00000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #15:
score: 0
Accepted
time: 7ms
memory: 6240kb
input:
100 51 #################################################################################################### .................................................................................................... ###########################################################################################...
output:
1.00000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
1 2 # # #
output:
-1
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #17:
score: 0
Accepted
time: 6ms
memory: 6348kb
input:
99 50 ################################################################################################### ................................................................................................... ##############################################################################################...
output:
2.00000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #18:
score: 0
Accepted
time: 18ms
memory: 8052kb
input:
100 47 #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#. .#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...
output:
2.82842712
result:
ok found '2.8284271', expected '2.8284270', error '0.0000000'
Test #19:
score: 0
Accepted
time: 19ms
memory: 6768kb
input:
100 43 .#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#. .#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#....
output:
2.82842712
result:
ok found '2.8284271', expected '2.8284270', error '0.0000000'
Test #20:
score: 0
Accepted
time: 33ms
memory: 8132kb
input:
99 2 #........#............#.#.#...................................#................##..............#... ............................##...#......#...##.............#.........#..#...#............#...#..... #...............................................#..............#.....#.........#.........#........
output:
98.00510191
result:
ok found '98.0051019', expected '98.0051020', error '0.0000000'
Test #21:
score: 0
Accepted
time: 5ms
memory: 5940kb
input:
90 2 #############..######.###.##.#########.###.###########.####.############################## #...##########.#.#################.############.########################.################# ###################.###.##.####.#######..##.########.#############################.#######
output:
81.00617260
result:
ok found '81.0061726', expected '81.0061730', error '0.0000000'
Test #22:
score: 0
Accepted
time: 32ms
memory: 7592kb
input:
95 3 #.#..............#.............#.......#..##.....#.#............#....#..................##..... .....#.#........#...#...........#......................#...#.....#.........#.....#...........#. #.......#.#....#.......#.......#.......#..#.#.#.#....#.#...#..#......#........#..........#....#
output:
47.01063709
result:
ok found '47.0106371', expected '47.0106370', error '0.0000000'
Test #23:
score: 0
Accepted
time: 5ms
memory: 8064kb
input:
92 3 #########################.###########################.####################################.# #######.##############.#.#################.#########.########.#############################. ###.##.####.###.####.#####.########.#########.########.##.#######.##########################
output:
42.00000000
result:
ok found '42.0000000', expected '42.0000000', error '0.0000000'
Test #24:
score: 0
Accepted
time: 36ms
memory: 8592kb
input:
93 4 ##..#.......................#.....#.#.#..............#.....#........#.....................#.. ......#...................#..##...................#...............###.....#....#..........#.# #......#.........#....#.................#......#...#......##..........#.........#.#..#.#..#.#
output:
30.06659276
result:
ok found '30.0665928', expected '30.0665930', error '0.0000000'
Test #25:
score: 0
Accepted
time: 3ms
memory: 7972kb
input:
92 4 ###.###############.######.##.#########################.######.###.#####.################### #.##..#####################.###########################.########..###############.#######... #######################.###.############.##..####.#################.#.#..####.##############
output:
28.01785145
result:
ok found '28.0178514', expected '28.0178510', error '0.0000000'
Test #26:
score: 0
Accepted
time: 47ms
memory: 7712kb
input:
94 5 #........#....#.................................................#.....................#....... #................#...............#..##..................#........#.......#...#................ ##..................................................##................#.......#...............
output:
23.02172887
result:
ok found '23.0217289', expected '23.0217290', error '0.0000000'
Test #27:
score: -100
Wrong Answer
time: 0ms
memory: 3824kb
input:
1 2 # . .
output:
2.00000000
result:
wrong answer 1st numbers differ - expected: '1.0000000', found: '2.0000000', error = '1.0000000'