QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#55287#1760. Jammed Gymabdelrahman001#AC ✓2ms4424kbC++1.2kb2022-10-12 22:51:282022-10-12 22:51:29

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-12 22:51:29]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:4424kb
  • [2022-10-12 22:51:28]
  • 提交

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'