結果

問題 No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
ユーザー kyskys
提出日時 2022-10-15 01:10:00
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 9,854 bytes
コンパイル時間 3,619 ms
スコア 0
最終ジャッジ日時 2022-10-15 01:12:20
合計ジャッジ時間 138,653 ms
ジャッジサーバーID
(参考情報)
judge12 / judge13
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 TLE -
testcase_02 TLE -
testcase_03 TLE -
testcase_04 TLE -
testcase_05 TLE -
testcase_06 TLE -
testcase_07 TLE -
testcase_08 TLE -
testcase_09 TLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 TLE -
testcase_31 TLE -
testcase_32 TLE -
testcase_33 TLE -
testcase_34 TLE -
testcase_35 TLE -
testcase_36 TLE -
testcase_37 TLE -
testcase_38 TLE -
testcase_39 TLE -
testcase_40 TLE -
testcase_41 TLE -
testcase_42 TLE -
testcase_43 TLE -
testcase_44 TLE -
testcase_45 TLE -
testcase_46 TLE -
testcase_47 TLE -
testcase_48 TLE -
testcase_49 TLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: 関数 ‘ll score(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)’ 内:
main.cpp:171:1: 警告: 制御が非 void 関数の終りに到達しました [-Wreturn-type]
  171 | }
      | ^

ソースコード

diff #

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#ifdef _MSC_VER
#include <ppl.h>
#else
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
/* const */
constexpr double PI = 3.141592653589793238462643;
/* io */
namespace aux {
    template<typename T, unsigned N, unsigned L> struct tp { static void print(std::ostream& os, const T& v) { os << std::get<N>(v) << ", "; tp<T, N + 1, L>::print(os, v); } };
    template<typename T, unsigned N> struct tp<T, N, N> { static void print(std::ostream& os, const T& v) { os << std::get<N>(v); } };
}
template<typename... Ts> std::ostream& operator<<(std::ostream& os, const std::tuple<Ts...>& t) { os << '['; aux::tp<std::tuple<Ts...>, 0, sizeof...(Ts) - 1>::print(os, t); os << ']'; return os; }
template <class T, class = typename T::iterator, std::enable_if_t<!std::is_same<T, std::string>::value, int> = 0> std::ostream& operator<<(std::ostream& os, T const& a);
template <class T, class S> std::ostream& operator<<(std::ostream& os, std::pair<T, S> const& p) { return os << '[' << p.first << ", " << p.second << ']'; }
template <class T, class S> std::istream& operator>>(std::istream& is, std::pair<T, S>& p) { return is >> p.first >> p.second; }
template <class T, class, std::enable_if_t<!std::is_same<T, std::string>::value, int>>
std::ostream& operator<<(std::ostream& os, T const& a) { bool f = true; os << '['; for (auto const& x : a) { os << (f ? "" : ", ") << x; f = false; } os << ']'; return os; }
template <class T, size_t N, std::enable_if_t<!std::is_same<T, char>::value, int> = 0>
std::ostream& operator<<(std::ostream& os, const T(&a)[N]) { bool f = true; os << '['; for (auto const& x : a) { os << (f ? "" : ", ") << x; f = false; } os << ']'; return os; }
template <class T, class = decltype(std::begin(std::declval<T&>())), class = typename std::enable_if<!std::is_same<T, std::string>::value>::type>
std::istream& operator>>(std::istream& is, T& a) { for (auto& x : a) is >> x; return is; }
struct IOSetup { IOSetup(bool f) { if (f) { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); } std::cout << std::fixed << std::setprecision(15); } } iosetup(true);
/* format */
template<typename... Ts> std::string format(const std::string& f, Ts... t) { size_t l = std::snprintf(nullptr, 0, f.c_str(), t...); std::vector<char> b(l + 1); std::snprintf(&b[0], l + 1, f.c_str(), t...); return std::string(&b[0], &b[0] + l); }
/* dump */
#define ENABLE_DUMP
#ifdef ENABLE_DUMP
#define DUMPOUT std::cerr
std::ostringstream DUMPBUF;
#define dump(...) do{DUMPBUF<<"  ";DUMPBUF<<#__VA_ARGS__<<" :[DUMP - "<<__LINE__<<":"<<__FUNCTION__<<"]"<<std::endl;DUMPBUF<<"    ";dump_func(__VA_ARGS__);DUMPOUT<<DUMPBUF.str();DUMPBUF.str("");DUMPBUF.clear();}while(0);
void dump_func() { DUMPBUF << std::endl; }
template <class Head, class... Tail> void dump_func(Head&& head, Tail&&... tail) { DUMPBUF << head; if (sizeof...(Tail) == 0) { DUMPBUF << " "; } else { DUMPBUF << ", "; } dump_func(std::move(tail)...); }
#else
#define dump(...) void(0);
#endif
/* misc */
struct Timer {
    double t = 0, paused = 0, tmp; Timer() { reset(); } static double time() {
#ifdef _MSC_VER
        return __rdtsc() / 3.0e9;
#else
        unsigned long long a, d;
        __asm__ volatile("rdtsc"
            : "=a"(a), "=d"(d));
        return (d << 32 | a) / 3.0e9;
#endif
    } void reset() { t = time(); } void pause() { tmp = time(); } void restart() { paused += time() - tmp; } double elapsedMs() { return (time() - t - paused) * 1000.0; }
} timer;
struct Xorshift {
    uint64_t x = 88172645463325252LL;
    void set_seed(unsigned seed, int rep = 100) { x = (seed + 1) * 10007; for (int i = 0; i < rep; i++) next_int(); }
    unsigned next_int() { x = x ^ (x << 7); return x = x ^ (x >> 9); }
    unsigned next_int(unsigned mod) { x = x ^ (x << 7); x = x ^ (x >> 9); return x % mod; }
    unsigned next_int(unsigned l, unsigned r) { x = x ^ (x << 7); x = x ^ (x >> 9); return x % (r - l + 1) + l; }
    double next_double() { return double(next_int()) / UINT_MAX; }
} rnd;
template<typename T> void shuffle_vector(std::vector<T>& v, Xorshift& rnd) { int n = v.size(); for (int i = n - 1; i >= 1; i--) { int r = rnd.next_int(i); std::swap(v[i], v[r]); } }
std::vector<std::string> split(std::string str, const std::string& delim) { for (char& c : str) if (delim.find(c) != std::string::npos) c = ' '; std::istringstream iss(str); std::vector<std::string> parsed; std::string buf; while (iss >> buf) parsed.push_back(buf); return parsed; }

template<typename T, typename ...Args> auto make_vector(T x, int arg, Args ...args) { if constexpr (sizeof...(args) == 0)return std::vector<T>(arg, x); else return std::vector(arg, make_vector<T>(x, args...)); }
template<typename T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template<typename T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using pdd = std::pair<double, double>;
constexpr int MAXBE = 1;
constexpr double START_TEMP = 10, END_TEMP = 1;
int N, K;
using namespace std;

ll score(vector<int> Bs, vector<int> Ms, vector<int> Es, vector<int> T, vector<int> U) {
    vector<vector<int>> X(K, vector<int>(N, 0)), Y(K, vector<int>(N, 0));

    for (int n = 0; n < N; n++) {
        int start = 2 * Bs[n];
        int diff = 2 * Es[n];
        int end = 2 * Ms[n];
        int last = (start - end) / diff;
        int thr = start * (last + 1) - last * (last + 1) / 2 * diff;

        for (int i = 0; i < K; i++) {
            int t;
            t = T[i];
            if (t <= thr) {
                int ok = MAXBE;
                int ng = -1;
                while (ng + 1 < ok){
                    int ch = (ok + ng) / 2;
                    if (t < start * (ch + 1) - ch * (ch + 1) / 2 * diff) ng = ch;
                    else ok = ch;
                }
                t -= start * ok - ok * (ok - 1) / 2 * diff;
                int sgn;
                if (ok % 2) sgn = -1;
                else sgn = 1;
                if (t <= (start - ok * diff) / 2) X[i][n] = sgn * t;
                else X[i][n] = sgn * (start - ok * diff - t);
            } else {
                t -= start * (last + 1) - last * (last + 1) / 2 * diff;
                int ok = last + t / end;
                t %= end;
                int sgn;
                if (ok % 2) sgn = -1;
                else sgn = 1;
                if (t <= end / 2) X[i][n] = sgn * t;
                else X[i][n] = sgn * (end - t);
            }
            t = U[i];
            if (t <= thr) {
                int ok = MAXBE;
                int ng = -1;
                while (ng + 1 < ok){
                    int ch = (ok + ng) / 2;
                    if (t < start * (ch + 1) - ch * (ch + 1) / 2 * diff) ng = ch;
                    else ok = ch;
                }
                t -= start * ok - ok * (ok - 1) / 2 * diff;
                int sgn;
                if (ok % 2) sgn = -1;
                else sgn = 1;
                if (t <= (start - ok * diff) / 2) Y[i][n] = sgn * t;
                else Y[i][n] = sgn * (start - ok * diff - t);
            } else {
                t -= start * (last + 1) - last * (last + 1) / 2 * diff;
                int ok = last + t / end;
                t %= end;
                int sgn;
                if (ok % 2) sgn = -1;
                else sgn = 1;
                if (t <= end / 2) Y[i][n] = sgn * t;
                else Y[i][n] = sgn * (end - t);
            }
        }

        double tmp1 = 0;
        for (int k = 0; k < N; k++) {
            double t = 0;
            for (int i = 0; i < N - 1; i++) {
                for (int j = i + 1; j < N; j++) {
                    t += (double)abs(X[k][i] - X[k][j]) / (double)(Bs[i] + Bs[j]);
                }
            }
            t *= 20000000.0 / N / (N - 1);
            tmp1 += t;
        }
        tmp1 /= K;
        double tmp2 = 0;
        for (int k = 0; k < N; k++) {
            int t = 0;
            for (int i = 0; i < N - 1; i++) {
                for (int j = i + 1; j < N; j++) {
                    chmax(t, abs(X[k][i] - X[k][j]));
                }
            double tt = 10000000.0 / sqrt((double)t / 20 + 1);
            tmp2 += tt;
            }
        }

        ll ans1, ans2;
        ans1 = round(tmp1);
        ans2 = round(tmp2);
        return ans1 * ans2;
    }
}


int main() {
    cin >> N >> K;
    vector<int> T(K), U(K);
    cin >> T >> U;
    
    vector<int> Bs(N), Ms(N), Es(N);

    for (int i = 0; i < N; i++) {
        int tmp = rnd.next_int(MAXBE) + 1;
        Bs[i] = tmp;
        Ms[i] = rnd.next_int(tmp) + 1;
        Es[i] = rnd.next_int(tmp) + 1;
    }

    double tmp_score = score(Bs, Ms, Es, T, U);
    double start_time = timer.elapsedMs(), now_time, end_time = 1900;
    while ((now_time = timer.elapsedMs()) < end_time){
        int idx = rnd.next_int(N);
        int newb = rnd.next_int(MAXBE) + 1;
        int newm = rnd.next_int(newb) + 1;
        int newe = rnd.next_int(newb) + 1;
        int oldb, oldm, olde;
        oldb = Bs[idx];
        oldm = Ms[idx];
        olde = Es[idx];
        Bs[idx] = newb;
        Ms[idx] = newm;
        Es[idx] = newe;
        double new_score = score(Bs, Ms, Es, T, U);
        double temp = START_TEMP + (END_TEMP - START_TEMP) * now_time / 2000.0;
        double prob = exp((new_score - tmp_score) / temp);
        if (rnd.next_double() < prob) {
            Bs[idx] = oldb;
            Ms[idx] = oldm;
            Es[idx] = olde;
        } else {
            tmp_score = new_score;
        }

        for (int i = 0; i < N; i++) {
            cout << Bs[i] << ' ' << Ms[i] << ' ' << Es[i] << '\n';
        }
    }
    dump(tmp_score * 50);
    
}
0