QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#24483 | #2896. Black and White | WIO | AC ✓ | 220ms | 31536kb | C++14 | 1.1kb | 2022-03-31 03:19:37 | 2022-04-30 05:53:04 |
Judging History
answer
#include<bits/stdc++.h>
#define rp(a,b,c) for(long long a=(b);a<=(c);a++)
#define FILL(x,v) memset(x,v,sizeof(x))
using namespace std;
typedef long long ll;
ll n;
double p[20+5];
double ans[1<<25];
double faceup[1<<25];
double facedown[1<<25];
double dfs(ll ST)
{
if(ans[ST]>=0) return ans[ST];
double psum=0.0;
double esum=0.0;
rp(i,0,n-1)
{
if(ST&(1<<i))
{
ll afterclick = (ST ^ (1<<i));
double curP = faceup[1<<i] * facedown[afterclick] + facedown[1<<i] * faceup[afterclick];
esum+=curP*dfs(afterclick);
psum+=curP;
}
}
return ans[ST] = (1+esum)/psum;
}
int main()
{
cin>>n;
rp(i,0,n-1)
cin>>p[i];
rp(i,0,(1<<n)-1)
{
ans[i]=-1;
}
rp(i,0,n-1)
{
rp(j,i+1,n-1)
{
ans[(1<<i)|(1<<j)]=0;
}
}
rp(i,1,(1<<n)-1)
{
faceup[i]=1;
facedown[i]=1;
}
rp(i,0,n-1)
{
rp(stat,1,(1<<n)-1)
{
if(stat&(1<<i))
{
faceup[stat] *= p[i];
facedown[stat] *= (1-p[i]);
}
}
}
dfs((1<<n)-1);
printf("%.7lf\n",ans[(1<<n)-1]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 7828kb
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: 215ms
memory: 30696kb
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: 3ms
memory: 7852kb
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: 8208kb
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: 5ms
memory: 8136kb
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: 10ms
memory: 14180kb
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: 7860kb
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: 5ms
memory: 7868kb
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: 5ms
memory: 8332kb
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: 7776kb
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: 2ms
memory: 8068kb
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: 2ms
memory: 8164kb
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: 220ms
memory: 31412kb
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: 209ms
memory: 30720kb
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: 202ms
memory: 31536kb
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'