#807457 (C++14) No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance

提出ソース

結果

問題	No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
ユーザー	SSRS
提出日時	2022-10-15 00:03:45
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	340 ms / 2,000 ms
コード長	4,292 bytes
コンパイル時間	1,868 ms
実行使用メモリ	6,952 KB
スコア	1,417,917,513,288,746
最終ジャッジ日時	2022-10-15 00:04:19
合計ジャッジ時間	27,239 ms
ジャッジサーバーID （参考情報）	judge13 / judge11
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	319 ms 6,948 KB
testcase_01	AC	319 ms 4,904 KB
testcase_02	AC	338 ms 4,904 KB
testcase_03	AC	317 ms 4,904 KB
testcase_04	AC	317 ms 6,948 KB
testcase_05	AC	333 ms 4,904 KB
testcase_06	AC	321 ms 4,900 KB
testcase_07	AC	334 ms 4,904 KB
testcase_08	AC	330 ms 4,908 KB
testcase_09	AC	326 ms 6,948 KB
testcase_10	AC	318 ms 6,948 KB
testcase_11	AC	334 ms 4,900 KB
testcase_12	AC	318 ms 4,904 KB
testcase_13	AC	316 ms 4,900 KB
testcase_14	AC	330 ms 4,904 KB
testcase_15	AC	319 ms 4,904 KB
testcase_16	AC	319 ms 4,900 KB
testcase_17	AC	337 ms 4,904 KB
testcase_18	AC	319 ms 6,948 KB
testcase_19	AC	317 ms 4,904 KB
testcase_20	AC	334 ms 4,900 KB
testcase_21	AC	320 ms 4,900 KB
testcase_22	AC	317 ms 6,948 KB
testcase_23	AC	333 ms 4,900 KB
testcase_24	AC	316 ms 4,904 KB
testcase_25	AC	314 ms 4,904 KB
testcase_26	AC	336 ms 4,900 KB
testcase_27	AC	319 ms 4,908 KB
testcase_28	AC	320 ms 4,900 KB
testcase_29	AC	332 ms 4,904 KB
testcase_30	AC	318 ms 4,900 KB
testcase_31	AC	322 ms 4,900 KB
testcase_32	AC	332 ms 6,948 KB
testcase_33	AC	315 ms 6,952 KB
testcase_34	AC	318 ms 4,904 KB
testcase_35	AC	331 ms 4,900 KB
testcase_36	AC	318 ms 4,904 KB
testcase_37	AC	326 ms 4,904 KB
testcase_38	AC	329 ms 4,900 KB
testcase_39	AC	324 ms 4,900 KB
testcase_40	AC	315 ms 4,900 KB
testcase_41	AC	340 ms 4,904 KB
testcase_42	AC	316 ms 6,948 KB
testcase_43	AC	323 ms 4,900 KB
testcase_44	AC	333 ms 4,900 KB
testcase_45	AC	333 ms 4,900 KB
testcase_46	AC	326 ms 4,904 KB
testcase_47	AC	325 ms 4,900 KB
testcase_48	AC	334 ms 4,900 KB
testcase_49	AC	329 ms 4,900 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
long long ap(long long a, long long d, long long n){
  return (2 * a + (n - 1) * d) * n / 2;
}
int get(int B, int M, int E, int t){
  int cnt = (B - M) / E + 1;
  long long T = ap(B * 2, -E * 2, cnt);
  if (t <= T){
    int tv = 0, fv = (B - M) / E + 1;
    while (fv - tv > 1){
      int mid = (tv + fv) / 2;
      if (ap(B * 2, -E * 2, mid) <= t){
        tv = mid;
      } else {
        fv = mid;
      }
    }
    long long t2 = ap(B * 2, -E * 2, tv);
    t -= t2;
    if (tv % 2 == 0){
      int a = B - E * tv;
      if (t <= a){
        return t;
      } else {
        return a * 2 - t;
      }
    } else {
      int a = B - E * tv;
      if (t <= a){
        return -t;
      } else {
        return -(a * 2 - t);
      }
    }
  } else {
    t -= T;
    t %= M * 4;
    int ans;
    if (t < M){
      ans = t;
    } else if (t < M * 3){
      ans = M * 2 - t;
    } else {
      ans = t - M * 4;
    }
    if (cnt % 2 == 1){
      ans *= -1;
    }
    return ans;
  }
}
long long get_score_1(int N, int K, vector<int> &T, vector<int> &B, vector<int> &M, vector<int> &E){
  long long S = 0;
  for (int i = 0; i < K; i++){
    vector<int> X(N);
    for (int j = 0; j < N; j++){
      X[j] = get(B[j], M[j], E[j], T[i]);
    }
    double ans = 0;
    for (int j = 0; j < N; j++){
      for (int k = j + 1; k < N; k++){
        ans += (double) abs(X[j] - X[k]) / (B[j] + B[k]);
      }
    }
    ans *= 20000000;
    ans /= N;
    ans /= N - 1;
    S += ans;
  }
  return S;
}
long long get_score_2(int N, int K, vector<int> &U, vector<int> &B, vector<int> &M, vector<int> &E){
  long long S = 0;
  for (int i = 0; i < K; i++){
    vector<int> X(N);
    for (int j = 0; j < N; j++){
      X[j] = get(B[j], M[j], E[j], U[i]);
    }
    int mx = 0;
    for (int j = 0; j < N; j++){
      for (int k = j + 1; k < N; k++){
        mx = max(mx, abs(X[k] - X[j]));
      }
    }
    double ans = (double) mx / 20 + 1;
    ans = 10000000 / sqrt(ans);
    S += ans;
  }
  return S;
}
long long get_score(int N, int K, vector<int> &T, vector<int> &U, vector<int> &B, vector<int> &M, vector<int> &E){
  long long S1 = get_score_1(N, K, T, B, M, E) / K;
  long long S2 = get_score_2(N, K, U, B, M, E) / K;
  return S1 * S2;
}
void generate(int K, vector<int> &T, vector<int> &U){
  int D = 200;
  vector<int> G(K * 2 + 1);
  mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
  uniform_real_distribution<> dist(0.0, 1.0);
  while (true){
    vector<double> F(K * 2, 0);
    for (int i = 0; i < K * 2; i++){
      while (F[i] == 0){
        F[i] = dist(mt);
      }
    }
    G[0] = 0;
    bool ok = true;
    for (int i = 0; i < K * 2; i++){
      int c = D / F[i];
      if (G[i] + c > 1000000000){
        ok = false;
        break;
      }
      G[i + 1] = G[i] + c;
    }
    if (ok){
      break;
    }
  }
  T.resize(K);
  U.resize(K);
  for (int i = 0; i < K; i++){
    T[i] = G[i * 2 + 1];
    U[i] = G[i * 2 + 2];
  }
  if (mt() % 2 == 0){
    swap(T, U);
  }
}
void solve(int N, int K, vector<int> &T, vector<int> &U, vector<int> &B, vector<int> &M, vector<int> &E){
  mt19937 mt(0);
  B.resize(N);
  M.resize(N);
  E.resize(N);
  for (int i = 0; i < N; i++){
    B[i] = mt() % 10 + 1;
    M[i] = mt() % B[i] + 1;
    E[i] = mt() % 3 + 1;
  }
  long long mx = get_score(N, K, T, U, B, M, E);
  for (int i = 0; i < 1000; i++){
    int p = mt() % N;
    vector<int> B2 = B, M2 = M, E2 = E;
    B2[p] = mt() % 10 + 1;
    M2[p] = mt() % B2[p] + 1;
    E2[p] = mt() % 3 + 1;
    long long x = get_score(N, K, T, U, B2, M2, E2);
    if (x > mx){
      mx = x;
      B = B2;
      M = M2;
      E = E2;
    }
  }
}
long long test(int N, int K){
  long long ans = 0;
  for (int i = 0; i < 50; i++){
    vector<int> T, U;
    generate(K, T, U);
    vector<int> B, M, E;
    solve(N, K, T, U, B, M, E);
    ans += get_score(N,  K, T, U, B, M, E);
  }
  return ans;
}
int main(){
  //cout << test(50, 50) << endl;
  int N, K;
  cin >> N >> K;
  vector<int> T(N);
  for (int i = 0; i < N; i++){
    cin >> T[i];
  }
  vector<int> U(N);
  for (int i = 0; i < N; i++){
    cin >> U[i];
  }
  vector<int> B, M, E;
  solve(N, K, T, U, B, M, E);
  for (int i = 0; i < N; i++){
    cout << B[i] << ' ' << M[i] << ' ' << E[i] << endl;
  }
}

yukicoder

結果

テストケース

ソースコード