QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#629463#4230. Leaderboard EffectnickbelovAC ✓2955ms1847764kbC++203.7kb2024-10-11 12:01:452024-10-11 12:01:51

Judging History

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

  • [2024-10-11 12:01:51]
  • 评测
  • 测评结果:AC
  • 用时:2955ms
  • 内存:1847764kb
  • [2024-10-11 12:01:45]
  • 提交

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