QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#182598 | #6565. Game Show Elimination | GeZhiyuan | AC ✓ | 276ms | 89632kb | C++14 | 5.2kb | 2023-09-18 10:24:59 | 2023-09-18 10:24:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 1000 + 5, S = (1 << 10) + 5, M = 10 + 5;
int n = 0, m = 0, lg[S] = {};
double dp[M][M][3] = {}, dpx[M][M] = {}, p[M][S][M] = {}, q[S][M] = {}, f[N][M][S] = {}, g[N][S] = {}, ans[N] = {};
int tot = 0, a[M << 1] = {};
inline int cross(int l1, int r1, int l2, int r2){
return max(0, min(r1, r2) - max(l1, l2));
}
inline double work(int d, int s, int k, int Lx, int Rx){
memset(dp, 0, sizeof(dp));
int las = m + 1;
double ret = 0, ex = 0;
dp[las][0][0] = 1.00;
for(int i = 0 ; i < m ; i ++) if((s >> i) & 1){
int l = -(d + i), r = l + m;
if(k == i) ex = 1.00 * cross(l, r, Lx, Rx) / m;
else{
double p1 = 1.00 * cross(l, r, l, Lx) / m, p2 = 1.00 * cross(l, r, Lx, Rx) / m, p3 = 1.00 * cross(l, r, Rx, r) / m;
for(int x = 0 ; x <= m ; x ++) for(int op = 0 ; op <= 1 ; op ++){
dp[i][x][op] += dp[las][x][op] * p1;
dp[i][x + 1][op] += dp[las][x][op] * p2;
dp[i][x][op + 1] += dp[las][x][op] * p3;
}
las = i;
}
}
int l = 0, r = m;
if(k == m) ex = 1.00 * cross(l, r, Lx, Rx) / m;
else{
double p1 = 1.00 * cross(l, r, l, Lx) / m, p2 = 1.00 * cross(l, r, Lx, Rx) / m, p3 = 1.00 * cross(l, r, Rx, r) / m;
for(int x = 0 ; x <= m ; x ++) for(int op = 0 ; op <= 1 ; op ++){
dp[m][x][op] += dp[las][x][op] * p1;
dp[m][x + 1][op] += dp[las][x][op] * p2;
dp[m][x][op + 1] += dp[las][x][op] * p3;
}
las = m;
}
for(int x = 0 ; x <= m ; x ++) for(int op = 0 ; op <= 1 ; op ++) if(x || op) ret += dp[las][x][op] / (x + 1);
return ret * ex;
}
inline double solve(int d, int s, int k){
tot = 0;
memset(a, 0, sizeof(a));
for(int i = 0 ; i < m ; i ++) if((s >> i) & 1){
int l = -(d + i), r = l + m;
a[tot ++] = l, a[tot ++] = r;
}
int l = 0, r = m;
a[tot ++] = l, a[tot ++] = r;
sort(a, a + tot); tot = unique(a, a + tot) - a;
double ret = 0;
for(int i = 1 ; i < tot ; i ++) ret += work(d, s, k, a[i - 1], a[i]);
return ret;
}
inline double workx(int s, int k, int Lx, int Rx){
memset(dpx, 0, sizeof(dpx));
int las = m;
double ret = 0, ex = 0;
dpx[las][0] = 1.00;
for(int i = 0 ; i < m ; i ++) if((s >> i) & 1){
int l = -i, r = l + m;
if(k == i) ex = 1.00 * cross(l, r, Lx, Rx) / m;
else{
double p1 = 1.00 * cross(l, r, l, Lx) / m, p2 = 1.00 * cross(l, r, Lx, Rx) / m;
for(int x = 0 ; x <= m ; x ++){
dpx[i][x] += dpx[las][x] * p1;
dpx[i][x + 1] += dpx[las][x] * p2;
}
las = i;
}
}
for(int x = 0 ; x <= m ; x ++) ret += dpx[las][x] / (x + 1);
return ret * ex;
}
inline double solvex(int s, int k){
tot = 0;
memset(a, 0, sizeof(a));
for(int i = 0 ; i < m ; i ++) if((s >> i) & 1){
int l = -i, r = l + m;
a[tot ++] = l, a[tot ++] = r;
}
sort(a, a + tot); tot = unique(a, a + tot) - a;
double ret = 0;
for(int i = 1 ; i < tot ; i ++) ret += workx(s, k, a[i - 1], a[i]);
return ret;
}
inline int lowbit(int x){
if(x) return x & -x;
else return 1 << m;
}
inline int bits(int l, int r){
if(l < r) return (1 << r) - (1 << l);
else return 0;
}
inline int popcnt(int x){
return __builtin_popcount(x);
}
int main(){
scanf("%d %d", &n, &m);
for(int i = 0 ; i <= m ; i ++) lg[1 << i] = i;
for(int d = 1 ; d < m ; d ++) for(int s = 1 ; s < (1 << m) ; s ++) if(s & 1){
for(int i = 0 ; i < m ; i ++) if((s >> i) & 1) p[d][s][i] = solve(d, s, i);
p[d][s][m] = solve(d, s, m);
}
f[n][1][bits(0, min(m, n - 1))] = 1;
for(int h = n ; h >= 1 ; h --) for(int d = 1 ; d < m ; d ++) for(int s = (1 << m) - 1 ; s > 0 ; s --) if(s & 1) if(f[h][d][s]){
int rk = max(h - d - m, 0) + popcnt(s) + 1;
for(int i = 0 ; i < m ; i ++) if((s >> i) & 1){
if(i){
f[h][d][s - (1 << i)] += f[h][d][s] * p[d][s][i];
ans[h - d - i] += f[h][d][s] * p[d][s][i] * rk;
}
else{
int sh = lg[lowbit(s - 1)], dx = sh + d, t = (s >> sh) + bits(m - sh, min(m, h - dx));
if(dx < m){
f[h][dx][t] += f[h][d][s] * p[d][s][i];
ans[h - d] += f[h][d][s] * p[d][s][i] * rk;
}
else{
if(t) g[h - dx][t] += f[h][d][s] * p[d][s][i];
ans[h - d] += f[h][d][s] * p[d][s][i] * rk, ans[h] += f[h][d][s] * p[d][s][i];
}
}
}
int dx = lg[lowbit(s - 1)];
if(dx < m){
int t = (s >> dx) + bits(m - dx, min(m, h - d - dx));
f[h - d][dx][t] += f[h][d][s] * p[d][s][m];
}
else{
ans[h - d] += f[h][d][s] * p[d][s][m];
if(h - d - m > 0) g[h - d - m][bits(0, min(h - d - m, m))] += f[h][d][s] * p[d][s][m];
}
ans[h] += f[h][d][s] * p[d][s][m] * rk;
}
for(int s = 1 ; s < (1 << m) ; s ++) if(s & 1) for(int i = 0 ; i < m ; i ++) if((s >> i) & 1) q[s][i] = solvex(s, i);
for(int h = n ; h >= 1 ; h --) for(int s = (1 << m) - 1 ; s > 0 ; s --) if(s & 1){
int rk = max(h - m, 0) + popcnt(s) + 1;
for(int i = 0 ; i < m ; i ++) if((s >> i) & 1) if(g[h][s]){
if(i){
g[h][s - (1 << i)] += g[h][s] * q[s][i];
ans[h - i] += g[h][s] * q[s][i] * rk;
}
else{
int d = lg[lowbit(s - 1)], t = (s >> d) + bits(m - d, min(m, h - d));
if(t) g[h - d][t] += g[h][s] * q[s][i];
ans[h] += g[h][s] * q[s][i] * rk;
}
}
}
for(int i = 1 ; i <= n ; i ++) printf("%.6lf\n", ans[i]);
return 0;
}
/*
3 2
2.109375
2.625000
1.265625
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 8012kb
input:
3 2
output:
2.109375 2.625000 1.265625
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 276ms
memory: 89632kb
input:
1000 10
output:
2.927293 3.537316 4.281182 5.131221 6.053933 7.019189 8.005702 9.001291 10.000165 11.000000 12.000000 13.000000 14.000000 15.000000 16.000000 17.000000 18.000000 19.000000 20.000000 21.000000 22.000000 23.000000 24.000000 25.000000 26.000000 27.000000 28.000000 29.000000 30.000000 31.000000 32.00000...
result:
ok 1000 numbers
Test #3:
score: 0
Accepted
time: 15ms
memory: 21320kb
input:
300 8
output:
2.751263 3.390074 4.175007 5.066022 6.020147 7.004558 8.000573 9.000000 10.000000 11.000000 12.000000 13.000000 14.000000 15.000000 16.000000 17.000000 18.000000 19.000000 20.000000 21.000000 22.000000 23.000000 24.000000 25.000000 26.000000 27.000000 28.000000 29.000000 30.000000 31.000000 32.00000...
result:
ok 300 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 15196kb
input:
1000 3
output:
2.230256 3.034766 4.000000 5.000000 6.000000 7.000000 8.000000 9.000000 10.000000 11.000000 12.000000 13.000000 14.000000 15.000000 16.000000 17.000000 18.000000 19.000000 20.000000 21.000000 22.000000 23.000000 24.000000 25.000000 26.000000 27.000000 28.000000 29.000000 30.000000 31.000000 32.00000...
result:
ok 1000 numbers
Test #5:
score: 0
Accepted
time: 73ms
memory: 8620kb
input:
7 10
output:
2.981586 3.493605 3.965342 4.319677 4.508725 4.498881 4.232184
result:
ok 7 numbers
Test #6:
score: 0
Accepted
time: 92ms
memory: 77092kb
input:
993 9
output:
2.841121 3.464359 4.227324 5.096943 6.035282 7.010574 8.002387 9.000303 10.000000 11.000000 12.000000 13.000000 14.000000 15.000000 16.000000 17.000000 18.000000 19.000000 20.000000 21.000000 22.000000 23.000000 24.000000 25.000000 26.000000 27.000000 28.000000 29.000000 30.000000 31.000000 32.00000...
result:
ok 993 numbers