結果
問題 | No.5018 Let's Make a Best-seller Book |
ユーザー |
![]() |
提出日時 | 2023-10-01 00:27:26 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 245 ms / 400 ms |
コード長 | 5,002 bytes |
コンパイル時間 | 2,278 ms |
コンパイル使用メモリ | 210,224 KB |
実行使用メモリ | 24,372 KB |
スコア | 201,054 |
平均クエリ数 | 52.00 |
最終ジャッジ日時 | 2023-10-01 12:34:26 |
合計ジャッジ時間 | 31,413 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#include <bits/stdc++.h>using namespace std;class xrand {uint64_t x;public:using result_type = uint32_t;static constexpr result_type min() {return std::numeric_limits<result_type>::min();}static constexpr result_type max() {return std::numeric_limits<result_type>::max();}xrand(uint64_t k) : x(k) {}xrand() : xrand(1) {}result_type operator()() {x ^= x << 9;x ^= x >> 7;return (x * 0x123456789abcdef) >> 32;}};xrand rng;uniform_real_distribution<double> dist_d(0.5, 1.5);constexpr int T = 52, N = 10;constexpr int sample_size = 2000;double calc_p(int s, int p, int r, double d) {assert(s <= r);const double base = sqrt(r) * pow(1.05, p) * d;double low = clamp(s / base, 0.75, 1.25);double high = clamp((s + 1) / base, 0.75, 1.25);if (s == r) {high = 1.25;}return (high - low) * 2;}int convert(int x) {const int r = x % 10;if (r == 0) return x;if (r <= 3) return x + 3 - r;if (r <= 6) return x + 6 - r;return x + 10 - r;}int main() {int t, n, money;cin >> t >> n >> money;money /= 500;array<int, N> s, p, r;s.fill(0);p.fill(0);r.fill(0);array<array<double, sample_size>, N> d_particle;for (int i = 0; i < N; i++) {for (auto &&x : d_particle[i]) {x = dist_d(rng);}}int score = 0, prev_ad = -1;for (int week = 0; week < T; week++) {for (int i = 0; i < N; i++) {sort(d_particle[i].begin(), d_particle[i].end());}array<double, N> d2_avg;d2_avg.fill(0.0);for (int i = 0; i < N; i++) {for (int j = 0; j < sample_size; j++) {d2_avg[i] += d_particle[i][j] * d_particle[i][j];}d2_avg[i] /= sample_size;}array<double, N> weight;for (int i = 0; i < N; i++) {weight[i] = pow(1.05, 2 * p[i]) * d2_avg[i];}double v = 0.0, v_l = 0.0, v_r = 1e5;while (v_r - v_l > 1e-5) {double mid = 0.5 * (v_l + v_r);int count = 0;for (int i = 0; i < N; i++) {count += max(0, int(weight[i] * mid) - r[i]);}if (count <= money) {v_l = mid;} else {v_r = mid;}}v = v_l;bool ad_flag = false;if (week < 24 and week >= prev_ad + 2 and money >= 2100) {ad_flag = true;}if (week < 33 and week >= prev_ad + 2 and money >= 2500) {ad_flag = true;}if (week >= prev_ad + 2 and money >= 4000) {ad_flag = true;}if (week >= 42) {cout << 1;for (int i = 0; i < 10; i++) {cout << ' ' << max(0, int(weight[i] * v) - r[i]);}cout << endl;} else if (ad_flag) {cout << "2 2" << endl;prev_ad = week;} else {cout << 1;for (int i = 0; i < 10; i++) {double d_min = d_particle[i][0];cout << ' '<< max(0, min(int(weight[i] * v) - r[i],convert(7 * d_min * d_min *pow(1.05, 2 * p[i])) -r[i]));}cout << endl;}cin >> money;money /= 500;for (int i = 0; i < N; i++) {cin >> s[i];score += s[i];}double p2_sum = 0;for (int i = 0; i < N; i++) {cin >> p[i];double p_expect = p[i];for (int w = week + 1; w < T; w++) {if (w < 44) {p_expect += 1.2;} else {p_expect -= 0.7;}p2_sum += pow(1.05, 2 * p_expect) * d2_avg[i];}}for (auto &&x : r) {cin >> x;}for (int i = 0; i < N; i++) {array<double, sample_size> d_prob;for (int j = 0; j < sample_size; j++) {d_prob[j] = calc_p(s[i], p[i], r[i] + s[i], d_particle[i][j]);}discrete_distribution dist_idx(d_prob.begin(), d_prob.end());array<double, sample_size> d_new;for (int j = 0; j < sample_size; j++) {d_new[j] = d_particle[i][dist_idx(rng)];}d_particle[i] = move(d_new);}// cerr << score + 7 * p2_sum << endl;// if (week == T - 1) {// for (int i = 0; i < N; i++) {// cerr << reduce(d_particle[i].begin(), d_particle[i].end()) /// sample_size// << endl;// }// }}return 0;}