QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#80417 | #2913. Archery Accuracy | joesmitty | AC ✓ | 901ms | 5308kb | C++14 | 3.8kb | 2023-02-23 17:03:10 | 2023-02-23 17:03:12 |
Judging History
answer
#include <iostream>
#include <tuple>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iomanip>
#include <ctime>
#include <cctype>
#include <climits>
#include <chrono>
#include <array>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int, int> pii;
typedef pair < pair < int, int >, int > piii;
typedef pair < pair <int, int > , pair <int, int> > piiii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
#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 all(a) a.begin(), a.end()
#define endl '\n';
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
template <typename T>
void pr(vector<T> &v) {
FOR(i, 0, sz(v)) cout << v[i] << " ";
cout << endl;
}
template <typename T>
void pr(vector<vector<T> > &v) {
FOR(i, 0, sz(v)) { pr(v[i]); }
}
template <typename T>
void re(T &x) {
cin >> x;
}
template <typename T>
void re(vector<T> &a) {
FOR(i, 0, sz(a)) re(a[i]);
}
template <class Arg, class... Args>
void re(Arg &first, Args &... rest) {
re(first);
re(rest...);
}
template <typename T>
void pr(T x) {
cout << x << endl;
}
template <class Arg, class... Args>
void pr(const Arg &first, const Args &... rest) {
cout << first << " ";
pr(rest...);
cout << endl;
}
void ps() { cout << endl; }
template<class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
cout << t; if (sizeof...(ts)) cout << " "; ps(ts...);
}
const ll MOD = 998244353;
#define inf 1e18;
#define INF INT_MAX
long double PI = 4*atan(1);
long double eps = 1e-12;
long double pwin(long double p, long double a, long double b) {
if(abs(p - 0.5) < 0.0001) {
return b/(a+b);
} else {
if(p < 0.5) {
long double x = pow(p/(1-p), a)-pow(p/(1-p), a+b);
long double y = 1-pow(p/(1-p), a+b);
return x/y;
} else {
long double x = pow((1-p)/p, b) - 1;
long double y = pow((1-p)/p, a+b) - 1;
return x/y;
}
}
return 0.5;
}
int main() {
//auto start = chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);cin.tie(0);
//ofstream cout("output.txt");
//ifstream cin("input.txt");
#ifdef DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n; cin >> n;
vector<long double> p(n); re(p);
vi tar(n+1);
FOR(i,0,n) cin >> tar[i+1];
vector<long double> pup(1 << n);
pup[0] = 1;
for(int i = 1; i < (1 << n); i++) {
int cnt = 0;
for(int j = 0; j < n; j++) if(i & (1 << j)) cnt++;
for(int j = 0; j < n; j++) {
if(i & (1 << j)) {
long double pos = pup[i ^ (1 << j)];
long double up = tar[cnt] - tar[cnt-1];
long double down = tar[cnt] + tar[cnt-1];
long double val = pos * pwin(p[j], up, down) + (1-pos) * pwin(p[j], down, up);
pup[i] = max(pup[i], val);
}
}
}
cout << setprecision(12) << pup[(1 << n) - 1] << endl;
//auto stop = chrono::high_resolution_clock::now();
//auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
//cout << duration.count() << endl;
//cin.close();
//cout.close();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 428ms
memory: 5068kb
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.451642215269
result:
ok found '0.4516422', expected '0.4516422', error '0.0000000'
Test #2:
score: 0
Accepted
time: 519ms
memory: 5152kb
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.58093501342
result:
ok found '0.5809350', expected '0.5809350', error '0.0000000'
Test #3:
score: 0
Accepted
time: 538ms
memory: 5080kb
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.40390033587
result:
ok found '0.4039003', expected '0.4039003', error '0.0000000'
Test #4:
score: 0
Accepted
time: 307ms
memory: 5272kb
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.860952342153
result:
ok found '0.8609523', expected '0.8609523', error '0.0000000'
Test #5:
score: 0
Accepted
time: 659ms
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.776088213912
result:
ok found '0.7760882', expected '0.7760882', error '0.0000000'
Test #6:
score: 0
Accepted
time: 405ms
memory: 5308kb
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.475040920128
result:
ok found '0.4750409', expected '0.4750409', error '0.0000000'
Test #7:
score: 0
Accepted
time: 901ms
memory: 5200kb
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.986376391643
result:
ok found '0.9863764', expected '0.9863764', error '0.0000000'
Test #8:
score: 0
Accepted
time: 628ms
memory: 5296kb
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.884537941723
result:
ok found '0.8845379', expected '0.8845379', error '0.0000000'
Test #9:
score: 0
Accepted
time: 482ms
memory: 5196kb
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.929999999999
result:
ok found '0.9300000', expected '0.9300000', error '0.0000000'
Test #10:
score: 0
Accepted
time: 641ms
memory: 5300kb
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.845433066857
result:
ok found '0.8454331', expected '0.8454331', error '0.0000000'
Test #11:
score: 0
Accepted
time: 560ms
memory: 5236kb
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.997191923295
result:
ok found '0.9971919', expected '0.9971919', error '0.0000000'
Test #12:
score: 0
Accepted
time: 511ms
memory: 5284kb
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.169772515004
result:
ok found '0.1697725', expected '0.1697725', error '0.0000000'
Test #13:
score: 0
Accepted
time: 564ms
memory: 5292kb
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.282704561765
result:
ok found '0.2827046', expected '0.2827046', error '0.0000000'
Test #14:
score: 0
Accepted
time: 339ms
memory: 5064kb
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.813789074256
result:
ok found '0.8137891', expected '0.8137891', error '0.0000000'
Test #15:
score: 0
Accepted
time: 227ms
memory: 5084kb
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.478156391666
result:
ok found '0.4781564', expected '0.4781564', error '0.0000000'
Test #16:
score: 0
Accepted
time: 613ms
memory: 5284kb
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.934674656153
result:
ok found '0.9346747', expected '0.9346747', error '0.0000000'
Test #17:
score: 0
Accepted
time: 525ms
memory: 5152kb
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.994863326681
result:
ok found '0.9948633', expected '0.9948633', error '0.0000000'
Test #18:
score: 0
Accepted
time: 471ms
memory: 5296kb
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.909851928058
result:
ok found '0.9098519', expected '0.9098519', error '0.0000000'
Test #19:
score: 0
Accepted
time: 822ms
memory: 5180kb
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.991124035266
result:
ok found '0.9911240', expected '0.9911240', error '0.0000000'
Test #20:
score: 0
Accepted
time: 350ms
memory: 5088kb
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.468040487498
result:
ok found '0.4680405', expected '0.4680405', error '0.0000000'
Test #21:
score: 0
Accepted
time: 3ms
memory: 3556kb
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.986617756151
result:
ok found '0.9866178', expected '0.9866178', error '0.0000000'
Test #22:
score: 0
Accepted
time: 2ms
memory: 3604kb
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.987560647491
result:
ok found '0.9875606', expected '0.9875606', error '0.0000000'
Test #23:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
4 0.50 0.49 0.49 0.50 1 8 10 47
output:
0.492164978508
result:
ok found '0.4921650', expected '0.4921650', error '0.0000000'
Test #24:
score: 0
Accepted
time: 1ms
memory: 3796kb
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.785864862523
result:
ok found '0.7858649', expected '0.7858649', error '0.0000000'
Test #25:
score: 0
Accepted
time: 32ms
memory: 3788kb
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.787925256213
result:
ok found '0.7879253', expected '0.7879253', error '0.0000000'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
6 0.50 0.50 0.48 0.46 0.50 0.50 1 11 12 13 16 97
output:
0.494907022878
result:
ok found '0.4949070', expected '0.4949070', error '0.0000000'
Test #27:
score: 0
Accepted
time: 2ms
memory: 3720kb
input:
5 0.50 0.38 0.50 0.50 0.46 44 51 52 53 56
output:
0.273852196165
result:
ok found '0.2738522', expected '0.2738522', error '0.0000000'
Test #28:
score: 0
Accepted
time: 125ms
memory: 3592kb
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.2958715779
result:
ok found '0.2958716', expected '0.2958716', error '0.0000000'
Test #29:
score: 0
Accepted
time: 2ms
memory: 3608kb
input:
4 0.50 0.44 0.50 0.47 4 5 17 96
output:
0.490039965029
result:
ok found '0.4900400', expected '0.4900400', error '0.0000000'
Test #30:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
5 0.50 0.46 0.50 0.50 0.50 13 15 22 24 92
output:
0.477704081827
result:
ok found '0.4777041', expected '0.4777041', error '0.0000000'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
4 0.50 0.50 0.48 0.50 3 9 59 60
output:
0.497012738854
result:
ok found '0.4970127', expected '0.4970127', error '0.0000000'
Test #32:
score: 0
Accepted
time: 3ms
memory: 3772kb
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.498182981353
result:
ok found '0.4981830', expected '0.4981830', error '0.0000000'
Test #33:
score: 0
Accepted
time: 4ms
memory: 3584kb
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.270645539368
result:
ok found '0.2706455', expected '0.2706455', error '0.0000000'
Test #34:
score: 0
Accepted
time: 2ms
memory: 3628kb
input:
5 0.50 0.42 0.43 0.40 0.50 12 14 15 18 96
output:
0.423680738246
result:
ok found '0.4236807', expected '0.4236807', error '0.0000000'
Test #35:
score: 0
Accepted
time: 224ms
memory: 4232kb
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.28032827307
result:
ok found '0.2803283', expected '0.2803283', error '0.0000000'
Test #36:
score: 0
Accepted
time: 1ms
memory: 3552kb
input:
4 0.50 0.42 0.48 0.49 1 2 26 29
output:
0.439614763705
result:
ok found '0.4396148', expected '0.4396148', error '0.0000000'
Test #37:
score: 0
Accepted
time: 48ms
memory: 3716kb
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.464158911743
result:
ok found '0.4641589', expected '0.4641589', error '0.0000000'
Test #38:
score: 0
Accepted
time: 2ms
memory: 3704kb
input:
2 0.50 0.6 46 51
output:
0.950980384996
result:
ok found '0.9509804', expected '0.9509804', error '0.0000000'
Test #39:
score: 0
Accepted
time: 0ms
memory: 3700kb
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.354176826089
result:
ok found '0.3541768', expected '0.3541768', error '0.0000000'
Test #40:
score: 0
Accepted
time: 138ms
memory: 3764kb
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.376042822697
result:
ok found '0.3760428', expected '0.3760428', error '0.0000000'
Test #41:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
3 0.45 0.5 0.55 98 99 100
output:
0.814999997668
result:
ok found '0.8150000', expected '0.8150000', error '0.0000000'
Test #42:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
2 0.75 0.25 1 2
output:
0.75
result:
ok found '0.7500000', expected '0.7500000', error '0.0000000'
Test #43:
score: 0
Accepted
time: 39ms
memory: 5176kb
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.5
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #44:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
4 0.7 0.6 0.4 0.3 2 4 6 8
output:
0.927722104489
result:
ok found '0.9277221', expected '0.9277221', error '0.0000000'