QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#55287 | #1760. Jammed Gym | abdelrahman001# | AC ✓ | 2ms | 4424kb | C++ | 1.2kb | 2022-10-12 22:51:28 | 2022-10-12 22:51:29 |
Judging History
answer
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = 1e2 + 5;
const ld PI = acos(-1);
int n, m, a[N], b[N];
ld memo[N][N];
ld unit_ang;
ld dis(int i, int j) {
if(i > j)
swap(i, j);
int cnt = min(j - i, m - j + i);
ld ang = cnt * unit_ang;
if(ang == 180)
return 2;
ld rad = ang * PI / 180;
ld ret = sin(rad / 2);
return ret * 2;
}
ld solve(int i, int lst) {
if(i == n)
return 0;
ld &ans = memo[i][lst];
if(ans != -1)
return ans;
ans = 1e9;
for(int j = 0;j < m;j++) {
if(b[j] == a[i])
ans = min(ans, solve(i + 1, j) + dis(lst, j));
}
return ans;
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n;
for(int i = 0;i < n;i++)
cin >> a[i];
cin >> m;
for(int i = 0;i < m;i++)
cin >> b[i];
unit_ang = (ld)360 / (ld)m;
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
memo[i][j] = -1;
ld ans = 1e9;
for(int i = 0;i < m;i++)
if(b[i] == a[0])
ans = min(ans, solve(1, i) + 1);
cout << fixed << setprecision(9) << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 4284kb
input:
10 1 3 2 2 3 1 3 3 3 3 10 1 2 3 1 1 2 1 2 2 2
output:
4.090169944
result:
ok found '4.0901699', expected '4.0901699', error '0.0000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 4264kb
input:
20 3 2 3 4 4 4 1 4 2 4 3 2 3 2 3 3 4 1 4 4 10 4 1 2 3 4 1 1 3 2 4
output:
11.385582863
result:
ok found '11.3855829', expected '11.3855829', error '0.0000000'
Test #3:
score: 0
Accepted
time: 2ms
memory: 4324kb
input:
30 5 4 2 2 3 2 2 4 3 5 2 1 2 1 2 3 5 1 4 4 1 1 2 4 5 3 1 4 2 3 10 4 5 3 3 2 3 2 1 5 1
output:
26.526668421
result:
ok found '26.5266684', expected '26.5266684', error '0.0000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 4176kb
input:
100 4 5 8 5 10 1 9 3 3 3 1 2 4 7 9 9 4 5 7 7 1 6 8 2 1 4 5 9 5 8 8 2 5 3 8 10 8 6 4 9 8 9 1 4 1 5 2 6 10 6 6 3 4 3 4 5 10 6 10 4 1 3 10 4 7 1 8 1 5 10 7 9 8 9 2 7 8 10 5 10 5 1 9 3 2 3 4 1 5 6 4 9 1 7 10 9 3 8 10 10 50 9 8 7 1 7 7 9 4 8 10 4 3 3 10 4 3 1 3 9 2 7 5 6 8 7 2 3 1 8 9 4 5 9 7 4 2 7 1 4 9...
output:
43.842913903
result:
ok found '43.8429139', expected '43.8429139', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4268kb
input:
100 5 2 6 9 5 2 9 7 6 1 7 6 4 9 6 10 5 6 6 4 6 10 2 1 3 4 9 6 1 9 1 9 6 2 2 10 4 6 6 2 6 8 6 8 2 1 9 8 4 4 2 7 5 5 9 10 8 5 6 9 8 8 7 7 8 3 6 2 4 2 9 5 10 4 8 7 10 9 7 10 3 10 9 1 6 1 4 8 5 1 2 3 1 7 4 7 9 6 10 4 100 4 9 2 9 3 8 10 8 1 3 9 4 1 9 4 5 2 9 9 9 5 3 5 3 8 10 7 1 8 9 8 10 2 4 2 4 5 10 8 8...
output:
24.556588216
result:
ok found '24.5565882', expected '24.5565882', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4264kb
input:
100 3 19 13 12 13 1 12 10 3 10 17 6 18 8 7 20 12 14 4 2 9 10 13 5 3 12 17 17 13 5 13 2 15 10 18 19 17 6 16 4 4 12 6 3 7 7 8 16 16 14 4 2 12 1 14 8 20 5 3 7 5 5 19 14 7 11 17 4 2 6 13 16 5 17 2 19 7 15 19 6 13 19 8 11 1 5 2 19 8 11 11 20 8 2 10 15 13 11 20 6 100 2 9 8 15 18 7 11 14 19 10 14 20 3 10 1...
output:
47.902691543
result:
ok found '47.9026915', expected '47.9026915', error '0.0000000'
Test #7:
score: 0
Accepted
time: 2ms
memory: 4424kb
input:
100 16 24 16 6 28 6 11 17 13 26 5 10 21 7 20 26 3 18 16 15 16 19 24 2 21 7 9 15 6 8 8 7 17 25 29 13 29 6 14 9 29 14 30 2 2 17 20 9 9 14 11 22 3 1 9 4 9 16 9 13 12 9 15 1 2 7 3 28 12 7 28 2 25 28 1 25 19 15 11 8 10 27 7 2 16 29 7 13 18 7 30 11 12 20 9 29 26 29 15 17 100 7 10 23 17 22 23 13 5 9 6 18 2...
output:
68.581985869
result:
ok found '68.5819859', expected '68.5819859', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 4420kb
input:
100 18 7 17 6 31 2 26 8 1 21 40 37 23 22 26 13 28 17 19 28 15 10 1 22 8 34 31 16 4 16 25 36 9 25 31 17 22 38 33 13 40 37 15 32 4 22 15 2 5 16 7 28 13 8 20 10 1 17 21 18 18 34 19 12 11 24 28 14 5 9 35 25 4 9 38 21 7 8 39 12 12 29 6 16 40 22 38 28 9 29 17 13 28 27 19 40 1 9 20 9 100 27 7 30 18 14 39 3...
output:
73.819349843
result:
ok found '73.8193498', expected '73.8193498', error '0.0000000'