QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#120348 | #6565. Game Show Elimination | hos_lyric | AC ✓ | 513ms | 183568kb | C++14 | 5.7kb | 2023-07-06 16:57:17 | 2023-07-06 16:57:19 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
using Double = long double;
constexpr Double EPS = 1e-100L;
int N, K;
vector<Double> ans;
struct Prob {
Double top1, top2;
Double se[10];
};
// top1 - top2, top2 - set
Prob prob[11][1 << 10];
// top1, top1 - top2, top2 - set
// top1 - top2 >= K ==> top1 remains forever (change top1 := top2 + K)
Double dp[1010][11][1 << 10];
int main() {
for (; ~scanf("%d%d", &N, &K); ) {
ans.assign(N, 1.0);
if (N >= 2) {
memset(prob, 0, sizeof(prob));
for (int j = 1; j <= K; ++j) for (int h = 1 << K; (h -= 2) >= 0; ) {
int len = 0;
int skills[12];
skills[len++] = 0;
skills[len++] = 0 - j;
for (int k = 1; k < K; ++k) if (h >> k & 1) {
skills[len++] = 0 - j - k;
}
Double fs[12] = {};
for (int u = 0; u < len; ++u) {
// person u is the second
for (int x = skills[u]; x < skills[u] + K; ++x) {
// [x, x + 1)
// eq, big
Double sub[12 + 2][1 + 2] = {};
sub[1][0] = 1.0 / K;
for (int v = 0; v < len; ++v) if (u != v) {
Double pSmall = 0.0, pEq = 0.0, pBig = 0.0;
if (skills[v] + K <= x) {
pSmall = 1.0;
} else if (x + 1 <= skills[v]) {
pBig = 1.0;
} else {
pSmall = (Double)(x - skills[v]) / K;
pEq = 1.0 / K;
pBig = (Double)((skills[v] + K) - (x + 1)) / K;
}
for (int eq = len; eq >= 1; --eq) for (int big = 1; big >= 0; --big) {
sub[eq][big + 1] += sub[eq][big] * pBig;
sub[eq + 1][big] += sub[eq][big] * pEq;
sub[eq][big] *= pSmall;
}
}
for (int eq = len; eq >= 1; --eq) {
fs[u] += sub[eq][1] / eq;
if (eq >= 2) {
fs[u] += sub[eq][0] / eq;
}
}
}
}
int pos = 0;
prob[j][h].top1 = fs[pos++];
prob[j][h].top2 = fs[pos++];
for (int k = 1; k < K; ++k) if (h >> k & 1) {
prob[j][h].se[k] = fs[pos++];
}
assert(pos == len);
}
const int mask = (1 << K) - (1 << 1);
memset(dp, 0, sizeof(dp));
{
int ini = 0;
for (int k = 1; k < K; ++k) if (N - 2 - k >= 0) {
ini |= 1 << k;
}
dp[N - 1][1][ini] = 1.0;
}
for (int i = N; --i >= 0; ) {
for (int j = 1; j <= K; ++j) {
int coming = 0;
for (int k = K; k < 2 * K; ++k) if (i - j - k >= 0) {
coming |= 1 << k;
}
for (int h = 1 << K; (h -= 2) >= 0; ) {
const Double f = dp[i][j][h];
if (f > EPS) {
// cerr<<i<<" "<<j<<" "<<h<<": "<<f<<" -> "<<prob[j][h].top1<<" "<<prob[j][h].top2<<"; ";pv(prob[j][h].se,prob[j][h].se+K);
const int score = 1 + __builtin_popcount(h) + max(i - j - K + 1, 0);
// top1
{
const Double fp = f * prob[j][h].top1;
ans[i] += fp * score;
if (h) {
const int jj = __builtin_ctz(h);
dp[i - j][jj][(h | coming) >> jj & mask] += fp;
} else if (coming) {
const int jj = __builtin_ctz(coming);
dp[i - j - jj + K][K][coming >> jj & mask] += fp;
}
}
// top2
{
const Double fp = f * prob[j][h].top2;
ans[i - j] += fp * score;
if (h) {
const int jj = __builtin_ctz(h);
if (j + jj < K) {
dp[i][j + jj][(h | coming) >> jj & mask] += fp;
} else {
dp[i - j - jj + K][K][(h | coming) >> jj & mask] += fp;
}
} else if (coming) {
const int jj = __builtin_ctz(coming);
dp[i - j - jj + K][K][coming >> jj & mask] += fp;
}
}
// from set
for (int k = 1; k < K; ++k) if (h >> k & 1) {
const Double fp = f * prob[j][h].se[k];
ans[i - j - k] += fp * score;
dp[i][j][h - (1 << k)] += fp;
}
}
}
}
}
}
for (int i = 0; i < N; ++i) {
printf("%.9Lf\n", ans[i]);
}
#ifdef LOCAL
cerr<<"========"<<endl;
#endif
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 183548kb
input:
3 2
output:
2.109375000 2.625000000 1.265625000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 513ms
memory: 183520kb
input:
1000 10
output:
2.927293317 3.537316157 4.281182203 5.131220660 6.053932779 7.019188510 8.005702399 9.001291030 10.000165208 11.000000000 12.000000000 13.000000000 14.000000000 15.000000000 16.000000000 17.000000000 18.000000000 19.000000000 20.000000000 21.000000000 22.000000000 23.000000000 24.000000000 25.000000...
result:
ok 1000 numbers
Test #3:
score: 0
Accepted
time: 34ms
memory: 183524kb
input:
300 8
output:
2.751263051 3.390073727 4.175006865 5.066021519 6.020146558 7.004557859 8.000572593 9.000000000 10.000000000 11.000000000 12.000000000 13.000000000 14.000000000 15.000000000 16.000000000 17.000000000 18.000000000 19.000000000 20.000000000 21.000000000 22.000000000 23.000000000 24.000000000 25.000000...
result:
ok 300 numbers
Test #4:
score: 0
Accepted
time: 4ms
memory: 183568kb
input:
1000 3
output:
2.230256168 3.034765671 4.000000000 5.000000000 6.000000000 7.000000000 8.000000000 9.000000000 10.000000000 11.000000000 12.000000000 13.000000000 14.000000000 15.000000000 16.000000000 17.000000000 18.000000000 19.000000000 20.000000000 21.000000000 22.000000000 23.000000000 24.000000000 25.000000...
result:
ok 1000 numbers
Test #5:
score: 0
Accepted
time: 154ms
memory: 183508kb
input:
7 10
output:
2.981586438 3.493604960 3.965342265 4.319677059 4.508724856 4.498880848 4.232183574
result:
ok 7 numbers
Test #6:
score: 0
Accepted
time: 173ms
memory: 183468kb
input:
993 9
output:
2.841121229 3.464359245 4.227324367 5.096942598 6.035281666 7.010574243 8.002387394 9.000302518 10.000000000 11.000000000 12.000000000 13.000000000 14.000000000 15.000000000 16.000000000 17.000000000 18.000000000 19.000000000 20.000000000 21.000000000 22.000000000 23.000000000 24.000000000 25.000000...
result:
ok 993 numbers