結果

問題 No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
ユーザー takumi152takumi152
提出日時 2022-10-15 00:59:56
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,902 ms / 2,000 ms
コード長 9,255 bytes
コンパイル時間 2,676 ms
実行使用メモリ 6,952 KB
スコア 853,844,885,311,915
最終ジャッジ日時 2022-10-15 01:01:45
合計ジャッジ時間 107,379 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge9
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,901 ms
4,900 KB
testcase_01 AC 1,902 ms
5,156 KB
testcase_02 AC 1,901 ms
4,904 KB
testcase_03 AC 1,901 ms
5,160 KB
testcase_04 AC 1,902 ms
4,900 KB
testcase_05 AC 1,901 ms
4,900 KB
testcase_06 AC 1,901 ms
4,904 KB
testcase_07 AC 1,902 ms
4,900 KB
testcase_08 AC 1,901 ms
4,908 KB
testcase_09 AC 1,902 ms
4,900 KB
testcase_10 AC 1,901 ms
4,904 KB
testcase_11 AC 1,902 ms
4,904 KB
testcase_12 AC 1,902 ms
4,904 KB
testcase_13 AC 1,902 ms
4,904 KB
testcase_14 AC 1,901 ms
5,156 KB
testcase_15 AC 1,902 ms
4,904 KB
testcase_16 AC 1,901 ms
5,156 KB
testcase_17 AC 1,902 ms
4,900 KB
testcase_18 AC 1,901 ms
5,160 KB
testcase_19 AC 1,901 ms
4,900 KB
testcase_20 AC 1,902 ms
4,900 KB
testcase_21 AC 1,901 ms
4,904 KB
testcase_22 AC 1,902 ms
4,904 KB
testcase_23 AC 1,902 ms
4,904 KB
testcase_24 AC 1,902 ms
5,156 KB
testcase_25 AC 1,902 ms
5,160 KB
testcase_26 AC 1,902 ms
5,160 KB
testcase_27 AC 1,902 ms
4,908 KB
testcase_28 AC 1,902 ms
5,156 KB
testcase_29 AC 1,902 ms
5,160 KB
testcase_30 AC 1,901 ms
5,160 KB
testcase_31 AC 1,902 ms
4,904 KB
testcase_32 AC 1,901 ms
5,156 KB
testcase_33 AC 1,902 ms
5,156 KB
testcase_34 AC 1,902 ms
4,904 KB
testcase_35 AC 1,901 ms
5,156 KB
testcase_36 AC 1,902 ms
5,156 KB
testcase_37 AC 1,901 ms
4,904 KB
testcase_38 AC 1,902 ms
5,160 KB
testcase_39 AC 1,902 ms
4,900 KB
testcase_40 AC 1,902 ms
5,164 KB
testcase_41 AC 1,901 ms
5,156 KB
testcase_42 AC 1,902 ms
4,908 KB
testcase_43 AC 1,902 ms
5,156 KB
testcase_44 AC 1,902 ms
4,904 KB
testcase_45 AC 1,902 ms
4,900 KB
testcase_46 AC 1,901 ms
6,952 KB
testcase_47 AC 1,901 ms
4,900 KB
testcase_48 AC 1,901 ms
4,904 KB
testcase_49 AC 1,902 ms
4,900 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 solve1() {
  auto 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;
  };

  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() > 0.100) 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 solve2() {
  auto calc_pendulum_pos = [](ll b, ll m, ll e, ll time) {
    ll decay_cycle_limit = (b * 2 - m * 2 + e * 2 - 1) / (e * 2);
    ll decay_end_time = (decay_cycle_limit * (b * 2 + (b * 2 - e * 2 * (decay_cycle_limit - 1)))) / 2;
    if (time < decay_end_time) {
      ll ng = -1;
      ll ok = decay_cycle_limit + 1;
      while (abs(ng - ok) > 1) {
        ll target_cycle = (ng + ok) / 2;
        ll cycle_end_time = (target_cycle * (b * 2 + (b * 2 - e * 2 * (target_cycle - 1)))) / 2;
        if (time < cycle_end_time) ok = target_cycle;
        else ng = target_cycle;
      }
      ll direction = (ok % 2 != 0) ? 1 : -1;
      ll in_cycle_time = time - ((ok - 1) * (b * 2 + (b * 2 - e * 2 * (ok - 2)))) / 2;
      ll cycle_length = b * 2 - e * 2 * (ok - 1);
      // if (in_cycle_time < 0 || cycle_length <= in_cycle_time) {
      //   cerr << b << " " << m << " " << e << " " << time << " " << ok << " " << in_cycle_time << " " << cycle_length << " " << ((ok - 1) * (b * 2 + (b * 2 - e * 2 * (ok - 2)))) / 2 << " " << decay_cycle_limit << " " << decay_end_time << endl;
      //   assert(false);
      // }
      if (in_cycle_time <= cycle_length / 2) return in_cycle_time * direction;
      else return (cycle_length * 2 - in_cycle_time) * direction;
    }
    else {
      ll direction = (decay_cycle_limit % 2 == 0) ? 1 : -1;
      ll in_cycle_time = (time - decay_end_time) % (m * 2);
      if (in_cycle_time <= m) return in_cycle_time * direction;
      else return (m * 2 - in_cycle_time) * direction;
    }
  };

  ll best_score = 0;
  ll best_b1 = 1;
  ll best_m1 = 1;
  ll best_e1 = 1;
  ll best_b2 = 1;
  ll best_m2 = 1;
  ll best_e2 = 1;
  for (ll b1 = 1; ; b1++) {
    for (ll m1 = b1; m1 >= 1; m1--) {
      for (ll e1 = 1; e1 < b1 - m1 + 1; e1++) {
        for (ll b2 = 1; b2 <= b1; b2++) {
          for (ll m2 = b2; m2 >= 1; m2--) {
            for (ll e2 = 1; e2 < b2 - m2 + 1; e2++) {
              ll t_score = 0;
              ll u_score = 0;
              for (int i = 0; i < k; i++) {
                ll pos1 = calc_pendulum_pos(b1, m1, e1, t[i]);
                ll pos2 = calc_pendulum_pos(b2, m2, e2, t[i]);
                t_score += (ll)(1e7 * (double) abs(pos1 - pos2) / (double) (b1 + b2));
              }
              for (int i = 0; i < k; i++) {
                ll pos1 = calc_pendulum_pos(b1, m1, e1, u[i]);
                ll pos2 = calc_pendulum_pos(b2, m2, e2, 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) {
                cerr << b1 << " " << m1 << " " << e1 << " " << b2 << " " << m2 << " " << e2 << " " << t_score / k << " " << u_score / k << " " << total_score << endl;
                best_score = total_score;
                best_b1 = b1;
                best_m1 = m1;
                best_e1 = e1;
                best_b2 = b2;
                best_m2 = m2;
                best_e2 = e2;
              }
            }
            if (theTimer.time() > 1.900) break;
          }
          if (theTimer.time() > 1.900) break;
        }
        if (theTimer.time() > 1.900) break;
      }
      if (theTimer.time() > 1.900) break;
    }
    if (theTimer.time() > 1.900) break;
  }

  cerr << "score = " << best_score << endl;
  
  for (int i = 0; i < n / 2; i++) {
    b[i] = best_b1;
    m[i] = best_m1;
    e[i] = best_e1;
  }
  for (int i = n / 2; i < n; i++) {
    b[i] = best_b2;
    m[i] = best_m2;
    e[i] = best_e2;
  }
}

void solve() {
  // solve1();
  solve2();
}

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