QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#24483#2896. Black and WhiteWIOAC ✓220ms31536kbC++141.1kb2022-03-31 03:19:372022-04-30 05:53:04

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 05:53:04]
  • 评测
  • 测评结果:AC
  • 用时:220ms
  • 内存:31536kb
  • [2022-03-31 03:19:37]
  • 提交

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'