QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#33782#4230. Leaderboard EffectBalintR#AC ✓982ms106968kbC++2.6kb2022-06-05 05:52:552022-06-05 05:52:56

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-05 05:52:56]
  • 评测
  • 测评结果:AC
  • 用时:982ms
  • 内存:106968kb
  • [2022-06-05 05:52:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cmplx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) (v).begin(), (v).end()
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound((v).begin(), (v).end(), x) - (v).begin())
#define ubv(v, x) (upper_bound((v).begin(), (v).end(), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << arr[_i]; cerr << endl;}

const int MN = 17;
const int PW = 1<<MN;
const int MT = 101;

int n, t, pw;
int rrr[MN], crr[MN];
double dif[MN];

double dp[MT][PW];
double solved[MT][MN];

int main(){
    boost();
    cin >> n >> t;
    pw = 1 << n;
    FR(i, n) cin >> rrr[i] >> crr[i] >> dif[i];
    dp[0][pw-1] = 1;

    FR(i, t){
        FOR(s, 1, pw){
            if(dp[i][s] == 0) continue;
            double solveSum = 0;
            FR(j, n) solveSum += solved[i][j] * ((s >> j) & 1);

            vector<double> tryCh(n);
            if(solveSum) FR(j, n) tryCh[j] = solved[i][j]/solveSum * ((s >> j) & 1);
            else {
                int pop = __builtin_popcount(s);
                FR(j, n) tryCh[j] = double((s >> j) & 1) / pop;
            }

            //dbg(s);
            //dbgArr(tryCh.begin(), SZ(tryCh));

            FR(j, n){
                double chNoSolve = dp[i][s] * tryCh[j] * (1-dif[j]);
                double chSolve = dp[i][s] * tryCh[j] * dif[j];

                if(i + rrr[j] <= t) dp[i+rrr[j]][s^(1<<j)] += chNoSolve;
                if(i + rrr[j] + crr[j] <= t){
                    dp[i+rrr[j]+crr[j]][s^(1<<j)] += chSolve;
                    solved[i+rrr[j]+crr[j]][j] += chSolve;
                }
            }
        }

        FR(j, n) solved[i+1][j] += solved[i][j];
    }

    cout << fixed << setprecision(9);
    FR(i, n) cout << solved[t][i] << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 18204kb

input:

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

output:

0.456250000
0.456250000
0.296875000
0.296875000

result:

ok 4 numbers

Test #2:

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

input:

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

output:

0.203125000
0.203125000
0.683238636
0.683238636

result:

ok 4 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 22220kb

input:

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

output:

0.120000000
0.000000000
0.112628571
0.159739683
0.206444444

result:

ok 5 numbers

Test #4:

score: 0
Accepted
time: 174ms
memory: 63152kb

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.546688360
0.055519018
0.393621391
0.350874920
0.667424409
0.571222513
0.799952217
0.040005404
0.006145049
0.551256232
0.299989033
0.391260583
0.760474924
0.518805181
0.071748788

result:

ok 15 numbers

Test #5:

score: 0
Accepted
time: 411ms
memory: 77884kb

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.085880481
0.425292732
0.937411152
0.092224957
0.433995938
0.075522927
0.173430796
0.101752997
0.534933339
0.765138886
0.408570031
0.000234545
0.837491099
0.150632755
0.889198545
0.776051252

result:

ok 16 numbers

Test #6:

score: 0
Accepted
time: 15ms
memory: 68764kb

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.022417364
0.000671987
0.188134005
0.267402196
0.000806452
0.481207173
0.001508624
0.728900640
0.093530247
0.014415754
0.100479452
0.007905300
0.016108346
0.011464407
0.193442248
0.108540508

result:

ok 16 numbers

Test #7:

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

input:

2 100
44 23 0.344489870631275
18 13 0.617983603136949

output:

0.344489871
0.617983603

result:

ok 2 numbers

Test #8:

score: 0
Accepted
time: 982ms
memory: 106968kb

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.609720599
0.066416291
0.275964793
0.011631666
0.265396874
0.927618725
0.110452453
0.900022841
0.272454777
0.544419064
0.807557010
0.787438275
0.424197478
0.453289870
0.071088847
0.023050640
0.276630994

result:

ok 17 numbers

Test #9:

score: 0
Accepted
time: 467ms
memory: 90484kb

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.586724519
0.912953421
0.006580617
0.421056087
0.460749792
0.031503039
0.749829862
0.246898056
0.741615886
0.008716559
0.634338338
0.599407644
0.030966264
0.141901746
0.226289267
0.285202950
0.681215953

result:

ok 17 numbers

Test #10:

score: 0
Accepted
time: 459ms
memory: 90712kb

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.005494077
0.037237799
0.629437253
0.003543466
0.781023528
0.677157940
0.410806433
0.003743883
0.642440930
0.016553323
0.303805123
0.423831677
0.086198287
0.826970933
0.461284708
0.163760869
0.128595372

result:

ok 17 numbers

Test #11:

score: 0
Accepted
time: 531ms
memory: 91624kb

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.027115034
0.792437156
0.206196778
0.020443184
0.797474393
0.426878810
0.285203946
0.551883379
0.792822140
0.081619893
0.498293254
0.004121958
0.643010750
0.299258019
0.386625245
0.014474542
0.270607574

result:

ok 17 numbers

Test #12:

score: 0
Accepted
time: 441ms
memory: 91720kb

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.397289127
0.761422131
0.831520204
0.780827798
0.196244889
0.254090236
0.190704612
0.703615786
0.680280816
0.035553141
0.002595389
0.211203659
0.003954786
0.014426061
0.529030491
0.218260746
0.087684493

result:

ok 17 numbers

Test #13:

score: 0
Accepted
time: 12ms
memory: 49224kb

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.071557905
0.008531951
0.035781505
0.057417466
0.000000000
0.000000000
0.026577955
0.000000000
0.000000000
0.076177755
0.000000000
0.000000000
0.000000000
0.000000000
0.000000000
0.000000000
0.000000000

result:

ok 17 numbers

Test #14:

score: 0
Accepted
time: 12ms
memory: 49680kb

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.000000000
0.000000000
0.060282814
0.000000000
0.041553545
0.000000000
0.052642288
0.011165490
0.000000000
0.000000000
0.000000000
0.042661428
0.000000000
0.045098071
0.000000000
0.039767235
0.056074868

result:

ok 17 numbers

Test #15:

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

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.538500000
0.376500000
0.241500000
0.238500000
0.238500000

result:

ok 5 numbers