結果
問題 | No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance |
ユーザー |
![]() |
提出日時 | 2022-10-15 00:46:38 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,879 ms / 2,000 ms |
コード長 | 4,760 bytes |
コンパイル時間 | 972 ms |
実行使用メモリ | 6,952 KB |
スコア | 1,059,460,821,476,991 |
最終ジャッジ日時 | 2022-10-15 00:48:26 |
合計ジャッジ時間 | 103,144 ms |
ジャッジサーバーID (参考情報) |
judge9 / judge11 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
#include <iostream>#include <algorithm>#include <iomanip>#include <vector>#include <queue>#include <deque>#include <set>#include <map>#include <tuple>#include <cmath>#include <numeric>#include <functional>#include <cassert>#include <random>#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }using namespace std;typedef long long ll;template<typename T>vector<vector<T>> vec2d(int n, int m, T v){return vector<vector<T>>(n, vector<T>(m, v));}template<typename T>vector<vector<vector<T>>> vec3d(int n, int m, int k, T v){return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, v)));}template<typename T>void print_vector(vector<T> v, char delimiter=' '){if(v.empty()) {cout << endl;return;}for(int i = 0; i+1 < v.size(); i++) cout << v[i] << delimiter;cout << v.back() << endl;}int N, K;int t[50], u[50];void input(){cin >> N >> K;for(int i = 0; i < K; i++) cin >> t[i];for(int i = 0; i < K; i++) cin >> u[i];}int naive_simulate(int b, int m, int e, int t){int d = 1, a = b;int x = 0;for(int i = 1; i <= t; i++){x += d;if(x == a*d){d *= -1;a = max(m, a-e);}}return x;}int simulate(int b, int m, int e, int t){assert(m == b);int rem = t%(4*b);if(rem <= b){return rem;}else if(rem <= 3*b){return b-(rem-b);}else{return -b+(rem-3*b);}}void test(){for(int b = 1; b <= 100; b++){for(int e = 1; e <= 10; e++){for(int t = 0; t <= 100; t++){assert(simulate(b, b, e, t) == naive_simulate(b, b, e, t));}}}}int b[50], m[50], e[50];ll eval(){vector<int> x(N);double s0 = 0.0;double coef = 2e7/((double)N*(double)(N-1));for(int i = 0; i < K; i++){for(int j = 0; j < K; j++){x[j] = simulate(b[j], m[j], e[j], t[j]);}for(int j = 0; j < N; j++){for(int k = j+1; k < N; k++){s0 += coef*abs(x[j]-x[k])/((double)(b[j]+b[k]));}}}double s1 = 0.0;for(int i = 0; i < K; i++){for(int j = 0; j < N; j++){x[j] = simulate(b[j], m[j], e[j], t[j]);}int max_diff = 0;for(int j = 0; j < N; j++){for(int k = j+1; k < N; k++){chmax(max_diff, abs(x[k]-x[j]));}}s1 += 1e7/sqrt(0.05*max_diff+1.0);}return round(s0/(double)K)*round(s1/(double)K);}const int min_b = 1, max_b = 1000000000;void solve(double time_limit, double start_temp = 5.0, double end_temp = 0.5, int seed=42){mt19937 mt;mt.seed(seed);uniform_real_distribution<float> rand_dist(0.0, 1.0);auto accept_proba = [&](int diff, double temp){return min(1.0, exp((double)diff/temp));};auto randint = [&](const int l, const int r){return mt()%(r - l) + l;};clock_t start = clock();for(int i = 0; i < N; i++){b[i] = randint(1, 10);m[i] = b[i];e[i] = 1;}ll cur_score = eval();double temperature = start_temp;double remaining_time = time_limit - (double)(clock()-start)/CLOCKS_PER_SEC;int max_db = 5;for(int iter = 0; ; iter++){if(iter%100 == 0){clock_t cur_time = clock();remaining_time = time_limit - (double)(cur_time-start)/CLOCKS_PER_SEC;temperature = end_temp + (start_temp-end_temp) * (remaining_time/time_limit);if(remaining_time < 0.0) {debug_value(iter)break;}}int idx = randint(0, N);int db = randint(0, max_db*2)-max_db;int prev_b = b[idx];b[idx] += db;chmax(b[idx], min_b);chmin(b[idx], max_b);m[idx] = b[idx];ll new_score = eval();if(accept_proba(new_score-cur_score, temperature) >= rand_dist(mt)){cur_score = new_score;}else{b[idx] = prev_b;m[idx] = prev_b;}}}void output(){for(int i = 0; i < N; i++) cout << b[i] << ' ' << m[i] << ' ' << e[i] << endl;}int main(){ios::sync_with_stdio(false);cin.tie(0);cout << setprecision(10) << fixed;input();solve(1.8);output();cerr << eval() << endl;}