QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#197922 | #3518. Final Standings | beshoyhany# | AC ✓ | 14ms | 13636kb | C++20 | 2.5kb | 2023-10-02 21:53:54 | 2023-10-02 21:53:56 |
Judging History
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'