QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#629463 | #4230. Leaderboard Effect | nickbelov | AC ✓ | 2955ms | 1847764kb | C++20 | 3.7kb | 2024-10-11 12:01:45 | 2024-10-11 12:01:51 |
Judging History
answer
#include <vector>
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
ostream_iterator<T> oit(const string &s = " "){ return ostream_iterator<T>(cout,s.c_str()); }
inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }
#define A(a) begin(a),end(a)
inline auto len = ranges::ssize;
struct chash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template<typename T, typename U> using pb_map = gp_hash_table<T, U, chash>;
template<typename T> using pb_set = gp_hash_table<T, null_type, chash>;
#define K first
#define V second
using ll = long long;
using ld = double;
using vi = vector<int>;
using vii = vector<vector<int>>;
typedef vector<ll> vll;
using pll = pair<ll,ll>;
using pii = pair<int,int>;
const int L = 17;
void run()
{
int n,t; cin >> n >> t;
vector<ld> ans(n);
vi rt(n),ct(n); vector<ld> p(n);
for(int i : rep(n))
cin >> rt[i] >> ct[i] >> p[i];
// i need two sweep arrays, one for people who have just solved something, and one for people who are reading things
vector<array<ld,L>> solved(t+1);
vector<array<ld,1LL<<L>> sweep(t+1);
vector< array<array<ld,1LL<<L>,L> > reading(t); //time,problem,mask
sweep[0][(1<<n)-1] = 1; //everyone starts out ready to read something, having read nothing
for(int i=0;i<=t;i++){ //simulate
for(int j =0;j<n;j++) ans[j] += solved[i][j]; //update total solve distribution
if(i==t) break;
for(int j =0;j<n;j++){ //move the reading people over to the free group, update solved
for(int msk=0;msk<(1<<n);msk++){ //loop over the problems ppl are reading
if(ct[j]+i<=t) solved[i+ct[j]][j] += reading[i][j][msk] * p[j], sweep[i+ct[j]][msk] += reading[i][j][msk] * p[j];
sweep[i][msk] += reading[i][j][msk] * (1.0-p[j]);
}
}
for(int msk=0;msk<(1<<n);msk++){ //move the free people over to the reading group
ld sm = 0,problem_cnt=0; for(int j =0;j<n;j++)
if((msk>>j)&1) sm+=ans[j],problem_cnt++;
if(sm==0){
for(int j=0;j<n;j++)
if( ((msk>>j)&1) and rt[j]+i<t)
reading[rt[j]+i][j][msk ^ (1<<j)] += (1.0/problem_cnt)*(sweep[i][msk]);
}else{
for(int j=0;j<n;j++)
if( ((msk>>j)&1) and rt[j]+i<t)
reading[rt[j]+i][j][msk ^ (1<<j)] += (ans[j]/sm)*sweep[i][msk];
}
}
}
ranges::copy(ans,oit<ld>("\n"));
}
int main()
{
//KING OF THE WORLD...... U.W.T.B
cin.tie(0);
ios_base::sync_with_stdio(false);
cout << fixed << setprecision(10);
run();
}
詳細信息
Test #1:
score: 100
Accepted
time: 76ms
memory: 778488kb
input:
4 42 10 10 0.75 10 10 0.75 10 12 1 10 12 1
output:
0.4562500000 0.4562500000 0.2968750000 0.2968750000
result:
ok 4 numbers
Test #2:
score: 0
Accepted
time: 63ms
memory: 778488kb
input:
4 42 10 12 0.75 10 12 0.75 10 10 1 10 10 1
output:
0.2031250000 0.2031250000 0.6832386364 0.6832386364
result:
ok 4 numbers
Test #3:
score: 0
Accepted
time: 172ms
memory: 1847624kb
input:
5 100 40 60 0.6 40 61 1 10 40 0.3 10 40 0.4 10 40 0.5
output:
0.1200000000 0.0000000000 0.1126285714 0.1597396825 0.2064444444
result:
ok 5 numbers
Test #4:
score: 0
Accepted
time: 764ms
memory: 1847716kb
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.5466883601 0.0555190182 0.3936213911 0.3508749198 0.6674244091 0.5712225129 0.7999522166 0.0400054043 0.0061450487 0.5512562318 0.2999890330 0.3912605833 0.7604749242 0.5188051813 0.0717487880
result:
ok 15 numbers
Test #5:
score: 0
Accepted
time: 1459ms
memory: 1847576kb
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.0858804807 0.4252927315 0.9374111521 0.0922249570 0.4339959385 0.0755229268 0.1734307964 0.1017529966 0.5349333393 0.7651388862 0.4085700308 0.0002345452 0.8374910988 0.1506327548 0.8891985447 0.7760512520
result:
ok 16 numbers
Test #6:
score: 0
Accepted
time: 1318ms
memory: 1847748kb
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.0224173644 0.0006719875 0.1881340045 0.2674021961 0.0008064522 0.4812071728 0.0015086240 0.7289006401 0.0935302469 0.0144157539 0.1004794522 0.0079053003 0.0161083459 0.0114644066 0.1934422483 0.1085405082
result:
ok 16 numbers
Test #7:
score: 0
Accepted
time: 143ms
memory: 1847764kb
input:
2 100 44 23 0.344489870631275 18 13 0.617983603136949
output:
0.3444898706 0.6179836031
result:
ok 2 numbers
Test #8:
score: 0
Accepted
time: 2955ms
memory: 1847524kb
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.6097205987 0.0664162909 0.2759647935 0.0116316662 0.2653968739 0.9276187247 0.1104524533 0.9000228413 0.2724547775 0.5444190644 0.8075570096 0.7874382752 0.4241974780 0.4532898699 0.0710888474 0.0230506400 0.2766309939
result:
ok 17 numbers
Test #9:
score: 0
Accepted
time: 2568ms
memory: 1570976kb
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.5867245193 0.9129534209 0.0065806169 0.4210560868 0.4607497916 0.0315030385 0.7498298624 0.2468980556 0.7416158859 0.0087165585 0.6343383380 0.5994076444 0.0309662643 0.1419017458 0.2262892673 0.2852029504 0.6812159526
result:
ok 17 numbers
Test #10:
score: 0
Accepted
time: 2556ms
memory: 1571004kb
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.0054940768 0.0372377989 0.6294372534 0.0035434659 0.7810235280 0.6771579400 0.4108064335 0.0037438832 0.6424409296 0.0165533232 0.3038051233 0.4238316770 0.0861982873 0.8269709332 0.4612847085 0.1637608691 0.1285953725
result:
ok 17 numbers
Test #11:
score: 0
Accepted
time: 2557ms
memory: 1571128kb
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.0271150339 0.7924371560 0.2061967781 0.0204431843 0.7974743934 0.4268788097 0.2852039460 0.5518833788 0.7928221404 0.0816198932 0.4982932540 0.0041219581 0.6430107504 0.2992580192 0.3866252447 0.0144745423 0.2706075742
result:
ok 17 numbers
Test #12:
score: 0
Accepted
time: 2544ms
memory: 1571160kb
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.3972891275 0.7614221310 0.8315202044 0.7808277980 0.1962448889 0.2540902360 0.1907046121 0.7036157862 0.6802808159 0.0355531412 0.0025953894 0.2112036588 0.0039547856 0.0144260609 0.5290304907 0.2182607455 0.0876844931
result:
ok 17 numbers
Test #13:
score: 0
Accepted
time: 2212ms
memory: 1847732kb
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.0715579050 0.0085319511 0.0357815053 0.0574174662 0.0000000000 0.0000000000 0.0265779551 0.0000000000 0.0000000000 0.0761777549 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000
result:
ok 17 numbers
Test #14:
score: 0
Accepted
time: 2287ms
memory: 1847600kb
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.0000000000 0.0000000000 0.0602828144 0.0000000000 0.0415535446 0.0000000000 0.0526422882 0.0111654904 0.0000000000 0.0000000000 0.0000000000 0.0426614281 0.0000000000 0.0450980714 0.0000000000 0.0397672348 0.0560748678
result:
ok 17 numbers
Test #15:
score: 0
Accepted
time: 44ms
memory: 741572kb
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.5385000000 0.3765000000 0.2415000000 0.2385000000 0.2385000000
result:
ok 5 numbers