QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#240972#7110. Kuririn MIRACLEpandapythonerWA 374ms4000kbC++235.0kb2023-11-05 21:30:102023-11-05 21:30:11

Judging History

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

  • [2023-11-05 21:30:11]
  • 评测
  • 测评结果:WA
  • 用时:374ms
  • 内存:4000kb
  • [2023-11-05 21:30:10]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using ld = long double;

struct vec {
    ld x, y;
    vec(ld x, ld y) : x(x), y(y){};
    ld operator%(const vec &o) const {
        return x * o.y - y * o.x;
    }
};

ld v, r, d;

const int n = 15;

vector<ld> fct;

void build_fct() {
    fct.resize(n + 1);
    fct[0] = 1;
    for (int i = 1; i <= n; i += 1) {
        fct[i] = fct[i - 1] * i;
    }
}

vector<ld> mul(const vector<ld> &a, const vector<ld> &b) {
    vector<ld> c(n, 0);
    for (int i = 0; i < n; i += 1) {
        for (int j = 0; j < n; j += 1) {
            if (i + j >= n) {
                break;
            }
            c[i + j] += a[i] * b[j];
        }
    }
    return c;
}

vector<ld> operator*(const vector<ld> &a, const vector<ld> &b) {
    return mul(a, b);
}

vector<ld> operator+(const vector<ld> &a, const vector<ld> &b) {
    vector<ld> c(n);
    for (int i = 0; i < n; i += 1) {
        c[i] = a[i] + b[i];
    }
    return c;
}

vector<ld> operator*(ld x, const vector<ld> &a) {
    vector<ld> c(n);
    for (int i = 0; i < n; i += 1) {
        c[i] = x * a[i];
    }
    return c;
}

vector<ld> operator-(const vector<ld> &a, const vector<ld> &b) {
    vector<ld> c(n);
    for (int i = 0; i < n; i += 1) {
        c[i] = a[i] - b[i];
    }
    return c;
}

vector<ld> get_rev(const vector<ld> &a) {
    vector<ld> b(n);
    b[0] = 1 / a[0];
    for (int i = 1; i < n; i += 1) {
        ld cur_sm = 0;
        for (int j = 0; j < i; j += 1) {
            cur_sm += a[i - j] * b[j];
        }
        b[i] = -cur_sm / a[0];
    }
    return b;
}

vector<ld> operator/(const vector<ld> &a, const vector<ld> &b) {
    auto rvb = get_rev(b);
    return a * rvb;
}

vector<ld> deriv(const vector<ld> &a) {
    vector<ld> c(n);
    c[n - 1] = 0;
    for (int i = 1; i < n; i += 1) {
        c[i - 1] = a[i] * i;
    }
    return c;
}

vector<ld> integr(const vector<ld> &a) {
    vector<ld> c(n);
    c[0] = 0;
    for (int i = 0; i + 1 < n; i += 1) {
        c[i + 1] = a[i] / ((ld)(i) + 1);
    }
    return c;
}

vector<ld> log(const vector<ld> &a) {
    ll t = a[0];
    auto c = integr(deriv(a) / a);
    c[0] = log(t);
    return c;
}

vector<ld> exp(const vector<ld> &a) {
    vector<ld> rs(n, 0);
    vector<ld> apw(n, 0);
    apw[0] = 1;
    for (int i = 0; i < n; i += 1) {
        rs = rs + (1 / fct[i]) * apw;
        apw = apw * a;
    }
    return rs;
}

void print(const vector<ld> &a) {
    for (auto x : a) {
        cerr << x << " ";
    }
    cerr << "\n";
}

vector<ld> sinx() {
    vector<ld> a(n);
    for (int i = 1; i < n; i += 2) {
        if (((i - 1) / 2) % 2 == 0) {
            a[i] = 1 / fct[i];
        } else {
            a[i] = -1 / fct[i];
        }
    }
    return a;
}

ld get_val(vector<ld> &a, ld x) {
    ld pw = 1;
    ld rs = 0;
    for (int i = 0; i < n; i += 1) {
        rs += a[i] * pw;
        pw *= x;
    }
    return rs;
}

vector<ld> sqrt(const vector<ld> &a) {
    auto b = 0.5 * log(a);
    return exp(b);
}

vector<ld> gnrt;

ld f(ld a) {
    ld sn = sin(a);
    return sqrtl(3 + sn * sn) + sn;
}

ld integral_a(ld a) {
    static const int N = 1e5;
    ld res = 0;
    for (int i = 1; i < N; ++i) {
        ld l = (i - 1) * a / N;
        ld r = i * a / N;
        res += f(l) + f(r) + 4 * f((l + r) / 2);
    }
    return res * a / 6 / N;
}

ld time_a(ld a) {
    ld cnst = 2 * r / 3 / v;
    // return cnst * get_val(gnrt, a);
    return cnst * integral_a(a);
}

int32_t main() {
    build_fct();
    if (1) {
        vector<ld> sn = sinx();
        cout << get_val(sn, 2) << " " << sin(2) << "\n";
    }
    auto sn = sinx();
    auto sn2 = sn * sn;
    vector<ld> three(n, 0);
    three[0] = 3;
    auto a = sqrt(three + sn2) + sn;
    gnrt = integr(a);
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
#ifdef LOCAL
    freopen("../input.txt", "r", stdin);
    freopen("../output.txt", "w", stdout);
#endif
    int tt;
    cin >> tt;
    cout << fixed << setprecision(20);
    while (tt--) {
        cin >> v >> r >> d;
        ld lo = 0, hi = M_PI;
        static const int kek = 50;
        for (int _ = 0; _ < kek; ++_) {
            ld a = (lo + hi) / 2;
            ld t = time_a(a);
            ld sn = sin(a), cs = cos(a);
            ld u = v * (sqrtl(sn * sn + 3) - sn);
            vec cur(v + u * sn, u * cs);
            vec dir(d - 2 * r - v * t + 2 * r * cs, -2 * r * sn);
            if (dir % cur > 0) {
                lo = a;
            } else {
                hi = a;
            }
        }
        ld t = time_a(hi);
        ld sn = sin(hi), cs = cos(hi);
        ld x = d - 2 * r - v * t + 2 * r * cs, y = -2 * r * sn;
        ld ans = t + sqrtl((x * x + y * y)) / (2 * v);
        ans = min(ans, d / v);
        cout << ans << '\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 374ms
memory: 4000kb

input:

1
2.00 3 30.0

output:

0.909297 0.909297
8.31054539457454717697

result:

wrong answer 1st numbers differ - expected: '8.3105799', found: '0.9092970', error = '0.8905856'