QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#24053 | #2896. Black and White | Emiya_Kiritsugu | AC ✓ | 342ms | 28096kb | C++17 | 2.0kb | 2022-03-25 17:42:55 | 2022-04-30 04:49:22 |
Judging History
answer
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <iostream>
#include <string.h>
using namespace std;
const int INF = INT_MAX >> 1;
const int MOD = 1'000'000'000 + 7;
int N;
double dfs(const int ST, vector<double> &expec, vector<double> const &faceUp, vector<double> const &faceDown) {
if(expec[ST] >= 0) {
return expec[ST];
}
double psum = 0.0;
double Esum = 0.0;
for(int i = 0; i < N; ++i) {
if(ST & (1 << i)) {
int afterKick = (ST ^ (1 << i));
double curP = faceUp[1<<i] * faceDown[afterKick] + faceDown[1<<i] * faceUp[afterKick];
Esum += curP * dfs(afterKick, expec, faceUp, faceDown);
psum += curP;
}
}
expec[ST] = (1 + Esum) / psum;
return expec[ST];
}
void solve(int testCase) {
scanf("%d", &N);
vector<double> ps(N, 0.0);
for(int i = 0; i < N; ++i)
scanf("%lf", &ps[i]);
// if(2 == N) {
// return;
// }
const int MAXSZ = 1 << N;
vector<double> expec(MAXSZ, -1);
for(int i = 0; i < N; ++i) {
for(int j = i + 1; j < N; ++j) {
expec[(1 << i) | (1 << j) ] = 0;
}
}
vector<double> faceUp(MAXSZ, 1), faceDown(MAXSZ, 1);
for(int i = 0; i < N; ++i) {
for(int state = 1; state < MAXSZ; ++state) {
if(state & (1 << i)) {
faceUp[state] *= ps[i];
faceDown[state] *= (1 - ps[i]);
}
}
}
dfs(MAXSZ - 1, expec, faceUp, faceDown);
printf("%.7lf\n", expec[MAXSZ-1]);
}
bool multi = false;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
if (multi) {
cin >> t;
}
for (int i = 1; i <= t; ++i) {
solve(i);
// cout << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3860kb
input:
2 0.616 0.689
output:
0.0000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #2:
score: 0
Accepted
time: 342ms
memory: 27824kb
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: 1ms
memory: 3760kb
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: 4172kb
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: 4ms
memory: 3772kb
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: 16ms
memory: 6432kb
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: 2ms
memory: 3712kb
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: 0ms
memory: 3776kb
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: 11ms
memory: 4676kb
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: 3ms
memory: 3956kb
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: 0ms
memory: 4196kb
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: 6ms
memory: 4200kb
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: 306ms
memory: 28000kb
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: 308ms
memory: 28096kb
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: 317ms
memory: 28048kb
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.7646556
result:
ok found '194776950.7646556', expected '194776950.7616470', error '0.0000000'