QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#496634 | #4230. Leaderboard Effect | CelestialCoder# | AC ✓ | 2080ms | 213928kb | C++20 | 2.4kb | 2024-07-28 14:02:26 | 2024-07-28 14:02:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 17;
const int MAX_T = 100 + 1;
const double EPS = 1e-15;
double dp[MAX_T][1 << MAX_N];
double score[MAX_T][MAX_N];
double scsum[MAX_T][1 << MAX_N];
bool ok[MAX_T][1 << MAX_N];
int popcnt[1 << MAX_N];
void solve() {
int n, T;
cin >> n >> T;
vector<int> r(n), c(n);
vector<double> pr(n);
for (int i=0; i<n; ++i) cin >> r[i] >> c[i] >> pr[i];
for (int i=0; i<(1<<n); ++i) popcnt[i] = __builtin_popcount(i);
memset(dp, 0, sizeof dp);
memset(score[0], 0, sizeof score[0]);
memset(scsum, 0, sizeof scsum);
dp[0][0] = 1.0;
const int fulm = (1 << n) - 1;
for (int t=1; t<=T; ++t) {
memcpy(score[t], score[t-1], sizeof score[t]);
for (int mask=0; mask<(1<<n); ++mask) {
double sum1 = 0.0, sum2 = 0.0;
for (int i=0; i<n; ++i) {
if (mask & (1 << i)) {
int cpl = fulm ^ mask ^ (1 << i);
double sel_pr1 = 0.0;
if (t >= r[i]+c[i]) sel_pr1 = (scsum[t-r[i]-c[i]][cpl] == 0 ? 1.0 / popcnt[cpl] : score[t-r[i]-c[i]][i] / scsum[t-r[i]-c[i]][cpl]);
double sel_pr2 = 0.0;
if (t >= r[i]) sel_pr2 = (scsum[t-r[i]][cpl] == 0 ? 1.0 / popcnt[cpl] : score[t-r[i]][i] / scsum[t-r[i]][cpl]);
double tmp1 = (t < r[i]+c[i] ? 0.0 : dp[t-r[i]-c[i]][mask ^ (1 << i)] * pr[i] * sel_pr1);
double tmp2 = (t < r[i] ? 0.0 : dp[t-r[i]][mask ^ (1 << i)] * (1.0-pr[i]) * sel_pr2);
score[t][i] += tmp1;
sum1 += tmp1;
sum2 += tmp2;
}
}
dp[t][mask] = sum1 + sum2;
// cout << "dp: " << t << ' ' << mask << ' ' << dp[t][mask] << '\n';
}
// for (int i=0; i<n; ++i) cout << t << ' ' << i << ' ' << score[t][i] << '\n';
for (int mask=0; mask<(1<<n); ++mask) {
for (int i=0; i<n; ++i) {
if (mask & (1 << i)) scsum[t][mask] += score[t][i];
}
}
}
for (int i=0; i<n; ++i) cout << score[T][i] << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout << fixed << setprecision(15);
solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 212068kb
input:
4 42 10 10 0.75 10 10 0.75 10 12 1 10 12 1
output:
0.456250000000000 0.456250000000000 0.296875000000000 0.296875000000000
result:
ok 4 numbers
Test #2:
score: 0
Accepted
time: 7ms
memory: 212552kb
input:
4 42 10 12 0.75 10 12 0.75 10 10 1 10 10 1
output:
0.203125000000000 0.203125000000000 0.683238636363636 0.683238636363636
result:
ok 4 numbers
Test #3:
score: 0
Accepted
time: 4ms
memory: 212164kb
input:
5 100 40 60 0.6 40 61 1 10 40 0.3 10 40 0.4 10 40 0.5
output:
0.120000000000000 0.000000000000000 0.112628571428571 0.159739682539683 0.206444444444444
result:
ok 5 numbers
Test #4:
score: 0
Accepted
time: 469ms
memory: 210880kb
input:
15 100 4 14 0.954205412740471 5 11 0.264054003774017 1 7 0.521673865442381 3 12 0.6756938980261 1 15 0.980129050876819 2 12 0.836645892885326 10 3 0.959863273940343 13 6 0.230786407526669 3 13 0.0575791282076707 6 5 0.706328060881614 1 15 0.662404274712202 2 13 0.715327416279894 11 2 0.9275847467499...
output:
0.546688360092044 0.055519018242139 0.393621391115126 0.350874919754766 0.667424409119582 0.571222512937186 0.799952216612443 0.040005404338939 0.006145048719599 0.551256231843785 0.299989033034684 0.391260583274801 0.760474924225950 0.518805181308483 0.071748788009809
result:
ok 15 numbers
Test #5:
score: 0
Accepted
time: 962ms
memory: 212528kb
input:
16 100 1 8 0.203833126785817 1 10 0.551151943064124 1 12 0.996220861387656 1 7 0.198656409543208 2 2 0.467994369421028 8 3 0.201277956430612 1 10 0.33397726300295 1 8 0.223430703554389 3 12 0.715363922664928 9 6 0.883743052774488 1 9 0.51636293824285 2 7 0.00210327442137626 6 11 0.978989778915285 1 ...
output:
0.085880480704923 0.425292731546362 0.937411152137167 0.092224956990477 0.433995938461809 0.075522926844036 0.173430796407677 0.101752996585516 0.534933339311469 0.765138886172388 0.408570030793363 0.000234545182917 0.837491098750247 0.150632754765004 0.889198544694592 0.776051252008178
result:
ok 16 numbers
Test #6:
score: 0
Accepted
time: 952ms
memory: 212892kb
input:
16 100 36 30 0.246284470931766 40 2 0.00729886464249319 34 9 0.969806174971755 2 27 0.700168809611093 2 49 0.00964738878291982 11 13 0.843818712396597 23 15 0.015695164745825 2 11 0.860911871987035 8 39 0.759047449661107 33 17 0.156016479857797 5 40 0.704380590007194 2 36 0.0742940485679995 13 17 0....
output:
0.022417364414376 0.000671987468592 0.188134004526025 0.267402196062388 0.000806452249446 0.481207172814252 0.001508624006811 0.728900640076841 0.093530246883962 0.014415753884894 0.100479452210368 0.007905300344661 0.016108345935736 0.011464406576285 0.193442248319016 0.108540508187959
result:
ok 16 numbers
Test #7:
score: 0
Accepted
time: 4ms
memory: 210812kb
input:
2 100 44 23 0.344489870631275 18 13 0.617983603136949
output:
0.344489870631275 0.617983603136949
result:
ok 2 numbers
Test #8:
score: 0
Accepted
time: 2080ms
memory: 212880kb
input:
17 100 1 6 0.618966248907732 1 6 0.126915204708293 4 7 0.35153234988752 2 3 0.0368548187261588 1 5 0.299571483949073 1 12 0.944530094804986 3 12 0.249408160616937 1 11 0.91317090384857 5 8 0.377638681694897 4 12 0.639080155811651 1 4 0.809300766237897 8 5 0.812731204986182 1 10 0.480107932016118 7 1...
output:
0.609720598660348 0.066416290908454 0.275964793487314 0.011631666152016 0.265396873852895 0.927618724724243 0.110452453340902 0.900022841304208 0.272454777474703 0.544419064353590 0.807557009623712 0.787438275235433 0.424197477957634 0.453289869882946 0.071088847407507 0.023050639997669 0.2766309939...
result:
ok 17 numbers
Test #9:
score: 0
Accepted
time: 1770ms
memory: 211812kb
input:
17 85 8 6 0.9977 1 4 0.9459 5 9 0.0733 2 9 0.759 9 6 0.921 5 6 0.2015 2 8 0.9407 8 10 0.7806 5 3 0.864 4 4 0.0777 9 3 0.9518 8 2 0.8221 10 9 0.2471 4 8 0.4679 7 6 0.603 3 2 0.4067 5 5 0.8879
output:
0.586724519250858 0.912953420937830 0.006580616859528 0.421056086792976 0.460749791576520 0.031503038542140 0.749829862412147 0.246898055559733 0.741615885873553 0.008716558501778 0.634338337966263 0.599407644446756 0.030966264343318 0.141901745771311 0.226289267326073 0.285202950435192 0.6812159525...
result:
ok 17 numbers
Test #10:
score: 0
Accepted
time: 1752ms
memory: 212720kb
input:
17 85 9 7 0.0563 7 7 0.1979 9 3 0.7689 1 6 0.0291 7 7 0.9631 5 8 0.847 8 6 0.6752 2 9 0.0396 4 2 0.6747 8 3 0.1071 8 4 0.5134 9 7 0.7491 6 8 0.3134 3 1 0.8355 4 5 0.5561 1 10 0.372 9 9 0.4515
output:
0.005494076787487 0.037237798874601 0.629437253361244 0.003543465855541 0.781023527962308 0.677157939955950 0.410806433460015 0.003743883246819 0.642440929631889 0.016553323195167 0.303805123336422 0.423831677025418 0.086198287282299 0.826970933203289 0.461284708494305 0.163760869135408 0.1285953724...
result:
ok 17 numbers
Test #11:
score: 0
Accepted
time: 1784ms
memory: 213020kb
input:
17 85 1 7 0.1344 5 8 0.99 8 3 0.437 4 9 0.1375 3 2 0.8208 1 8 0.5922 10 6 0.655 8 5 0.8043 2 5 0.8447 5 10 0.3305 9 3 0.725 1 8 0.0394 6 5 0.8091 8 7 0.6427 9 6 0.7282 4 7 0.1024 1 6 0.4222
output:
0.027115033929916 0.792437156034287 0.206196778123339 0.020443184337909 0.797474393400882 0.426878809713139 0.285203945992885 0.551883378811691 0.792822140398924 0.081619893150216 0.498293254014563 0.004121958074336 0.643010750412073 0.299258019222366 0.386625244711537 0.014474542348519 0.2706075742...
result:
ok 17 numbers
Test #12:
score: 0
Accepted
time: 1745ms
memory: 212904kb
input:
17 85 10 2 0.6556 3 1 0.7738 1 8 0.9047 3 10 0.9973 10 4 0.5266 8 1 0.4384 5 3 0.3559 3 6 0.7999 8 6 0.9665 3 4 0.142 7 5 0.0319 6 3 0.4056 6 10 0.0477 8 10 0.1334 5 8 0.8102 8 8 0.6 7 5 0.318
output:
0.397289127475765 0.761422130971487 0.831520204401349 0.780827798025840 0.196244888928752 0.254090235986807 0.190704612138877 0.703615786202459 0.680280815914446 0.035553141225697 0.002595389400108 0.211203658821676 0.003954785625942 0.014426060932876 0.529030490740827 0.218260745505959 0.0876844930...
result:
ok 17 numbers
Test #13:
score: 0
Accepted
time: 1754ms
memory: 213928kb
input:
17 100 10 41 0.986344070444954 38 40 0.13596976314146 23 65 0.589188420670698 23 41 0.862487981086339 66 62 0.756039635351495 84 82 0.466671597793749 17 74 0.451825236037525 97 49 0.785964886639839 76 26 0.432545432217108 10 33 0.495053202758143 35 72 0.437261903429889 55 95 0.333190022475783 83 56 ...
output:
0.071557905030191 0.008531951117394 0.035781505339295 0.057417466249548 0.000000000000000 0.000000000000000 0.026577955061031 0.000000000000000 0.000000000000000 0.076177754926464 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.0000000000...
result:
ok 17 numbers
Test #14:
score: 0
Accepted
time: 1759ms
memory: 212820kb
input:
17 100 52 66 0.608312285077897 77 36 0.182402129968963 43 16 0.906840075497175 75 100 0.508033408075313 25 60 0.688919263266595 84 59 0.17045120790047 75 9 0.831462171228754 16 69 0.185113485186001 71 54 0.372346884200038 90 65 0.235248490382517 62 50 0.917089563798644 47 45 0.717838729472597 56 51 ...
output:
0.000000000000000 0.000000000000000 0.060282814414062 0.000000000000000 0.041553544552180 0.000000000000000 0.052642288171710 0.011165490448638 0.000000000000000 0.000000000000000 0.000000000000000 0.042661428112687 0.000000000000000 0.045098071399119 0.000000000000000 0.039767234849516 0.0560748677...
result:
ok 17 numbers
Test #15:
score: 0
Accepted
time: 3ms
memory: 212296kb
input:
5 40 10 8 0.9 10 9 0.9 10 10 0.9 10 11 0.9 10 12 0.9
output:
0.538500000000000 0.376500000000000 0.241500000000000 0.238500000000000 0.238500000000000
result:
ok 5 numbers