QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#639718#1760. Jammed Gymoxford01#AC ✓1ms4208kbC++202.0kb2024-10-13 21:51:282024-10-13 21:51:28

Judging History

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

  • [2024-10-13 21:51:28]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:4208kb
  • [2024-10-13 21:51:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (auto i = a; i < (b); ++i)
#define repr(i, a, b) for (auto i = (a) - 1; i >= (b); --i)
#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<pii>;

template<class T>
inline bool cmax(T &a, const T& b) {
    return a < b ? a = b, 1 : 0;
}

template<class T>
inline bool cmin(T &a, const T &b) {
    return b < a ? a = b, 1 : 0;
}

const int inf = 0x3f3f3f3f;
const ll linf = 1e18;
const double dinf = numeric_limits<double>::infinity();

using ld = long double;

const double pi = acos(-1);

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int n;
    cin >> n;
    vi t(n + 1);
    rep(i, 1, n + 1) {
        cin >> t[i];
    }
    int m;
    cin >> m;
    vi q(m);
    
    rep(i, 0, m) {
        cin >> q[i];
    }

    vector< vector<double> > dp(n + 1, vector<double>(m, dinf));
    rep(i, 0, m) {
        if (q[i] == t[1]) {
            dp[1][i] = 1;
        }
    }

    auto dist = [&](int i, int j) {
        return hypot(cos((2 * pi * i) / m) - cos((2 * pi * j) / m), sin((2 * pi * i) / m) - sin((2 * pi * j) / m));
    };

    // cerr << dist(0, 2) << endl;

    rep(i, 2, n + 1) {
        rep(j, 0, m) {
            if (q[j] != t[i]) {
                continue;
            }
            rep(k, 0, m) {
                if (q[k] != t[i - 1]) {
                    continue;
                }
                cmin(dp[i][j], dp[i - 1][k] + dist(j, k));
            }
        }
    }

    double ans = dinf;
    rep(j, 0, m) {
        cmin(ans, dp[n][j]);
    }
    cout << fixed << setprecision(15) << ans << '\n';

    // rep(i, 1, n + 1) {
    //     rep(j, 0, m) {
    //         cerr << dp[i][j] << ' ';
    //     }
    //     cerr << endl;
    // }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 4204kb

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.090169943749475

result:

ok found '4.0901699', expected '4.0901699', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 4204kb

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.385582862918527

result:

ok found '11.3855829', expected '11.3855829', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4044kb

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.526668421194174

result:

ok found '26.5266684', expected '26.5266684', error '0.0000000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 4092kb

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.842913903045201

result:

ok found '43.8429139', expected '43.8429139', error '0.0000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 4124kb

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.556588215884386

result:

ok found '24.5565882', expected '24.5565882', error '0.0000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 4208kb

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.902691542503931

result:

ok found '47.9026915', expected '47.9026915', error '0.0000000'

Test #7:

score: 0
Accepted
time: 1ms
memory: 4168kb

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.581985869208253

result:

ok found '68.5819859', expected '68.5819859', error '0.0000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 4132kb

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.819349843004062

result:

ok found '73.8193498', expected '73.8193498', error '0.0000000'