結果

問題 No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
ユーザー takumi152takumi152
提出日時 2022-10-14 23:21:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,905 ms / 2,000 ms
コード長 5,395 bytes
コンパイル時間 2,246 ms
実行使用メモリ 6,956 KB
スコア 1,193,418,636,119,454
最終ジャッジ日時 2022-10-14 23:22:59
合計ジャッジ時間 107,785 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,903 ms
4,908 KB
testcase_01 AC 1,904 ms
4,904 KB
testcase_02 AC 1,903 ms
4,900 KB
testcase_03 AC 1,905 ms
4,900 KB
testcase_04 AC 1,903 ms
4,900 KB
testcase_05 AC 1,903 ms
4,900 KB
testcase_06 AC 1,902 ms
6,948 KB
testcase_07 AC 1,904 ms
4,900 KB
testcase_08 AC 1,902 ms
6,952 KB
testcase_09 AC 1,903 ms
4,904 KB
testcase_10 AC 1,905 ms
4,900 KB
testcase_11 AC 1,902 ms
6,948 KB
testcase_12 AC 1,903 ms
4,904 KB
testcase_13 AC 1,902 ms
4,900 KB
testcase_14 AC 1,903 ms
4,904 KB
testcase_15 AC 1,905 ms
4,900 KB
testcase_16 AC 1,902 ms
6,956 KB
testcase_17 AC 1,901 ms
4,904 KB
testcase_18 AC 1,904 ms
4,900 KB
testcase_19 AC 1,903 ms
4,904 KB
testcase_20 AC 1,902 ms
4,904 KB
testcase_21 AC 1,905 ms
4,904 KB
testcase_22 AC 1,903 ms
4,900 KB
testcase_23 AC 1,903 ms
4,900 KB
testcase_24 AC 1,903 ms
4,900 KB
testcase_25 AC 1,901 ms
4,900 KB
testcase_26 AC 1,904 ms
4,900 KB
testcase_27 AC 1,904 ms
4,904 KB
testcase_28 AC 1,902 ms
4,908 KB
testcase_29 AC 1,903 ms
6,948 KB
testcase_30 AC 1,904 ms
4,900 KB
testcase_31 AC 1,903 ms
6,948 KB
testcase_32 AC 1,904 ms
6,948 KB
testcase_33 AC 1,902 ms
4,900 KB
testcase_34 AC 1,904 ms
4,904 KB
testcase_35 AC 1,902 ms
4,904 KB
testcase_36 AC 1,904 ms
4,900 KB
testcase_37 AC 1,904 ms
4,900 KB
testcase_38 AC 1,903 ms
4,900 KB
testcase_39 AC 1,902 ms
6,952 KB
testcase_40 AC 1,903 ms
4,904 KB
testcase_41 AC 1,902 ms
4,904 KB
testcase_42 AC 1,903 ms
6,952 KB
testcase_43 AC 1,902 ms
3,396 KB
testcase_44 AC 1,903 ms
4,904 KB
testcase_45 AC 1,904 ms
4,904 KB
testcase_46 AC 1,902 ms
6,952 KB
testcase_47 AC 1,903 ms
4,904 KB
testcase_48 AC 1,903 ms
4,900 KB
testcase_49 AC 1,902 ms
6,952 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <unordered_set>
#include <random>
#include <cmath>
#include <cassert>

#include <x86intrin.h>

struct xorshift64 {
  unsigned long long int x = 88172645463325252ULL;
  inline unsigned short nextUShort() {
    x = x ^ (x << 7);
    return x = x ^ (x >> 9);
  }
  inline unsigned int nextUShortMod(unsigned long long int mod) {
    x = x ^ (x << 7);
    x = x ^ (x >> 9);
    return ((x & 0x0000ffffffffffff) * mod) >> 48;
  }
  inline unsigned int nextUInt() {
    x = x ^ (x << 7);
    return x = x ^ (x >> 9);
  }
  inline unsigned int nextUIntMod(unsigned long long int mod) {
    x = x ^ (x << 7);
    x = x ^ (x >> 9);
    return ((x & 0x00000000ffffffff) * mod) >> 32;
  }
  inline unsigned long long int nextULL() {
    x = x ^ (x << 7);
    return x = x ^ (x >> 9);
  }
  inline double nextDouble() {
    x = x ^ (x << 7);
    x = x ^ (x >> 9);
    return (double)x * 5.42101086242752217e-20;
  }
};

struct timer {
  double t = 0.0;
  double lastStop = 0.0;
  bool stopped = false;
  timer() {
    restart();
  }
  inline void restart() {
    t = now();
    stopped = false;
  }
  inline void start() {
    if (stopped) {
      t += now() - lastStop;
      stopped = false;
    }
  }
  inline void stop() {
    if (!stopped) {
      lastStop = now();
      stopped = true;
    }
  }
  inline double time() {
    if (stopped) return lastStop - t;
    else return now() - t;
  }
  inline double now() {
    unsigned long long l, h;
    __asm__ ("rdtsc" : "=a"(l), "=d"(h));
    #ifdef LOCAL
    return (double)(l | h << 32) * 2.857142857142857e-10; // 1 / 3.5e9, for local (Ryzen 9 3950X)
    #else
    // return (double)(l | h << 32) * 3.5714285714285715e-10; // 1 / 2.8e9, for AWS EC2 C3 (Xeon E5-2680 v2)
    // return (double)(l | h << 32) * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C4 (Xeon E5-2666 v3)
    // return (double)(l | h << 32) * 3.333333333333333e-10; // 1 / 3.0e9, for AWS EC2 C5 (Xeon Platinum 8124M / Xeon Platinum 8275CL)
    return (double)(l | h << 32) * 4.3478260869565215e-10; // 1 / 2.3e9, for yukicoder judge
    #endif
  }
};

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int, int> Pii;

const ll mod = 1000000007;

timer theTimer;
xorshift64 theRandom;
mt19937 theMersenne(1);

// hyper parameters

// enums

// structs

// constants
constexpr int n = 50;
constexpr int k = 50;

// inputs
array<int, k> t, u;

// outputs
array<int, n> b, m, e;

// internals

void receive_input() {
  int _n, _k;
  cin >> _n >> _k;
  for (int i = 0; i < k; i++) cin >> t[i];
  for (int i = 0; i < k; i++) cin >> u[i];
}

void init() {
}

inline ll calc_pendulum_pos(ll bm, ll time) {
  ll in_cycle_time = time % (bm * 4);
  if (in_cycle_time <= bm) return in_cycle_time;
  else if (in_cycle_time <= bm * 3) return bm * 2 - in_cycle_time;
  else return in_cycle_time - bm * 4;
}

void solve() {
  ll best_score = 0;
  ll best_bm1 = -1;
  ll best_bm2 = -1;
  for (int bm1 = 1; bm1 * 3 < min(t[0], u[0]); bm1++) {
    ll t_score = 0;
    ll u_score = 0;
    for (int i = 0; i < k; i++) {
        ll pos1 = calc_pendulum_pos(bm1, t[i]);
        ll pos2 = -pos1;
        t_score += (ll)(1e7 * (double) abs(pos1 - pos2) / (double) (bm1 * 3));
    }
    for (int i = 0; i < k; i++) {
        ll pos1 = calc_pendulum_pos(bm1, u[i]);
        ll pos2 = -pos1;
        u_score += (ll)(1e7 / (sqrt(abs(pos1 - pos2) / 20.0 + 1.0)));
    }
    ll total_score = (t_score / k) * (u_score / k);
    if (total_score > best_score) {
      best_score = total_score;
      best_bm1 = bm1;
      best_bm2 = -1;
    }
  }

  for (ll bm1 = 1; ; bm1++) {
    for (ll bm2 = 1; bm2 <= bm1; bm2++) {
      ll t_score = 0;
      ll u_score = 0;
      for (int i = 0; i < k; i++) {
        ll pos1 = calc_pendulum_pos(bm1, t[i]);
        ll pos2 = calc_pendulum_pos(bm2, t[i]);
        t_score += (ll)(1e7 * (double) abs(pos1 - pos2) / (double) (bm1 + bm2));
      }
      for (int i = 0; i < k; i++) {
        ll pos1 = calc_pendulum_pos(bm1, u[i]);
        ll pos2 = calc_pendulum_pos(bm2, u[i]);
        u_score += (ll)(1e7 / (sqrt(abs(pos1 - pos2) / 20.0 + 1.0)));
      }
      ll total_score = (t_score / k) * (u_score / k);
      if (total_score > best_score) {
        best_score = total_score;
        best_bm1 = bm1;
        best_bm2 = bm2;
      }
    }
    if (theTimer.time() > 1.900) break;
  }

  cerr << "score = " << best_score << endl;

  if (best_bm2 == -1) {
    for (int i = 0; i < n / 2; i++) {
      b[i] = best_bm1 * 2;
      m[i] = best_bm1;
      e[i] = best_bm1;
    }
    for (int i = n / 2; i < n; i++) {
      b[i] = best_bm1;
      m[i] = best_bm1;
      e[i] = 1;
    }
  }
  else {
    for (int i = 0; i < n / 2; i++) {
      b[i] = best_bm1;
      m[i] = best_bm1;
      e[i] = 1;
    }
    for (int i = n / 2; i < n; i++) {
      b[i] = best_bm2;
      m[i] = best_bm2;
      e[i] = 1;
    }
  }
}

void output_ans() {
  for (int i = 0; i < n; i++) cout << b[i] << " " << m[i] << " " << e[i] << endl;
}

int main(int argc, char *argv[]) {
  cin.tie(0);
  ios::sync_with_stdio(false);

  receive_input();

  init();
  solve();

  output_ans();

  return 0;
}
0