QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#54948#4230. Leaderboard EffectKING_UT#AC ✓2678ms1908832kbC++201.7kb2022-10-11 18:33:292022-10-11 18:33:32

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-11 18:33:32]
  • 评测
  • 测评结果:AC
  • 用时:2678ms
  • 内存:1908832kb
  • [2022-10-11 18:33:29]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t>using vc=vector<t>;
template<class t>using vvc=vc<vc<t>>;
template<class t, class u>bool chmin(t &a, u b){
	if(a > b){ a = b; return true;}
	else return false;
}
template<class t, class u>bool chmax(t &a, u b){
	if(a < b){ a = b; return true;}
	else return false;
}
using vi=vc<int>;
#define a first
#define b second
#define mp make_pair
using pi=pair<int,int>;

const int inf=INT_MAX/2-100;

const int nmax=17;
const int tmax=105;

using ld=long double;
ld dp[tmax][1<<nmax];

void slv(){
	int n,t;cin>>n>>t;
	vc<pi> rc(n);
	vc<ld> can(n);
	rep(i,n){
		cin>>rc[i].a>>rc[i].b;
		cin>>can[i];
	}
	using P=pair<int,ld>;
	vvc<P> add(t+1);
	
	dp[0][0]=1;
	
	vc<ld> done(n);
	
	rep(i,t+1){
		for(auto [j,v]:add[i])done[j]+=v;
		if(i<t){
			rep(bit,(1<<n)-1)if(dp[i][bit]>0){
				ld tot=0;
				int cnt=0;
				rep(j,n)if(!(bit&1<<j)){
					tot+=done[j];
					cnt++;
				}
				rep(j,n)if(!(bit&1<<j)){
					ld prob=(tot==0?ld(1)/cnt:done[j]/tot)*dp[i][bit];
					{//not solve
						int nx=i+rc[j].a;
						if(nx<=t){
							dp[nx][bit|1<<j]+=prob*(1-can[j]);
						}
					}
					{//solve
						int nx=i+rc[j].a+rc[j].b;
						if(nx<=t){
							dp[nx][bit|1<<j]+=prob*can[j];
							add[nx].eb(j,prob*can[j]);
						}
					}
				}
			}
		}
	}
	
	rep(i,n)cout<<done[i]<<endl;
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	slv();
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 18088kb

input:

4 42
10 10 0.75
10 10 0.75
10 12 1
10 12 1

output:

0.45625000000000000001
0.45625000000000000001
0.29687500000000000003
0.29687500000000000003

result:

ok 4 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 18092kb

input:

4 42
10 12 0.75
10 12 0.75
10 10 1
10 10 1

output:

0.20312500000000000000
0.20312500000000000000
0.68323863636363636363
0.68323863636363636363

result:

ok 4 numbers

Test #3:

score: 0
Accepted
time: 5ms
memory: 20220kb

input:

5 100
40 60 0.6
40 61 1
10 40 0.3
10 40 0.4
10 40 0.5

output:

0.12000000000000000000
0.00000000000000000000
0.11262857142857142857
0.15973968253968253969
0.20644444444444444443

result:

ok 5 numbers

Test #4:

score: 0
Accepted
time: 497ms
memory: 362424kb

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.54668836009203605519
0.05551901824213992240
0.39362139111512301585
0.35087491975478211022
0.66742440911959153898
0.57122251293715968219
0.79995221661243068795
0.04000540433893953495
0.00614504871959888828
0.55125623184380998030
0.29998903303469589735
0.39126058327480314647
0.76047492422599132086
0...

result:

ok 15 numbers

Test #5:

score: 0
Accepted
time: 1148ms
memory: 850880kb

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.08588048070492942615
0.42529273154636671240
0.93741115213716639349
0.09222495699047236759
0.43399593846182312734
0.07552292684403203595
0.17343079640767914689
0.10175299658552264439
0.53493333931145086948
0.76513888617242374851
0.40857003079337221851
0.00023454518291695144
0.83749109875028284264
0...

result:

ok 16 numbers

Test #6:

score: 0
Accepted
time: 37ms
memory: 54772kb

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.02241736441437572776
0.00067198746859231575
0.18813400452602550207
0.26740219606238851442
0.00080645224944633292
0.48120717281425315356
0.00150862400681100832
0.72890064007684276170
0.09353024688396185712
0.01441575388489400797
0.10047945221036762317
0.00790530034466072125
0.01610834593573616254
0...

result:

ok 16 numbers

Test #7:

score: 0
Accepted
time: 2ms
memory: 20232kb

input:

2 100
44 23 0.344489870631275
18 13 0.617983603136949

output:

0.34448987063127500000
0.61798360313694899998

result:

ok 2 numbers

Test #8:

score: 0
Accepted
time: 2678ms
memory: 1908832kb

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.60972059866033334916
0.06641629090845206311
0.27596479348733366727
0.01163166615201631793
0.26539687385289337563
0.92761872472416292333
0.11045245334090534544
0.90002284130407108286
0.27245477747470556713
0.54441906435362974969
0.80755700962378859062
0.78743827523542379290
0.42419747795768165773
0...

result:

ok 17 numbers

Test #9:

score: 0
Accepted
time: 1454ms
memory: 973236kb

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.58672451925085351718
0.91295342093797277012
0.00658061685952919133
0.42105608679299636431
0.46074979157654575077
0.03150303854214339403
0.74982986241219044018
0.24689805555974362682
0.74161588587362551895
0.00871655850178168914
0.63433833796624744175
0.59940764444686042098
0.03096626434331925751
0...

result:

ok 17 numbers

Test #10:

score: 0
Accepted
time: 1385ms
memory: 901796kb

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.00549407678748756453
0.03723779887460487792
0.62943725336130419614
0.00354346585554060389
0.78102352796223359626
0.67715793995596022781
0.41080643346000578138
0.00374388324681877431
0.64244092963195117177
0.01655332319516672402
0.30380512333644084922
0.42383167702539645543
0.08619828728229880658
0...

result:

ok 17 numbers

Test #11:

score: 0
Accepted
time: 1654ms
memory: 1093072kb

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.02711503392991635632
0.79243715603432841670
0.20619677812333993807
0.02044318433790967323
0.79747439340083094963
0.42687880971313618328
0.28520394599287390722
0.55188337881167392665
0.79282214039892284595
0.08161989315021482285
0.49829325401456582502
0.00412195807433574452
0.64301075041209664491
0...

result:

ok 17 numbers

Test #12:

score: 0
Accepted
time: 1412ms
memory: 949168kb

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.39728912747579148422
0.76142213097162263550
0.83152020440142030544
0.78082779802580724637
0.19624488892875800225
0.25409023598682602550
0.19070461213892970016
0.70361578620250507060
0.68028081591440284334
0.03555314122570714360
0.00259538940010823558
0.21120365882171380939
0.00395478562594186427
0...

result:

ok 17 numbers

Test #13:

score: 0
Accepted
time: 25ms
memory: 20740kb

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.07155790503019076150
0.00853195111739396568
0.03578150533929467923
0.05741746624954843056
0.00000000000000000000
0.00000000000000000000
0.02657795506103088235
0.00000000000000000000
0.00000000000000000000
0.07617775492646394233
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 17 numbers

Test #14:

score: 0
Accepted
time: 47ms
memory: 20864kb

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.00000000000000000000
0.00000000000000000000
0.06028281441406229047
0.00000000000000000000
0.04155354455217949851
0.00000000000000000000
0.05264228817170953664
0.01116549044863773569
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.04266142811268726464
0.00000000000000000000
0...

result:

ok 17 numbers

Test #15:

score: 0
Accepted
time: 2ms
memory: 20284kb

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.53849999999999999988
0.37649999999999999992
0.24149999999999999999
0.23849999999999999998
0.23849999999999999998

result:

ok 5 numbers