QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122127#6565. Game Show EliminationtacorefAC ✓805ms48884kbC++145.1kb2023-07-09 15:13:122023-07-09 15:13:15

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-09 15:13:15]
  • 评测
  • 测评结果:AC
  • 用时:805ms
  • 内存:48884kb
  • [2023-07-09 15:13:12]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<int, 2>;

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define rng(i, b, e) for (int i = (b); i <= (e); i++)
#define rep(i, k) rng(i, 0, k - 1)
#define gnr(i, e, b) for (int i = (e); i >= (b); i--)
#define per(i, k) gnr(i, k - 1, 0)
#define fi first
#define se second
#define pb push_back
#define vc vector
#define si(x) (int)(x.size())
using vi = vector<int>;
using ll = long long;
using pll = pair<ll, ll>;
map<char, int> Map;
double P[1 << 10][12][12], Pr[12];
int PC[1 << 10][12];
int n, K;
double Over(int a, int b) {
	if (abs(a - b) >= K) {
		if (a > b)
			return 1.0;
		return 0.0;
	}
	if (a > b)
		return 1 - Pr[a - b];
	return Pr[b - a];
}
using vd = vector<double>;
vd Mul(vd A, int t) { // (x+t)/K
	int m = si(A);
	vd res(m + 1);
	rep(i, m) {
		res[i] += A[i] * t / K;
		res[i + 1] += A[i] / K;
	}
	return res;
}
double res[1100];
vd Integral(vd A) {
	int m = si(A);
	vd res(m + 1);
	rep(i, m) { res[i + 1] += A[i] / (i + 1); }
	return res;
}
double Calc(int a, int M, vi T) {
	double ans = 0.0;
	rep(i, K) {
		int b = a + i, e = a + i + 1;
		int ck = 0;
		if (M + K <= b)
			continue;
		vd U;
		U.pb({1.0});
		for (auto &t : T) {
			if (t >= e) {
				ck = 1;
				break;
			}
			if (t + K <= b) {
				continue;
			}
			// b ~b + 1 t ~t + K
			// Prob: (x + b - t) / K
			U = Mul(U, b - t);
		}
		if (ck == 1)
			continue;
		if (M < e) {
			auto UU = Mul(U, b - M);
			vc<double> ZZ(si(U) + 1);
			rep(i, si(U) + 1) {
				ZZ[i] = -UU[i];
				if (i < si(U))
					ZZ[i] += U[i];
			}
			U = ZZ;
		}
		U = Integral(U);
		double tt = 0.0;
		for (auto &t : U)
			tt += t;
		ans += tt / K;
	}
	/*	printf("========\n%d\n", a);
		printf("%d\n", M);
		for (auto &t : T)
			printf("%d ", t);
		puts("");
		printf("%.10f\n", ans);
		puts("=======");*/
	return ans;
}

double D[1010][1 << 9][11];
int main() {
	scanf("%d%d", &n, &K);
	if(K==1){
		rng(i,1,n){

		}
	}
	rng(i, 0, K) { Pr[i] = 0.5 * (K - i) * (K - i) / (K * K); }
	rep(i, (1 << K)) {
		rng(j, 0, K) {
			vi V;
			rep(k, K) {
				if ((i >> k) & 1)
					V.pb(k);
			}
			V.pb(K + j);
			int m = si(V);
			if (m < 2)
				continue;
			PC[i][j] = m;
			rep(k, m) {
				rep(pv, m) {
					if (pv == k)
						continue;

					vi Z;
					rep(l, m) {
						if (l != pv && l != k) {
							Z.pb(V[l]);
						}
					}
					P[i][j][k] += Calc(V[k], V[pv], Z);
				}
				// printf("%d %d %d: %.10f\n", i, j, k, P[i][j][k]);
			}
		}
	}
	D[n][0][0] = 1;
	gnr(i, n, 0) {
		per(j, (1 << (K - 1))) {
			gnr(k, K, 0) {
				//printf("%d %d %d: %f\n", i, j, k, D[i][j][k]);
				if (D[i][j][k] < 1e-20)
					continue;
				
				int cnt = i;
				vi TP;
				rep(l, K - 1) {
					if ((j >> l) & 1){
						TP.pb(i + 1 + l);
						cnt++;
					}
				}
				int rem = -1;
				if (k) {
					cnt++;
					rem = i + K - 1 + k;
					TP.pb(i + K - 1 + k);
				}
				gnr(l, i - 1, i - 2) {
					if (l >= 0)
						TP.pb(l);
				}
				sort(all(TP));
				assert(!TP.empty());
				if (si(TP) == 1) { // only one left
					if (k!=K) {
						//printf("%d %f\n",TP[0], D[i][j][k]);
						res[TP[0]] += D[i][j][k];
					}
					continue;
				}
				int mid = TP[si(TP) - 2], ee = TP.back();
				int s = 0;
				vi V;
				rng(l, mid - K + 1, mid) {
					if (l < 0)
						continue;
					if (l >= i + 1 && ((j >> (l - i - 1)) & 1)) {
						s += (1 << (l - (mid - K + 1)));
						V.pb(l);
					}
					if (l < i) {
						s += (1 << (l - (mid - K + 1)));
						V.pb(l);
					}
				}
				V.pb(ee);
				int x = s, y = min(ee - mid - 1, K);
				int z = PC[x][y];
				//printf("cnt: %d\n",cnt);
				rep(l, z) {
					double p = P[x][y][l];
					//printf("prob %d %d %d: %f\n", x, y, l, p);
					if (p < 1e-12)
						continue;
					if (V[l] > i) {
						int pv = V[l];
						if (V[l] == rem) {
							//printf("%.10f %d %d\n", D[i][j][k] * p * cnt,k,K);
							assert(k!=K);
							assert(pv >= i+K);
							res[V[l]] += D[i][j][k] * p * cnt;
							//printf("%d %.10f\n",V[l],D[i][j][k] * p* cnt);
							D[i][j][0] += D[i][j][k] * p;
						} else {
							res[V[l]] += D[i][j][k] * p * cnt;
							//printf("%d %.10f\n",V[l],D[i][j][k] * p* cnt);
							D[i][j ^ (1 << (pv - i - 1))][k] += D[i][j][k] * p;
						}
					} else {
						int pv = V[l];
						int nrem = -1;
						int ns = 0;
						int nrori;
						for (auto &t : V) {
							if (t == pv)
								continue;
							if (t > pv) {
								if (t >= pv + K) {
									nrem = t - pv - K + 1;
									nrori = t;
								} else {
									ns += (1 << (t - pv - 1));
								}
							}
						}
						if (nrem == -1)
							nrem = 0;
						// printf("%d %d %d %f %f\n", pv, ns, nrem, D[i][j][k], p);

						//printf("%d %.10f\n",pv,D[i][j][k] * p* cnt);
						res[pv] += D[i][j][k] * p* cnt;
						if (nrem >= K && k < K) {
							//printf("?? %d %.10f\n",nrori, D[i][j][k] * p);
							res[nrori] += D[i][j][k] * p;
						}
						D[pv][ns][min(nrem,K)] += D[i][j][k] * p;
					}
				}
			}
		}
	}
	rep(i,n)printf("%.10f\n",res[i]);
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5720kb

input:

3 2

output:

2.1093750000
2.6250000000
1.2656250000

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 805ms
memory: 48884kb

input:

1000 10

output:

2.9272933166
3.5373161569
4.2811822033
5.1312206602
6.0539327790
7.0191885099
8.0057023991
9.0012910303
10.0001652077
11.0000000000
12.0000000000
13.0000000000
14.0000000000
15.0000000000
16.0000000000
17.0000000000
18.0000000000
19.0000000000
20.0000000000
21.0000000000
22.0000000000
23.0000000000
...

result:

ok 1000 numbers

Test #3:

score: 0
Accepted
time: 84ms
memory: 11068kb

input:

300 8

output:

2.7512630513
3.3900737271
4.1750068651
5.0660215194
6.0201465578
7.0045578589
8.0005725931
9.0000000000
10.0000000000
11.0000000000
12.0000000000
13.0000000000
14.0000000000
15.0000000000
16.0000000000
17.0000000000
18.0000000000
19.0000000000
20.0000000000
21.0000000000
22.0000000000
23.0000000000
...

result:

ok 300 numbers

Test #4:

score: 0
Accepted
time: 4ms
memory: 7672kb

input:

1000 3

output:

2.2302561681
3.0347656711
4.0000000000
5.0000000000
6.0000000000
7.0000000000
8.0000000000
9.0000000000
10.0000000000
11.0000000000
12.0000000000
13.0000000000
14.0000000000
15.0000000000
16.0000000000
17.0000000000
18.0000000000
19.0000000000
20.0000000000
21.0000000000
22.0000000000
23.0000000000
...

result:

ok 1000 numbers

Test #5:

score: 0
Accepted
time: 367ms
memory: 4884kb

input:

7 10

output:

2.9815864384
3.4936049601
3.9653422649
4.3196770586
4.5087248562
4.4988808477
4.2321835741

result:

ok 7 numbers

Test #6:

score: 0
Accepted
time: 294ms
memory: 29348kb

input:

993 9

output:

2.8411212285
3.4643592446
4.2273243674
5.0969425982
6.0352816658
7.0105742428
8.0023873942
9.0003025184
10.0000000000
11.0000000000
12.0000000000
13.0000000000
14.0000000000
15.0000000000
16.0000000000
17.0000000000
18.0000000000
19.0000000000
20.0000000000
21.0000000000
22.0000000000
23.0000000000
...

result:

ok 993 numbers