QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#120348#6565. Game Show Eliminationhos_lyricAC ✓513ms183568kbC++145.7kb2023-07-06 16:57:172023-07-06 16:57:19

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-06 16:57:19]
  • 评测
  • 测评结果:AC
  • 用时:513ms
  • 内存:183568kb
  • [2023-07-06 16:57:17]
  • 提交

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