QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#24053#2896. Black and WhiteEmiya_KiritsuguAC ✓342ms28096kbC++172.0kb2022-03-25 17:42:552022-04-30 04:49:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 04:49:22]
  • 评测
  • 测评结果:AC
  • 用时:342ms
  • 内存:28096kb
  • [2022-03-25 17:42:55]
  • 提交

answer

#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <iostream>
#include <string.h>

using namespace std;

const int INF = INT_MAX >> 1;
const int MOD = 1'000'000'000 + 7;
int N;

double dfs(const int ST, vector<double> &expec, vector<double> const &faceUp, vector<double> const &faceDown) {
    if(expec[ST] >= 0) {
        return expec[ST];
    }

    double psum = 0.0;
    double Esum = 0.0;
    for(int i = 0; i < N; ++i) {
        if(ST & (1 << i)) {
            int afterKick = (ST ^ (1 << i));
            double curP = faceUp[1<<i] * faceDown[afterKick] + faceDown[1<<i] * faceUp[afterKick];

            Esum += curP * dfs(afterKick, expec, faceUp, faceDown);
            psum += curP;
        }
    }

    expec[ST] = (1 + Esum) / psum;
    return expec[ST];
}

void solve(int testCase) {
    scanf("%d", &N);
    vector<double> ps(N, 0.0);
    for(int i = 0; i < N; ++i)
        scanf("%lf", &ps[i]);
    
    // if(2 == N) {
        
    //     return;
    // }

    const int MAXSZ = 1 << N;
    vector<double> expec(MAXSZ, -1);
    for(int i = 0; i < N; ++i) {
        for(int j = i + 1; j < N; ++j) {
            expec[(1 << i) | (1 << j) ] = 0;
        }
    }

    vector<double> faceUp(MAXSZ, 1), faceDown(MAXSZ, 1);
    for(int i = 0; i < N; ++i) {
        for(int state = 1; state < MAXSZ; ++state) {
            if(state & (1 << i)) {
                faceUp[state] *= ps[i];
                faceDown[state] *= (1 - ps[i]);
            }
        }
    }

    dfs(MAXSZ - 1, expec, faceUp, faceDown);

    printf("%.7lf\n", expec[MAXSZ-1]);
}  

bool multi = false;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    if (multi) {
        cin >> t;
    }
    for (int i = 1; i <= t; ++i) {
        solve(i);
        // cout << "\n";
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3860kb

input:

2
0.616
0.689

output:

0.0000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #2:

score: 0
Accepted
time: 342ms
memory: 27824kb

input:

20
0.256
0.546
0.617
0.86
0.138
0.282
0.271
0.124
0.238
0.769
0.899
0.214
0.166
0.626
0.876
0.161
0.774
0.891
0.819
0.653

output:

1393404.7887949

result:

ok found '1393404.7887949', expected '1393404.7887950', error '0.0000000'

Test #3:

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

input:

3
0.883
0.132
0.135

output:

1.1155498

result:

ok found '1.1155498', expected '1.1155498', error '0.0000000'

Test #4:

score: 0
Accepted
time: 6ms
memory: 4172kb

input:

15
0.739
0.448
0.842
0.564
0.457
0.406
0.767
0.769
0.357
0.852
0.721
0.826
0.228
0.122
0.512

output:

1845.8272349

result:

ok found '1845.8272349', expected '1845.8272349', error '0.0000000'

Test #5:

score: 0
Accepted
time: 4ms
memory: 3772kb

input:

14
0.521
0.652
0.578
0.388
0.81
0.813
0.477
0.829
0.491
0.716
0.288
0.383
0.758
0.848

output:

388.9970662

result:

ok found '388.9970662', expected '388.9970662', error '0.0000000'

Test #6:

score: 0
Accepted
time: 16ms
memory: 6432kb

input:

17
0.209
0.155
0.691
0.87
0.145
0.102
0.332
0.487
0.685
0.478
0.675
0.315
0.661
0.116
0.257
0.801
0.495

output:

11037.9445409

result:

ok found '11037.9445409', expected '11037.9445409', error '0.0000000'

Test #7:

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

input:

7
0.539
0.175
0.778
0.453
0.391
0.516
0.518

output:

23.1793180

result:

ok found '23.1793180', expected '23.1793180', error '0.0000000'

Test #8:

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

input:

14
0.49
0.211
0.349
0.33
0.43
0.71
0.577
0.238
0.521
0.613
0.528
0.63
0.4
0.294

output:

1102.8643059

result:

ok found '1102.8643059', expected '1102.8643059', error '0.0000000'

Test #9:

score: 0
Accepted
time: 11ms
memory: 4676kb

input:

16
0.564
0.338
0.674
0.81
0.12
0.171
0.692
0.455
0.423
0.297
0.773
0.178
0.428
0.822
0.471
0.506

output:

12659.1052855

result:

ok found '12659.1052855', expected '12659.1052855', error '0.0000000'

Test #10:

score: 0
Accepted
time: 3ms
memory: 3956kb

input:

12
0.236
0.652
0.797
0.853
0.377
0.48
0.445
0.127
0.231
0.893
0.26
0.334

output:

960.9267330

result:

ok found '960.9267330', expected '960.9267330', error '0.0000000'

Test #11:

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

input:

15
0.441
0.114
0.363
0.838
0.408
0.147
0.156
0.324
0.37
0.797
0.539
0.143
0.465
0.491
0.413

output:

912.5201799

result:

ok found '912.5201799', expected '912.5201799', error '0.0000000'

Test #12:

score: 0
Accepted
time: 6ms
memory: 4200kb

input:

15
0.415
0.35
0.648
0.155
0.183
0.297
0.828
0.771
0.703
0.196
0.178
0.633
0.859
0.293
0.505

output:

6347.3844128

result:

ok found '6347.3844128', expected '6347.3844128', error '0.0000000'

Test #13:

score: 0
Accepted
time: 306ms
memory: 28000kb

input:

20
0.285
0.478
0.189
0.427
0.711
0.68
0.765
0.302
0.383
0.313
0.5
0.849
0.318
0.406
0.157
0.498
0.709
0.526
0.314
0.507

output:

92303.2113846

result:

ok found '92303.2113846', expected '92303.2113846', error '0.0000000'

Test #14:

score: 0
Accepted
time: 308ms
memory: 28096kb

input:

20
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.5
0.9
0.9
0.9
0.9
0.9
0.9
0.9
0.9
0.9

output:

74234415.6750940

result:

ok found '74234415.6750940', expected '74234415.6743832', error '0.0000000'

Test #15:

score: 0
Accepted
time: 317ms
memory: 28048kb

input:

20
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.9
0.9
0.9
0.9
0.9
0.9
0.9
0.9
0.9
0.9

output:

194776950.7646556

result:

ok found '194776950.7646556', expected '194776950.7616470', error '0.0000000'