#807609 (C++17(gcc12)) No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance

• 問題: No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
• ユーザー: takumi152
• 提出日時: 2022-10-15 01:14:55
• 言語: C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,902 ms / 2,000 ms
• コード長: 9,041 bytes
• コンパイル時間: 2,572 ms
• 実行使用メモリ: 6,952 KB
• スコア: 1,185,627,241,981,039
• 最終ジャッジ日時: 2022-10-15 01:16:42
• 合計ジャッジ時間: 107,481 ms
• ジャッジサーバーID （参考情報）: judge13 / judge9

ファイルパターン	結果
other	AC * 50

ソースコード

#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 b2 = b * 2;
    ll m2 = m * 2;
    ll e2 = e * 2;
    ll decay_cycle_limit = ((b2 - m2) + e2 - 1) / e2;
    ll decay_end_time = (decay_cycle_limit * (b2 + (b2 - e2 * (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 * (b2 + (b2 - e2 * (target_cycle - 1)))) / 2;
        if (time < cycle_end_time) ok = target_cycle;
        else ng = target_cycle;
      }
      ll direction = ((ok - 1) % 2 == 0) ? 1 : -1;
      ll in_cycle_time = time - ((ok - 1) * (b2 + (b2 - e2 * (ok - 2)))) / 2;
      ll cycle_length = b2 - e2 * (ok - 1);
      if (in_cycle_time < 0 || cycle_length <= in_cycle_time) {
        assert(false);
      }
      if (in_cycle_time <= cycle_length / 2) return in_cycle_time * direction;
      else return (cycle_length - in_cycle_time) * direction;
    }
    else {
      ll direction = ((decay_cycle_limit + (time - decay_end_time) / m2) % 2 == 0) ? 1 : -1;
      ll in_cycle_time = (time - decay_end_time) % m2;
      if (in_cycle_time <= m) return in_cycle_time * direction;
      else return (m2 - 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;
}