QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#182598#6565. Game Show EliminationGeZhiyuanAC ✓276ms89632kbC++145.2kb2023-09-18 10:24:592023-09-18 10:24:59

Judging History

你现在查看的是最新测评结果

  • [2023-09-18 10:24:59]
  • 评测
  • 测评结果:AC
  • 用时:276ms
  • 内存:89632kb
  • [2023-09-18 10:24:59]
  • 提交

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