QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#197922#3518. Final Standingsbeshoyhany#AC ✓14ms13636kbC++202.5kb2023-10-02 21:53:542023-10-02 21:53:56

Judging History

This is the latest submission verdict.

  • [2023-10-02 21:53:56]
  • Judged
  • Verdict: AC
  • Time: 14ms
  • Memory: 13636kb
  • [2023-10-02 21:53:54]
  • Submitted

answer

#include<bits/stdc++.h>

#define ll long long
#define pp push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define ld long double
#define PI acos(-1)
#define sin(a) sin((a)*PI/180)
#define cos(a) cos((a)*PI/180)
#define ones(x) __builtin_popcountll(x)
//#define int ll

using namespace std;

void Drakon() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef Clion
    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}

unsigned long long inf = 1e10;
const double EPS = 1e-6;
const int MOD = 1000000007, N = 105, LOG = 25;

ll gcd(ll x, ll y) {
    return y ? gcd(y, x % y) : x;
}

ll lcm(ll a, ll b) {
    return (a * b) / __gcd(a, b);
}

ll mul(const ll &a, const ll &b) {
    return (a % MOD + MOD) * (b % MOD + MOD) % MOD;
}

ll add(const ll &a, const ll &b) {
    return (a + b + 2 * MOD) % MOD;
}

ll pw(ll x, ll y) {
    ll ret = 1;
    while (y > 0) {
        if (y % 2 == 0) {
            x = mul(x, x);
            y = y / 2;
        } else {
            ret = mul(ret, x);
            y = y - 1;
        }
    }
    return ret;
}

int t, p;
vector<double>s, d;
vector<char> state[N];
bool vis[N][N][N];
double dp[N][N][N];

double slv(int i, int rem, int team){
    if(rem < 0)return 0;
    if(i == p){
        return (rem == 0);
    }
    double &ret = dp[i][rem][team];
    if(vis[i][rem][team])return ret;
    vis[i][rem][team] = true;

    if(state[team][i] == '?'){
        ret = slv(i + 1, rem, team) * (1 - s[team] * d[i]) + slv(i + 1, rem - 1, team) * s[team] * d[i];
    }
    else if(state[team][i] == '-'){
        ret = slv(i + 1, rem, team);
    }
    else{
        ret = slv(i + 1, rem - 1, team);
    }

    return ret;
}

void solve() {
    cin >> t >> p;
    s.resize(t);
    d.resize(p);
    for (int i = 0; i < t - 1; ++i) {
        cin >> s[i];
    }
    for (int i = 0; i < p; ++i) {
        cin >> d[i];
    }

    int cnt = 0;
    for (int i = 0; i < t; ++i) {
        state[i].resize(p);
        for (int j = 0; j < p; ++j) {
            cin >> state[i][j];
            if(i == t - 1)cnt += state[i][j] == 'X';
        }
    }

    double ans = 1;
    for (int i = 0; i < t - 1; ++i) {
        double tmp = 0;
        for (int j = 0; j <= cnt; ++j) {
            tmp += slv(0, j, i);
        }
        ans *= tmp;
    }
    cout << fixed << setprecision(10) << ans;
}

signed main() {
    Drakon();
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

0.2649081094

result:

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

Test #2:

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

input:

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

output:

0.8387625000

result:

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

Test #3:

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

input:

2 2
0.9995
0.3 0.7
? X
X -

output:

0.7001500000

result:

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

Test #4:

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

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.4368576924

result:

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

Test #5:

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

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.0175984309

result:

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

Test #6:

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

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.9185006448

result:

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

Test #7:

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

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.7242581248

result:

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

Test #8:

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

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.0000000000

result:

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

Test #9:

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

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.0369413602

result:

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

Test #10:

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

input:

1 4

0.2 0.3 0.4 0.5
X X - -

output:

1.0000000000

result:

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

Test #11:

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

input:

2 1
0.6
0.9
?
-

output:

0.4600000000

result:

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

Test #12:

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

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.0005293489

result:

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

Test #13:

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

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.7463731030

result:

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

Test #14:

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

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.9999984581

result:

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

Test #15:

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

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.9999999951

result:

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

Test #16:

score: 0
Accepted
time: 14ms
memory: 13636kb

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.9999954660

result:

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

Test #17:

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

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.0000000000

result:

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

Test #18:

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

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.0000120060

result:

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

Test #19:

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

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.0000000000

result:

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

Test #20:

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

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.0000000000

result:

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

Test #21:

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

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.0000000000

result:

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

Test #22:

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

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.0000000000

result:

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