QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#859520 | #2896. Black and White | WeaRD276# | AC ✓ | 299ms | 24432kb | C++20 | 2.4kb | 2025-01-17 20:13:07 | 2025-01-17 20:13:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define x first
#define y second
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
typedef long long ll;
typedef long double db;
//typedef long double LD;
typedef pair<int, int> pii;
typedef pair<db, db> pdd;
typedef pair<ll, ll> pll;
int solve()
{
int n;
if (!(cin >> n))
return 1;
vector<db> p(n);
FOR (i, 0, n)
cin >> p[i];
if (n <= 2)
{
cout << "0\n";
return 0;
}
vector<int> masks;
FOR (i, 1, 1 << n)
{
masks.pb(i);
}
sort(all(masks), [](int l, int r)
{
return popcount((unsigned int)l) < popcount((unsigned int)r);
});
vector<db> dp(1 << n, -1);
for (int mask: masks)
{
int pp = popcount((unsigned int)mask);
if (pp < 3)
continue;
vector<int> in;
FOR (j, 0, n)
{
if (mask & 1 << j)
in.pb(j);
}
if (sz(in) == 3)
{
db pr = 0;
FOR (i, 0, 1 << 3)
{
db cr = 1;
FOR (j, 0, 3)
{
if (i & 1 << j)
cr *= p[in[j]];
else
cr *= (1 - p[in[j]]);
}
if (i != 0 && i != (1 << 3) - 1)
pr += cr;
}
dp[mask] = 1. / pr;
continue;
}
db p1 = 1, p2 = 1;
for (int j: in)
{
p1 *= p[j];
p2 *= (1 - p[j]);
}
db sm = 0;
db smpr = 0;
for (int j: in)
{
db cp1 = p1 / p[j];
db cp2 = p2 / (1 - p[j]);
cp1 *= (1 - p[j]);
cp2 *= p[j];
db pr = cp1 + cp2;
assert(pr <= 1. + 1e-7);
sm += pr;
smpr += pr * (dp[mask ^ (1 << j)] + 1);
}
assert(sm <= 1. + 1e-7);
dp[mask] = (smpr + 1 - sm) / sm;
}
cout << fixed << setprecision(7) << dp.back() << '\n';
return 0;
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int TET = 1e9;
//cin >> TET;
for (int i = 1; i <= TET; i++)
{
if (solve())
{
break;
}
#ifdef ONPC
cerr << "_____________________________\n";
#endif
}
#ifdef ONPC
cerr << "\nfinished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec\n";
#endif
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3968kb
input:
2 0.616 0.689
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #2:
score: 0
Accepted
time: 297ms
memory: 24432kb
input:
20 0.256 0.546 0.617 0.86 0.138 0.282 0.271 0.124 0.238 0.769 0.899 0.214 0.166 0.626 0.876 0.161 0.774 0.891 0.819 0.653
output:
1393404.7887949
result:
ok found '1393404.7887949', expected '1393404.7887950', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
3 0.883 0.132 0.135
output:
1.1155498
result:
ok found '1.1155498', expected '1.1155498', error '0.0000000'
Test #4:
score: 0
Accepted
time: 6ms
memory: 4480kb
input:
15 0.739 0.448 0.842 0.564 0.457 0.406 0.767 0.769 0.357 0.852 0.721 0.826 0.228 0.122 0.512
output:
1845.8272349
result:
ok found '1845.8272349', expected '1845.8272349', error '0.0000000'
Test #5:
score: 0
Accepted
time: 3ms
memory: 4096kb
input:
14 0.521 0.652 0.578 0.388 0.81 0.813 0.477 0.829 0.491 0.716 0.288 0.383 0.758 0.848
output:
388.9970662
result:
ok found '388.9970662', expected '388.9970662', error '0.0000000'
Test #6:
score: 0
Accepted
time: 32ms
memory: 6380kb
input:
17 0.209 0.155 0.691 0.87 0.145 0.102 0.332 0.487 0.685 0.478 0.675 0.315 0.661 0.116 0.257 0.801 0.495
output:
11037.9445409
result:
ok found '11037.9445409', expected '11037.9445409', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 4096kb
input:
7 0.539 0.175 0.778 0.453 0.391 0.516 0.518
output:
23.1793180
result:
ok found '23.1793180', expected '23.1793180', error '0.0000000'
Test #8:
score: 0
Accepted
time: 4ms
memory: 4200kb
input:
14 0.49 0.211 0.349 0.33 0.43 0.71 0.577 0.238 0.521 0.613 0.528 0.63 0.4 0.294
output:
1102.8643059
result:
ok found '1102.8643059', expected '1102.8643059', error '0.0000000'
Test #9:
score: 0
Accepted
time: 16ms
memory: 5120kb
input:
16 0.564 0.338 0.674 0.81 0.12 0.171 0.692 0.455 0.423 0.297 0.773 0.178 0.428 0.822 0.471 0.506
output:
12659.1052855
result:
ok found '12659.1052855', expected '12659.1052855', error '0.0000000'
Test #10:
score: 0
Accepted
time: 1ms
memory: 4224kb
input:
12 0.236 0.652 0.797 0.853 0.377 0.48 0.445 0.127 0.231 0.893 0.26 0.334
output:
960.9267330
result:
ok found '960.9267330', expected '960.9267330', error '0.0000000'
Test #11:
score: 0
Accepted
time: 7ms
memory: 4480kb
input:
15 0.441 0.114 0.363 0.838 0.408 0.147 0.156 0.324 0.37 0.797 0.539 0.143 0.465 0.491 0.413
output:
912.5201799
result:
ok found '912.5201799', expected '912.5201799', error '0.0000000'
Test #12:
score: 0
Accepted
time: 7ms
memory: 4480kb
input:
15 0.415 0.35 0.648 0.155 0.183 0.297 0.828 0.771 0.703 0.196 0.178 0.633 0.859 0.293 0.505
output:
6347.3844128
result:
ok found '6347.3844128', expected '6347.3844128', error '0.0000000'
Test #13:
score: 0
Accepted
time: 299ms
memory: 24424kb
input:
20 0.285 0.478 0.189 0.427 0.711 0.68 0.765 0.302 0.383 0.313 0.5 0.849 0.318 0.406 0.157 0.498 0.709 0.526 0.314 0.507
output:
92303.2113846
result:
ok found '92303.2113846', expected '92303.2113846', error '0.0000000'
Test #14:
score: 0
Accepted
time: 294ms
memory: 24432kb
input:
20 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.5 0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.9
output:
74234415.6750940
result:
ok found '74234415.6750940', expected '74234415.6743832', error '0.0000000'
Test #15:
score: 0
Accepted
time: 299ms
memory: 24432kb
input:
20 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.9
output:
194776950.7646554
result:
ok found '194776950.7646554', expected '194776950.7616470', error '0.0000000'