QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#197987 | #3518. Final Standings | Gamal74# | AC ✓ | 11ms | 4300kb | C++20 | 2.3kb | 2023-10-02 23:13:15 | 2023-10-02 23:13:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define fi first
#define se second
#define pp push_back
#define all(x) (x).begin(), (x).end()
#define Ones(n) __builtin_popcount(n)
#define endl '\n'
#define mem(arrr, xx) memset(arrr,xx,sizeof arrr)
//#define int long long
#define debug(x) cout << (#x) << " = " << x << endl
void Gamal() {
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
}
int dx[] = {+0, +0, -1, +1, +1, +1, -1, -1};
int dy[] = {-1, +1, +0, +0, +1, -1, +1, -1};
const double EPS = 1e-9;
const ll OO = 0X3F3F3F3F3F3F3F3F;
const int N = 100 + 5, INF = INT_MAX, MOD = 1e9 + 7, LOG = 20;
int p, vis[N][N], vid;
ld dp[N][N];
vector<ld> cur;
ld slv(int i, int rem) {
if (rem < 0)return 0;
if (i == cur.size())return 1;
ld &ret = dp[i][rem];
if (vis[i][rem] == vid)
return ret;
vis[i][rem] = vid;
ret = (1 - cur[i]) * slv(i + 1, rem) + cur[i] * slv(i + 1, rem - 1);
return ret;
}
void solve() {
int t;
cin >> t >> p;
t--;
vector<ld> v(t);
for (int i = 0; i < t; ++i) {
cin >> v[i];
}
vector<ld> d(p);
for (int i = 0; i < p; ++i) {
cin >> d[i];
}
vector<vector<ld>> prob(t);
vector<int> solved(t);
for (int i = 0; i < t; ++i) {
for (int j = 0; j < p; ++j) {
char c;
cin >> c;
if (c == 'X') {
solved[i]++;
} else if (c == '?') {
prob[i].push_back(d[j] * v[i]);
}
}
}
int cnt = 0;
for (int i = 0; i < p; ++i) {
char c;
cin >> c;
cnt += c == 'X';
}
ld ans = 1;
for (int i = 0; i < t; ++i) {
if (solved[i] > cnt) {
ans = 0;
break;
}
cur = prob[i];
vid++;
ans *= slv(0, cnt - solved[i]);
}
cout << fixed << setprecision(7) << ans;
}
signed main() {
Gamal();
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: 3896kb
input:
3 3 0.95 0.95 0.95 0.95 0.95 ? ? ? X X - X X -
output:
0.2649081
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.8387625
result:
ok found '0.8387625', expected '0.8387625', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
2 2 0.9995 0.3 0.7 ? X X -
output:
0.7001500
result:
ok found '0.7001500', expected '0.7001500', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3908kb
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.4368577
result:
ok found '0.4368577', expected '0.4368577', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4076kb
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.0175984
result:
ok found '0.0175984', expected '0.0175984', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 4116kb
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.9185006
result:
ok found '0.9185006', expected '0.9185006', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3900kb
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.7242581
result:
ok found '0.7242581', expected '0.7242581', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3852kb
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.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3784kb
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.0369414
result:
ok found '0.0369414', expected '0.0369414', error '0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
1 4 0.2 0.3 0.4 0.5 X X - -
output:
1.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
2 1 0.6 0.9 ? -
output:
0.4600000
result:
ok found '0.4600000', expected '0.4600000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 4016kb
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.0005293
result:
ok found '0.0005293', expected '0.0005293', error '0.0000000'
Test #13:
score: 0
Accepted
time: 1ms
memory: 4052kb
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.7463731
result:
ok found '0.7463731', expected '0.7463731', error '0.0000000'
Test #14:
score: 0
Accepted
time: 1ms
memory: 4260kb
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.9999985
result:
ok found '0.9999985', expected '0.9999985', error '0.0000000'
Test #15:
score: 0
Accepted
time: 1ms
memory: 4260kb
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:
1.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #16:
score: 0
Accepted
time: 11ms
memory: 4124kb
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.9999955
result:
ok found '0.9999955', expected '0.9999955', error '0.0000000'
Test #17:
score: 0
Accepted
time: 0ms
memory: 4284kb
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.0000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #18:
score: 0
Accepted
time: 8ms
memory: 4300kb
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.0000120
result:
ok found '0.0000120', expected '0.0000120', error '0.0000000'
Test #19:
score: 0
Accepted
time: 1ms
memory: 4000kb
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.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #20:
score: 0
Accepted
time: 1ms
memory: 4080kb
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.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #21:
score: 0
Accepted
time: 0ms
memory: 4012kb
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.0000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #22:
score: 0
Accepted
time: 0ms
memory: 4184kb
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.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'