QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#225173#2913. Archery AccuracyPetroTarnavskyiAC ✓184ms5268kbC++172.2kb2023-10-24 02:38:082023-10-24 02:38:09

Judging History

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

  • [2023-10-24 02:38:09]
  • 评测
  • 测评结果:AC
  • 用时:184ms
  • 内存:5268kb
  • [2023-10-24 02:38:08]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#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--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

vector<db> Gauss(vector<vector<db>> a)
{
	int n = SZ(a);
	if(n == 0)
		return {};
	int m = SZ(a[0]) - 1;//number of variables
	assert(n >= m);
	
	int vars = m;
	FOR(i, 0, m)
	{
		if (a[i][i] == 0)
		{
			int row = i;
			FOR(k, i + 1, n)
			{
				if (abs(a[row][i]) < abs(a[k][i]))
					row = k;
			}
			if(row == -1)
			{
				vars--;
				continue;
			}
			swap(a[i], a[row]);
		}
		db d = 1 / a[i][i];
		FOR(k, i + 1, n)
		{
			db c = a[k][i] * d;
			FOR(j, 0, m + 1)
				a[k][j] -= c * a[i][j];
		}
	}
	FOR(i, vars, n)
		if(a[i].back() != 0)
			cout << "No solution\n";
	vector<db> x(m);
	RFOR(i, m, 0)
	{
		x[i] = a[i].back();
		FOR(j, i + 1, m)
			x[i] -= a[i][j] * x[j];
		x[i] = x[i] / a[i][i];
	}
	return x;
}

const int N = 17;

db dp[1 << N];
db r1[N + 1][N + 1];
db r2[N + 1][N + 1];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(15);
	
	int n;
	cin >> n;
	vector<db> p(n);
	FOR (i, 0, n)
		cin >> p[i];
	VI s(n + 1, 0);
	FOR (i, 0, n)
		cin >> s[i + 1];
	
	FOR (i, 0, n)
	{
		FOR (j, 0, n)
		{
			int sz = 2 * s[i + 1];
			vector<vector<db>> a(sz, vector<db>(sz + 1));
			FOR (k, 0, sz - 1)
			{
				a[k][k] = -1;
				a[k][k + 1] = p[j];
				if (k)
				{
					a[k][k - 1] = 1 - p[j];
				}
				a[k][sz] = 0;
			}
			a[sz - 1][sz - 1] = 1;
			a[sz - 1][sz] = 1;
			auto res = Gauss(a);
			int x = (-s[i + 1]) + 1;
			r1[i][j] = res[s[i] - x];
			r2[i][j] = res[-s[i] - x];
		}
	}
	
	
	dp[0] = 1;
	FOR (i, 0, 1 << n)
	{
		int idx = __builtin_popcount(i);	
		FOR (j, 0, n)
		{
			if (i & (1 << j))
				continue;
			
			db P = r1[idx][j] * dp[i] + r2[idx][j] * (1 - dp[i]);
			if (P > dp[i | (1 << j)])
			{
				dp[i | (1 << j)] = P;
			}
		}
	}
	cout << dp[(1 << n) - 1] << '\n';
	
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 92ms
memory: 5120kb

input:

17
0.49
0.45
0.50
0.47
0.50
0.50
0.50
0.50
0.50
0.50
0.50
0.50
0.49
0.50
0.49
0.50
0.49
15
16
17
18
19
20
26
29
86
88
89
93
95
96
97
98
100

output:

0.451642215269408

result:

ok found '0.4516422', expected '0.4516422', error '0.0000000'

Test #2:

score: 0
Accepted
time: 125ms
memory: 5224kb

input:

17
0.50
0.50
0.50
0.50
0.47
0.49
0.50
0.50
0.50
0.49
0.39
0.51
0.46
0.49
0.50
0.50
0.50
1
65
67
68
69
70
71
78
79
84
90
91
94
95
96
97
100

output:

0.580935013419834

result:

ok found '0.5809350', expected '0.5809350', error '0.0000000'

Test #3:

score: 0
Accepted
time: 110ms
memory: 5048kb

input:

17
0.50
0.47
0.50
0.43
0.43
0.50
0.50
0.50
0.46
0.50
0.28
0.50
0.50
0.49
0.50
0.42
0.48
7
9
10
11
14
17
18
77
78
79
84
85
87
89
98
99
100

output:

0.403900335870246

result:

ok found '0.4039003', expected '0.4039003', error '0.0000000'

Test #4:

score: 0
Accepted
time: 73ms
memory: 5024kb

input:

17
0.50
0.50
0.50
0.47
0.50
0.52
0.50
0.50
0.50
0.50
0.50
0.50
0.50
0.50
0.48
0.50
0.49
3
4
6
7
8
9
10
11
15
73
75
76
80
81
82
89
100

output:

0.860952342152676

result:

ok found '0.8609523', expected '0.8609523', error '0.0000000'

Test #5:

score: 0
Accepted
time: 102ms
memory: 5236kb

input:

17
0.35
0.47
0.46
0.48
0.50
0.46
0.50
0.49
0.50
0.47
0.45
0.54
0.50
0.50
0.50
0.50
0.43
1
2
6
8
10
66
81
82
83
84
86
87
88
90
91
98
100

output:

0.776088213912349

result:

ok found '0.7760882', expected '0.7760882', error '0.0000000'

Test #6:

score: 0
Accepted
time: 55ms
memory: 5100kb

input:

17
0.50
0.50
0.50
0.50
0.47
0.50
0.50
0.46
0.50
0.49
0.46
0.50
0.50
0.49
0.50
0.5
0.49
1
7
9
10
12
14
15
16
18
19
81
83
84
85
86
87
100

output:

0.475040920128263

result:

ok found '0.4750409', expected '0.4750409', error '0.0000000'

Test #7:

score: 0
Accepted
time: 94ms
memory: 4988kb

input:

17
0.44
0.47
0.50
0.49
0.47
0.81
0.68
0.41
0.50
0.44
0.50
0.50
0.46
0.47
0.49
0.19
0.48
3
7
10
12
13
15
19
20
81
83
94
95
96
97
98
99
100

output:

0.986376391643103

result:

ok found '0.9863764', expected '0.9863764', error '0.0000000'

Test #8:

score: 0
Accepted
time: 82ms
memory: 5008kb

input:

17
0.46
0.50
0.50
0.36
0.43
0.42
0.40
0.51
0.50
0.37
0.50
0.49
0.50
0.52
0.50
0.50
0.50
2
3
4
5
6
67
68
69
73
75
76
82
85
86
87
88
100

output:

0.884537941723264

result:

ok found '0.8845379', expected '0.8845379', error '0.0000000'

Test #9:

score: 0
Accepted
time: 100ms
memory: 5044kb

input:

17
0.36
0.50
0.50
0.49
0.48
0.50
0.6
0.49
0.50
0.50
0.50
0.50
0.50
0.40
0.50
0.50
0.40
1
2
14
15
17
18
19
86
87
88
92
93
94
95
96
97
100

output:

0.929999999999000

result:

ok found '0.9300000', expected '0.9300000', error '0.0000000'

Test #10:

score: 0
Accepted
time: 80ms
memory: 5028kb

input:

17
0.45
0.49
0.45
0.49
0.50
0.47
0.51
0.49
0.50
0.49
0.50
0.50
0.48
0.50
0.50
0.47
0.50
16
17
26
27
29
30
31
32
33
35
36
87
92
93
94
95
100

output:

0.845433066857484

result:

ok found '0.8454331', expected '0.8454331', error '0.0000000'

Test #11:

score: 0
Accepted
time: 107ms
memory: 5180kb

input:

17
0.63
0.50
0.36
0.49
0.49
0.50
0.50
0.50
0.50
0.30
0.50
0.50
0.52
0.43
0.50
0.52
0.50
1
5
6
7
8
9
69
70
82
84
85
89
90
92
93
94
100

output:

0.997191923295143

result:

ok found '0.9971919', expected '0.9971919', error '0.0000000'

Test #12:

score: 0
Accepted
time: 140ms
memory: 5096kb

input:

17
0.50
0.48
0.50
0.50
0.39
0.50
0.50
0.45
0.49
0.47
0.50
0.49
0.50
0.41
0.27
0.50
0.50
52
53
55
56
75
84
85
86
88
89
92
93
94
95
96
98
100

output:

0.169772515004398

result:

ok found '0.1697725', expected '0.1697725', error '0.0000000'

Test #13:

score: 0
Accepted
time: 146ms
memory: 5144kb

input:

17
0.40
0.49
0.45
0.50
0.50
0.50
0.44
0.34
0.50
0.49
0.50
0.49
0.48
0.48
0.50
0.50
0.50
9
11
12
68
72
87
88
89
90
92
94
95
96
97
98
99
100

output:

0.282704561765083

result:

ok found '0.2827046', expected '0.2827046', error '0.0000000'

Test #14:

score: 0
Accepted
time: 104ms
memory: 5016kb

input:

17
0.50
0.50
0.50
0.50
0.43
0.50
0.50
0.50
0.46
0.50
0.50
0.45
0.50
0.50
0.50
0.49
0.51
3
4
8
13
14
73
83
84
85
86
87
88
90
92
93
94
100

output:

0.813789074256516

result:

ok found '0.8137891', expected '0.8137891', error '0.0000000'

Test #15:

score: 0
Accepted
time: 90ms
memory: 5060kb

input:

17
0.48
0.50
0.50
0.50
0.50
0.38
0.50
0.50
0.50
0.50
0.50
0.50
0.50
0.50
0.48
0.50
0.50
5
7
8
9
10
11
14
15
28
29
87
89
90
91
96
97
100

output:

0.478156391666115

result:

ok found '0.4781564', expected '0.4781564', error '0.0000000'

Test #16:

score: 0
Accepted
time: 110ms
memory: 5268kb

input:

17
0.50
0.50
0.49
0.50
0.47
0.48
0.46
0.50
0.35
0.50
0.50
0.54
0.50
0.36
0.49
0.50
0.51
3
4
18
20
21
22
23
80
87
88
90
91
93
96
98
99
100

output:

0.934674656153137

result:

ok found '0.9346747', expected '0.9346747', error '0.0000000'

Test #17:

score: 0
Accepted
time: 57ms
memory: 5220kb

input:

17
0.50
0.49
0.33
0.50
0.49
0.50
0.50
0.45
0.50
0.49
0.49
0.94
0.50
0.50
0.50
0.50
0.49
1
2
8
23
25
26
27
28
29
33
34
38
39
95
96
99
100

output:

0.994863326681255

result:

ok found '0.9948633', expected '0.9948633', error '0.0000000'

Test #18:

score: 0
Accepted
time: 65ms
memory: 5252kb

input:

17
0.50
0.50
0.34
0.50
0.51
0.50
0.48
0.50
0.50
0.48
0.50
0.50
0.50
0.51
0.49
0.50
0.47
2
3
4
5
6
9
11
12
13
76
79
80
81
92
98
99
100

output:

0.909851928058048

result:

ok found '0.9098519', expected '0.9098519', error '0.0000000'

Test #19:

score: 0
Accepted
time: 26ms
memory: 5268kb

input:

17
0.50
0.50
0.50
0.49
0.46
0.47
0.39
0.48
0.47
0.50
0.49
0.50
0.49
0.48
0.49
0.52
0.41
1
15
16
17
19
20
29
30
31
37
38
39
40
41
43
45
100

output:

0.991124035266483

result:

ok found '0.9911240', expected '0.9911240', error '0.0000000'

Test #20:

score: 0
Accepted
time: 108ms
memory: 5256kb

input:

17
0.50
0.50
0.50
0.50
0.50
0.50
0.49
0.44
0.50
0.48
0.50
0.50
0.49
0.50
0.50
0.35
0.50
5
6
8
12
13
14
75
76
79
80
81
83
95
96
98
99
100

output:

0.468040487498138

result:

ok found '0.4680405', expected '0.4680405', error '0.0000000'

Test #21:

score: 0
Accepted
time: 1ms
memory: 4112kb

input:

9
0.50
0.49
0.50
0.53
0.50
0.50
0.49
0.50
0.43
3
4
5
6
11
13
14
15
46

output:

0.986617756151447

result:

ok found '0.9866178', expected '0.9866178', error '0.0000000'

Test #22:

score: 0
Accepted
time: 8ms
memory: 4132kb

input:

8
0.67
0.50
0.41
0.37
0.39
0.50
0.40
0.57
1
2
47
50
61
62
64
65

output:

0.987560647490950

result:

ok found '0.9875606', expected '0.9875606', error '0.0000000'

Test #23:

score: 0
Accepted
time: 0ms
memory: 4056kb

input:

4
0.50
0.49
0.49
0.50
1
8
10
47

output:

0.492164978507617

result:

ok found '0.4921650', expected '0.4921650', error '0.0000000'

Test #24:

score: 0
Accepted
time: 1ms
memory: 3944kb

input:

7
0.47
0.21
0.49
0.48
0.52
0.50
0.50
1
7
8
29
31
32
34

output:

0.785864862522987

result:

ok found '0.7858649', expected '0.7858649', error '0.0000000'

Test #25:

score: 0
Accepted
time: 0ms
memory: 4176kb

input:

13
0.50
0.49
0.55
0.50
0.50
0.50
0.50
0.49
0.50
0.49
0.49
0.16
0.47
1
2
3
4
23
24
25
26
32
34
35
36
37

output:

0.787925256212935

result:

ok found '0.7879253', expected '0.7879253', error '0.0000000'

Test #26:

score: 0
Accepted
time: 5ms
memory: 4024kb

input:

6
0.50
0.50
0.48
0.46
0.50
0.50
1
11
12
13
16
97

output:

0.494907022877567

result:

ok found '0.4949070', expected '0.4949070', error '0.0000000'

Test #27:

score: 0
Accepted
time: 3ms
memory: 4080kb

input:

5
0.50
0.38
0.50
0.50
0.46
44
51
52
53
56

output:

0.273852196165007

result:

ok found '0.2738522', expected '0.2738522', error '0.0000000'

Test #28:

score: 0
Accepted
time: 5ms
memory: 4272kb

input:

15
0.48
0.49
0.50
0.50
0.48
0.48
0.43
0.50
0.50
0.50
0.49
0.50
0.47
0.50
0.47
10
11
13
14
17
19
20
21
22
23
24
25
27
28
29

output:

0.295871577900425

result:

ok found '0.2958716', expected '0.2958716', error '0.0000000'

Test #29:

score: 0
Accepted
time: 0ms
memory: 3936kb

input:

4
0.50
0.44
0.50
0.47
4
5
17
96

output:

0.490039965028504

result:

ok found '0.4900400', expected '0.4900400', error '0.0000000'

Test #30:

score: 0
Accepted
time: 4ms
memory: 4100kb

input:

5
0.50
0.46
0.50
0.50
0.50
13
15
22
24
92

output:

0.477704081827035

result:

ok found '0.4777041', expected '0.4777041', error '0.0000000'

Test #31:

score: 0
Accepted
time: 2ms
memory: 4224kb

input:

4
0.50
0.50
0.48
0.50
3
9
59
60

output:

0.497012738853499

result:

ok found '0.4970127', expected '0.4970127', error '0.0000000'

Test #32:

score: 0
Accepted
time: 5ms
memory: 4220kb

input:

9
0.43
0.50
0.50
0.50
0.49
0.50
0.50
0.50
0.50
1
2
9
13
48
51
52
54
55

output:

0.498182981352910

result:

ok found '0.4981830', expected '0.4981830', error '0.0000000'

Test #33:

score: 0
Accepted
time: 6ms
memory: 4228kb

input:

11
0.50
0.43
0.50
0.47
0.50
0.49
0.49
0.46
0.46
0.50
0.50
33
34
35
36
37
38
40
44
45
46
47

output:

0.270645539367926

result:

ok found '0.2706455', expected '0.2706455', error '0.0000000'

Test #34:

score: 0
Accepted
time: 4ms
memory: 4120kb

input:

5
0.50
0.42
0.43
0.40
0.50
12
14
15
18
96

output:

0.423680738246052

result:

ok found '0.4236807', expected '0.4236807', error '0.0000000'

Test #35:

score: 0
Accepted
time: 3ms
memory: 4484kb

input:

16
0.49
0.50
0.49
0.42
0.49
0.50
0.50
0.50
0.50
0.50
0.50
0.50
0.50
0.47
0.36
0.46
11
12
13
14
18
19
20
21
22
23
24
25
26
27
28
29

output:

0.280328273070482

result:

ok found '0.2803283', expected '0.2803283', error '0.0000000'

Test #36:

score: 0
Accepted
time: 1ms
memory: 3964kb

input:

4
0.50
0.42
0.48
0.49
1
2
26
29

output:

0.439614763704824

result:

ok found '0.4396148', expected '0.4396148', error '0.0000000'

Test #37:

score: 0
Accepted
time: 15ms
memory: 4220kb

input:

14
0.50
0.49
0.40
0.50
0.50
0.48
0.50
0.44
0.50
0.49
0.50
0.50
0.50
0.49
1
6
7
8
15
16
18
20
22
60
63
64
65
66

output:

0.464158911743387

result:

ok found '0.4641589', expected '0.4641589', error '0.0000000'

Test #38:

score: 0
Accepted
time: 1ms
memory: 4140kb

input:

2
0.50
0.6
46
51

output:

0.950980384995598

result:

ok found '0.9509804', expected '0.9509804', error '0.0000000'

Test #39:

score: 0
Accepted
time: 4ms
memory: 4028kb

input:

7
0.48
0.49
0.50
0.45
0.50
0.25
0.50
1
8
45
48
50
53
55

output:

0.354176826088803

result:

ok found '0.3541768', expected '0.3541768', error '0.0000000'

Test #40:

score: 0
Accepted
time: 4ms
memory: 4292kb

input:

15
0.50
0.50
0.49
0.44
0.50
0.38
0.38
0.49
0.50
0.50
0.40
0.49
0.49
0.49
0.50
1
5
10
11
12
13
15
16
17
18
19
20
21
22
45

output:

0.376042822696997

result:

ok found '0.3760428', expected '0.3760428', error '0.0000000'

Test #41:

score: 0
Accepted
time: 4ms
memory: 4144kb

input:

3
0.45
0.5
0.55
98
99
100

output:

0.814999997667775

result:

ok found '0.8150000', expected '0.8150000', error '0.0000000'

Test #42:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

2
0.75
0.25
1
2

output:

0.750000000000000

result:

ok found '0.7500000', expected '0.7500000', error '0.0000000'

Test #43:

score: 0
Accepted
time: 184ms
memory: 5224kb

input:

17
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

output:

0.500000000000001

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #44:

score: 0
Accepted
time: 0ms
memory: 3984kb

input:

4
0.7
0.6
0.4
0.3
2
4
6
8

output:

0.927722104489230

result:

ok found '0.9277221', expected '0.9277221', error '0.0000000'