QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#225173 | #2913. Archery Accuracy | PetroTarnavskyi | AC ✓ | 184ms | 5268kb | C++17 | 2.2kb | 2023-10-24 02:38:08 | 2023-10-24 02:38:09 |
Judging History
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'