QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#80417#2913. Archery AccuracyjoesmittyAC ✓901ms5308kbC++143.8kb2023-02-23 17:03:102023-02-23 17:03:12

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-23 17:03:12]
  • 评测
  • 测评结果:AC
  • 用时:901ms
  • 内存:5308kb
  • [2023-02-23 17:03:10]
  • 提交

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'