QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#197686#3518. Final StandingsIsaacMoris#AC ✓7ms4192kbC++141.5kb2023-10-02 18:23:242023-10-02 18:23:24

Judging History

This is the latest submission verdict.

  • [2023-10-02 18:23:24]
  • Judged
  • Verdict: AC
  • Time: 7ms
  • Memory: 4192kb
  • [2023-10-02 18:23:24]
  • Submitted

answer

#include<iostream>
#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 100 + 5, inf = 2e9;
ld dp[N][N];
int vis[N][N], tc;
ld d[N], s[N];
int cnt[N];

ld solve(int player, int i, int rem, vector<int> &problems) {
    if (rem <= 0)return 0;
    if (i == problems.size()) {
        return 1;
    }
    ld &ans = dp[i][rem];
    if (vis[i][rem] == tc)return ans;
    vis[i][rem] = tc;
    ld solvePro = s[player] * d[problems[i]];
    ans = solve(player, i + 1, rem - 1, problems) * solvePro + (1 - solvePro) * solve(player, i + 1, rem, problems);
    return ans;
}

void doWork() {
    int t, p;
    cin >> t >> p;
    for (int i = 0; i + 1 < t; i++) {
        cin >> s[i];
    }
    for (int i = 0; i < p; i++) {
        cin >> d[i];
    }

    ld ans = 1;
    vector<vector<int> > a;

    for (int i = 0; i < t; i++) {
        a.push_back({});
        for (int j = 0; j < p; j++) {
            char c;
            cin >> c;
            if (c == 'X') {
                cnt[i]++;
            } else if (c == '?') {
                a[i].push_back(j);
            }
        }
    }
    for (int i = 0; i + 1 < t; i++) {
        tc++;
        ans *= solve(i, 0, cnt[t - 1] - cnt[i] + 1, a[i]);
    }
    cout << fixed << setprecision(9) << ans;
}

int main() {
    IO
    int t = 1;
    //   cin >> t;
    for (int i = 1; i <= t; i++) {
        //  cout << "Case #" << i << ": ";
        doWork();
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3852kb

input:

3 3
0.95 0.95
0.95 0.95 0.95
? ? ?
X X -
X X -

output:

0.264908109

result:

ok found '0.2649081', expected '0.2649080', error '0.0000001'

Test #2:

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

input:

2 5
0.5
0.1 0.2 0.3 0.4 0.5
? ? ? ? ?
X - - - -

output:

0.838762500

result:

ok found '0.8387625', expected '0.8387625', error '0.0000000'

Test #3:

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

input:

2 2
0.9995
0.3 0.7
? X
X -

output:

0.700150000

result:

ok found '0.7001500', expected '0.7001500', error '0.0000000'

Test #4:

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

input:

10 10
0.123 0.321 0.456 0.654 0.789 0.987 0.00001 0.999 1.0
1.0 0.0 1.0 0.0 0.333 0.333 1.0 0.0 1.0 0.0
? ? ? - ? ? ? ? ? ?
? ? ? ? ? X ? ? ? ?
? - ? - - ? X ? - ?
? X ? ? - ? ? ? ? ?
- - - - - - X - - -
? ? ? ? - ? ? ? X ?
? - - ? X X ? ? - ?
? ? ? ? ? ? ? ? - ?
- ? - ? ? ? - - - ?
- X - X - - X - ...

output:

0.436857692

result:

ok found '0.4368577', expected '0.4368577', error '0.0000000'

Test #5:

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

input:

100 100
0.689155 0.168240 0.530088 0.942735 0.768589 0.412675 0.644574 0.563462 0.328203 0.190895 0.791336 0.222512 0.689632 0.579885 0.572048 0.608610 0.092101 0.692957 0.830000 0.260008 0.176340 0.320461 0.988391 0.200428 0.802988 0.470834 0.782480 0.555422 0.215995 0.039138 0.886394 0.024748 0.69...

output:

0.017598431

result:

ok found '0.0175984', expected '0.0175984', error '0.0000000'

Test #6:

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

input:

100 100
0.739154 0.896819 0.389388 0.848565 0.594443 0.276015 0.206422 0.712795 0.365333 0.476042 0.197904 0.348222 0.578902 0.142333 0.479748 0.350042 0.919599 0.139169 0.414150 0.593798 0.916769 0.134246 0.577282 0.225321 0.099476 0.560128 0.066144 0.670162 0.754154 0.804760 0.770396 0.163091 0.55...

output:

0.918500645

result:

ok found '0.9185006', expected '0.9185006', error '0.0000000'

Test #7:

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

input:

5 10
0.242538 0.704492 0.693277 0.287680
0.803364 0.395923 0.978611 0.252482 0.742638 0.797737 0.298886 0.518122 0.712812 0.039091
? ? - X - - - ? X -
X ? X - - X ? X ? -
X - - ? - X - X - -
? X - ? X - ? X X -
- X X - - X - X X -

output:

0.724258125

result:

ok found '0.7242581', expected '0.7242581', error '0.0000000'

Test #8:

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

input:

5 10
0.967964 0.005081 0.611507 0.904663
0.299430 0.378219 0.566297 0.251130 0.315192 0.364325 0.267384 0.411746 0.750870 0.285207
- - - ? - X ? - ? X
X - X - ? - - ? ? ?
X X ? - ? - ? ? X -
- - ? - - X - ? X X
X X - - X X X X - X

output:

1.000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #9:

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

input:

5 10
0.905411 0.671157 0.488513 0.226860
0.430025 0.027177 0.963820 0.109811 0.653668 0.148091 0.949071 0.189172 0.918600 0.434530
X - ? X ? - X ? X X
? - ? ? - - X - ? -
X - X ? - X - - - -
X X ? ? ? - X X ? ?
- X - - - X - X X X

output:

0.036941360

result:

ok found '0.0369414', expected '0.0369414', error '0.0000000'

Test #10:

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

input:

1 4

0.2 0.3 0.4 0.5
X X - -

output:

1.000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #11:

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

input:

2 1
0.6
0.9
?
-

output:

0.460000000

result:

ok found '0.4600000', expected '0.4600000', error '0.0000000'

Test #12:

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

input:

2 100
0.991921
0.998158 0.994156 0.998807 0.999717 0.990088 0.996412 0.996480 0.995090 0.993043 0.990610 0.992582 0.999043 0.990912 0.994159 0.994806 0.994192 0.990842 0.990886 0.995926 0.993143 0.993564 0.999147 0.999581 0.997420 0.993865 0.992056 0.994833 0.994969 0.991073 0.994468 0.990729 0.9926...

output:

0.000529349

result:

ok found '0.0005293', expected '0.0005293', error '0.0000000'

Test #13:

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

input:

3 100
0.608543 0.589703
0.737298 0.707906 0.778506 0.716552 0.748223 0.819207 0.834997 0.927112 0.894731 0.728533 0.830628 0.801969 0.875098 0.536811 0.710838 0.505515 0.972584 0.873987 0.878728 0.536656 0.830684 0.811442 0.515273 0.698014 0.919090 0.709101 0.994148 0.852719 0.793287 0.709344 0.8256...

output:

0.746373103

result:

ok found '0.7463731', expected '0.7463731', error '0.0000000'

Test #14:

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

input:

100 100
0.000014 0.000002 0.000006 0.000022 0.000020 0.000026 0.000004 0.000012 0.000001 0.000026 0.000004 0.000005 0.000019 0.000015 0.000028 0.000013 0.000027 0.000015 0.000021 0.000018 0.000030 0.000003 0.000015 0.000015 0.000016 0.000026 0.000022 0.000024 0.000007 0.000018 0.000013 0.000028 0.00...

output:

0.999998458

result:

ok found '0.9999985', expected '0.9999985', error '0.0000000'

Test #15:

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

input:

100 100
0.000001 0.000000 0.000000 0.000001 0.000001 0.000002 0.000000 0.000001 0.000000 0.000002 0.000000 0.000000 0.000001 0.000001 0.000002 0.000001 0.000002 0.000001 0.000001 0.000001 0.000002 0.000000 0.000001 0.000001 0.000001 0.000002 0.000001 0.000002 0.000000 0.000001 0.000001 0.000002 0.00...

output:

0.999999995

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #16:

score: 0
Accepted
time: 7ms
memory: 4144kb

input:

100 100
0.863753 0.764225 0.798073 0.933327 0.920291 0.964108 0.782574 0.852625 0.758305 0.966392 0.780157 0.793895 0.905184 0.874969 0.986522 0.860725 0.976363 0.872031 0.926096 0.900000 0.995896 0.776961 0.877855 0.872115 0.884298 0.967287 0.930474 0.952758 0.805131 0.903976 0.855482 0.982786 0.75...

output:

0.999995466

result:

ok found '0.9999955', expected '0.9999955', error '0.0000000'

Test #17:

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

input:

100 100
0.455013 0.056899 0.192291 0.733306 0.681165 0.856431 0.130297 0.410500 0.033220 0.865567 0.120628 0.175581 0.620735 0.499877 0.946087 0.442901 0.905451 0.488122 0.704383 0.600001 0.983584 0.107843 0.511419 0.488460 0.537192 0.869146 0.721896 0.811033 0.220526 0.615902 0.421927 0.931142 0.03...

output:

0.000000000

result:

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

Test #18:

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

input:

100 100
0.455013 0.056899 0.192291 0.733306 0.681165 0.856431 0.130297 0.410500 0.033220 0.865567 0.120628 0.175581 0.620735 0.499877 0.946087 0.442901 0.905451 0.488122 0.704383 0.600001 0.983584 0.107843 0.511419 0.488460 0.537192 0.869146 0.721896 0.811033 0.220526 0.615902 0.421927 0.931142 0.03...

output:

0.000012006

result:

ok found '0.0000120', expected '0.0000120', error '0.0000000'

Test #19:

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

input:

100 98
0.468467 0.603265 0.455013 0.056899 0.192291 0.733306 0.681165 0.856431 0.130297 0.410500 0.033220 0.865567 0.120628 0.175581 0.620735 0.499877 0.946087 0.442901 0.905451 0.488122 0.704383 0.600001 0.983584 0.107843 0.511419 0.488460 0.537192 0.869146 0.721896 0.811033 0.220526 0.615902 0.421...

output:

1.000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #20:

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

input:

100 98
0.773885 0.887121 0.242746 0.707466 0.668545 0.231465 0.213497 0.106659 0.321201 0.231399 0.550282 0.240498 0.755269 0.363372 0.009735 0.564173 0.774967 0.613985 0.564827 0.463059 0.306565 0.837471 0.145482 0.998446 0.584806 0.637623 0.165856 0.549593 0.218482 0.241157 0.178319 0.222142 0.221...

output:

1.000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #21:

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

input:

100 100
0.048549 0.141493 0.133709 0.046293 0.042699 0.021332 0.064240 0.046280 0.110056 0.048100 0.151054 0.072674 0.001947 0.112835 0.154993 0.122797 0.112965 0.092612 0.061313 0.167494 0.029096 0.199689 0.116961 0.127525 0.033171 0.109919 0.043696 0.048231 0.035664 0.044428 0.044379 0.010996 0.12...

output:

0.000000000

result:

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

Test #22:

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

input:

100 100
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.00...

output:

1.000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'