結果
問題 | No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance |
ユーザー |
![]() |
提出日時 | 2022-10-14 23:07:12 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,997 ms / 2,000 ms |
コード長 | 4,884 bytes |
コンパイル時間 | 1,600 ms |
実行使用メモリ | 5,160 KB |
スコア | 81,040,523,911,357 |
最終ジャッジ日時 | 2022-10-14 23:09:02 |
合計ジャッジ時間 | 109,849 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
#pragma GCC optimize("Ofast")#include <iostream>#include <algorithm>#include <string>#include <cstdlib>#include <cmath>#include <iomanip>#include <cctype>#include <sstream>#include <vector>#include <stack>#include <deque>#include <queue>#include <list>#include <set>#include <map>#include <unordered_map>#include <chrono>#include <random>using namespace std;using ll = long long;using P = pair<int, int>;template <class T>using V = vector<T>;template <class T>using VV = V<V<T>>;template <class T, class U>bool chmin(T& t, const U& u) { if (t > u) { t = u; return 1; } else return 0; }template <class T, class U>bool chmax(T& t, const U& u) { if (t < u) { t = u; return 1; } else return 0; }#define REP(i,n) for(int i=0;i<int(n);i++)#define FOR(i,a,b) for(int i=int(a);i<=int(b);i++)#define FORD(i,a,b) for(int i=int(a);i>=int(b);i--)#define MP make_pair#define SZ(x) int(x.size())#define ALL(x) x.begin(),x.end()#define INF 10001000#define endl "\n"chrono::system_clock::time_point t_start;const double TIME_LIMIT1 = 500, TIME_LIMIT = 1930;double last_update = 0, t_diff;double start_temp, end_temp;mt19937 rng;using uni_int = uniform_int_distribution<>;using uni_real = uniform_real_distribution<>;using u64 = uint64_t;using u32 = uint32_t;V<int> y_vec = { 0, 1,0, -1 };V<int> x_vec = { -1, 0,1, 0 };class XorInt {public:uint32_t x = 2463534242;XorInt() {};XorInt(uint32_t seed) {x = 2463534242 + seed;};uint32_t next() {x ^= x << 13; x ^= x >> 17; x ^= x << 5;return x;}uint32_t operator()(uint32_t l, uint32_t r) {return (this->next() % (r - l)) + l;}uint32_t operator()(uint32_t d) {return this->next() % d;}};XorInt xs;class Xor64 {public:uint64_t x = 88172645463325252ULL;Xor64() {};Xor64(uint64_t seed) {x = 88172645463325252ULL + seed;}uint64_t next() {x ^= x << 13; x ^= x >> 7; x ^= x << 17;return x;}uint64_t operator()(uint64_t l, uint64_t r) {return (this->next() % (r - l)) + l;}uint64_t operator()(uint64_t d) {return this->next() % d;}};Xor64 xx;void get_time() {auto t_now = chrono::system_clock::now();t_diff = chrono::duration_cast<chrono::milliseconds>(t_now - t_start).count();}int N, K;int MAX = 0;V<int> t, u;class Pendulum {public:int b=0;int m=0;int e = 0;V<int> enemy;V<int> group;Pendulum(int b, int m, int e) :b(max(b,m)), m(m), e(e) {int pos = 0;int count = 0;int amp = b;int dir = 1;FOR(time, 0, MAX) {if (time == t[count / 2]) {enemy.push_back(pos);count++;}else if (time == u[count / 2]) {group.push_back(pos);count++;}pos += dir;if (pos == amp * dir) {dir *= -1;amp = max(m, amp - e);}}};};V<Pendulum> pends,bestPends;ll getScore() {ll st = 0;ll su = 0;REP(k, K) {double x = 0.0;REP(i, N)REP(j, i) {x += double(abs(pends[i].enemy[k] - pends[j].enemy[k])) / (pends[i].b + pends[j].b);}x *= 20000000.0;x /= (double(N) * (N - 1));st += round(x);}st /= K;REP(k, K) {int ma_dis = 0;REP(i, N)REP(j, i) {chmax(ma_dis, abs(pends[i].group[k] - pends[j].group[k]));}double x = ma_dis;x /= 20.0;x += 1;su += round(10000000 / x);}su /= K;return st * su;}signed main() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);cerr << fixed << setprecision(15);t_start = chrono::system_clock::now();get_time();int cnt = 0;cin >> N >> K;t = V<int>(N);u = V<int>(N);REP(i, N)cin >> t[i];REP(i, N)cin >> u[i];MAX = max(t.back(), u.back());int bestScore = 0;int B = 10000;int M = 10000;int E = 10000;while (t_diff < TIME_LIMIT) {pends = V<Pendulum>();REP(i, N) {pends.push_back(Pendulum(xs(1, B+1), xs(1, M+1), xs(1, E+1)));}int score = getScore();if (chmax(bestScore, score)) {bestPends = pends;}get_time();cnt++;}REP(i, N) {cout << bestPends[i].b << " " << bestPends[i].m << " " << bestPends[i].e << endl;}get_time();cerr << "time=" << int(t_diff) << " ms" << endl;cerr << "score=" << bestScore << endl;//cerr << "last=" << last_update << endl;cerr << "cnt=" << cnt << endl;//cerr << "update=" << update_cnt << endl;return 0;}