QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#225171#3518. Final Standingshagry#AC ✓16ms22764kbC++141.8kb2023-10-24 02:16:032023-10-24 02:16:03

Judging History

This is the latest submission verdict.

  • [2023-10-24 02:16:03]
  • Judged
  • Verdict: AC
  • Time: 16ms
  • Memory: 22764kb
  • [2023-10-24 02:16:03]
  • Submitted

answer

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define MP make_pair
#define all(x) x.begin(),x.end()
#define Hagry ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);

using namespace std;
using ll = long long;
using ld = long double;
using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vector<int>>;

const int OO = 1e9 + 5;
const int N = 100 + 5;
char board[N][N];
int cnt[N], t, p;
ld dp[N][N][N], s[N], d[N];
bool vis[N][N][N];
int vid;

ld solve(int i, int rem, int team) {
    if (rem == 0)
        return 1;
    if (i == p)
        return 0;

    ld &ret = dp[i][rem][team];
    if (vis[i][rem][team] == vid)
        return ret;
    vis[i][rem][team] = vid;

    if (board[team][i] == 'X')
        ret = solve(i + 1, rem - 1, team);
    else if (board[team][i] == '-')
        ret = solve(i + 1, rem, team);
    else{
        ld get = s[team] * d[i];
        ret = get * solve(i+1, rem-1, team);
        ret += (1.0 - get) * solve(i+1, rem, team);
    }
    return ret;
}

void TC() {
    ++vid;
    cin >> t >> p;
    for (int i = 0; i < t - 1; ++i)
        cin >> s[i];
    for (int i = 0; i < p; ++i)
        cin >> d[i];

    for (int i = 0; i < t; ++i) {
        for (int j = 0; j < p; ++j) {
            cin >> board[i][j];
            cnt[i] += board[i][j] == 'X';
        }
    }

    ld ans = 1;
    for (int i = 0; i < t - 1; ++i) {
        ans *= (ld)1.0 - solve(0,cnt[t-1]+1, i);
    }

    cout << fixed << setprecision(9) << ans;
}

int32_t main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif
    Hagry
    int tt = 1;
//    cin >> tt;
    while (tt--) {
        TC();
        cout << '\n';
    }
    return 0;
}

詳細信息

Test #1:

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

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: 3936kb

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: 1ms
memory: 6044kb

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: 6056kb

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: 6ms
memory: 21284kb

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: 3ms
memory: 19668kb

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: 1ms
memory: 5972kb

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: 1ms
memory: 5996kb

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: 1ms
memory: 5876kb

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: 3892kb

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: 1ms
memory: 5924kb

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: 22440kb

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: 3ms
memory: 20944kb

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: 0ms
memory: 16692kb

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: 2ms
memory: 16804kb

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: 16ms
memory: 18296kb

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: 2ms
memory: 16760kb

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: 8ms
memory: 17776kb

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: 22764kb

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: 0ms
memory: 22452kb

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: 0ms
memory: 17356kb

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: 5ms
memory: 17792kb

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'