結果
| 問題 |
No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
|
| コンテスト | |
| ユーザー |
 kys
|
| 提出日時 | 2022-10-15 01:20:18 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,854 bytes |
| コンパイル時間 | 2,301 ms |
| スコア | 0 |
| 最終ジャッジ日時 | 2022-10-15 01:22:38 |
| 合計ジャッジ時間 | 138,116 ms |
|
ジャッジサーバーID （参考情報） |
judge9 / judge12 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | TLE * 50 |
コンパイルメッセージ
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 | }
| ^
ソースコード
#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 = 2;
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);
}