QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#859520#2896. Black and WhiteWeaRD276#AC ✓299ms24432kbC++202.4kb2025-01-17 20:13:072025-01-17 20:13:23

Judging History

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

  • [2025-01-17 20:13:23]
  • 评测
  • 测评结果:AC
  • 用时:299ms
  • 内存:24432kb
  • [2025-01-17 20:13:07]
  • 提交

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'