結果

問題 No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
ユーザー butsurizukibutsurizuki
提出日時 2022-10-02 08:59:55
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,931 ms / 2,000 ms
コード長 3,261 bytes
コンパイル時間 4,216 ms
実行使用メモリ 6,952 KB
スコア 1,193,418,636,119,454
最終ジャッジ日時 2022-10-14 21:19:21
合計ジャッジ時間 98,553 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,743 ms
4,900 KB
testcase_01 AC 1,672 ms
4,900 KB
testcase_02 AC 1,708 ms
6,948 KB
testcase_03 AC 1,718 ms
6,952 KB
testcase_04 AC 1,931 ms
4,904 KB
testcase_05 AC 1,768 ms
6,948 KB
testcase_06 AC 1,720 ms
6,948 KB
testcase_07 AC 1,696 ms
4,904 KB
testcase_08 AC 1,739 ms
4,904 KB
testcase_09 AC 1,693 ms
4,900 KB
testcase_10 AC 1,751 ms
4,904 KB
testcase_11 AC 1,665 ms
4,904 KB
testcase_12 AC 1,714 ms
6,952 KB
testcase_13 AC 1,741 ms
4,900 KB
testcase_14 AC 1,673 ms
4,904 KB
testcase_15 AC 1,752 ms
4,904 KB
testcase_16 AC 1,663 ms
4,904 KB
testcase_17 AC 1,706 ms
6,952 KB
testcase_18 AC 1,698 ms
4,904 KB
testcase_19 AC 1,664 ms
4,904 KB
testcase_20 AC 1,656 ms
4,900 KB
testcase_21 AC 1,738 ms
4,900 KB
testcase_22 AC 1,687 ms
6,948 KB
testcase_23 AC 1,697 ms
4,904 KB
testcase_24 AC 1,711 ms
4,904 KB
testcase_25 AC 1,683 ms
4,900 KB
testcase_26 AC 1,701 ms
4,900 KB
testcase_27 AC 1,729 ms
6,948 KB
testcase_28 AC 1,700 ms
6,948 KB
testcase_29 AC 1,708 ms
4,904 KB
testcase_30 AC 1,693 ms
6,952 KB
testcase_31 AC 1,706 ms
4,904 KB
testcase_32 AC 1,738 ms
6,948 KB
testcase_33 AC 1,738 ms
4,904 KB
testcase_34 AC 1,714 ms
4,904 KB
testcase_35 AC 1,700 ms
4,904 KB
testcase_36 AC 1,701 ms
6,948 KB
testcase_37 AC 1,727 ms
6,952 KB
testcase_38 AC 1,747 ms
4,904 KB
testcase_39 AC 1,692 ms
4,904 KB
testcase_40 AC 1,766 ms
4,900 KB
testcase_41 AC 1,708 ms
6,948 KB
testcase_42 AC 1,715 ms
6,948 KB
testcase_43 AC 1,701 ms
6,948 KB
testcase_44 AC 1,713 ms
4,904 KB
testcase_45 AC 1,782 ms
6,948 KB
testcase_46 AC 1,737 ms
4,904 KB
testcase_47 AC 1,684 ms
4,904 KB
testcase_48 AC 1,702 ms
6,952 KB
testcase_49 AC 1,740 ms
6,952 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

using namespace std;

typedef struct{
  int b;
  int m;
  int e;
}pendulum;

int getpos(int tim,pendulum &p){
  int b=p.b;
  int m=p.m;
  int e=p.e;
  int mg=(b-m)/e;
  long long st=0,fi=2e9;
  while(st<=fi){
    long long te=(st+fi)/2;
    long long val;

    if(te<=mg){
      long long fir=b;
      long long las=b-te*e;

      val=(fir+las);
      val*=(te+1);
    }
    else{
      long long fir=b;
      long long las=b-mg*e;

      val=(fir+las);
      val*=(mg+1);

      long long add=m;
      add*=(te-mg);
      add*=2;

      val+=add;
    }

    if(val<tim){st=te+1;}
    else{fi=te-1;}
  }

  long long subt=fi;
  long long val=0;
  if(subt>=0){
    if(subt<=mg){
      long long fir=b;
      long long las=b-subt*e;

      val=(fir+las);
      val*=(subt+1);
    }
    else{
      long long fir=b;
      long long las=b-mg*e;

      val=(fir+las);
      val*=(mg+1);

      long long add=m;
      add*=(subt-mg);
      add*=2;

      val+=add;
    }
  }

  long long jud=tim-val;
  long long len;
  if(st<=mg){len=b-st*e;}
  else{len=m;}

  long long ce=1;
  if(st%2){ce=-1;}
  if(jud<=len){return ce*jud;}
  else{return ce*(2*len-jud);}
}

int n,k;
vector<int> t,u;

long long eval(vector<pendulum> &sol,bool debug){
  // tairitsu
  double t_all=0.0;
  for(auto &nx : t){
    double t_cur=0.0;
    vector<double> x;
    for(auto &ny : sol){
      x.push_back(getpos(nx,ny));
    }
    for(int i=0;i<n;i++){
      for(int j=i+1;j<n;j++){
        double del=abs(x[i]-x[j]);
        del/=((double)(sol[i].b+sol[j].b));
        t_cur+=del;
      }
    }
    t_cur*=2.0e7;
    t_cur/=((double)(n*(n-1)));
    t_all+=round(t_cur);
    if(debug){cerr << ((int)round(t_cur)) << "\n";}
  }
  t_all/=((double)k);
  if(debug){cerr << "\n";}

  // kyoucyou
  double k_all=0.0;
  for(auto &nx : u){
    double k_cur=0.0;
    vector<double> x;
    for(auto &ny : sol){
      x.push_back(getpos(nx,ny));
    }
    for(int i=0;i<n;i++){
      for(int j=i+1;j<n;j++){
        k_cur=max(k_cur,abs(x[i]-x[j]));
      }
    }
    k_cur/=20.0;
    k_cur+=1.0;
    k_cur=1.0e7/sqrt(k_cur);
    k_all+=round(k_cur);
    if(debug){cerr << ((int)round(k_cur)) << "\n";}
  }
  k_all/=((double)k);
  if(debug){cerr << "\n";}

  long long rt=(t_all+0.5);
  long long rk=(k_all+0.5);
  if(debug){
    cerr << rt << "\n";
    cerr << rk << "\n";
    cerr << rt*rk << "\n";
  }
  return rt*rk;
}

long long get_rand(long long lim,mt19937_64 &eg){
  return (long long)(eg()%lim);
}

int main(){
  std::random_device seed_gen;
  std::mt19937_64 engine(seed_gen());

  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> k;
  t.resize(k);
  u.resize(k);
  for(auto &nx : t){cin >> nx;}
  for(auto &nx : u){cin >> nx;}

  long long maxsc=-1;
  vector<pendulum> res;
  for(int i=2;i<3500;i++){
    vector<pendulum> cres;
    for(int k=0;k<n;k++){
      if(k%2){cres.push_back({1,1,1});}
      else{cres.push_back({i,i,1});}
    }
    long long cursc=eval(cres,false);
    if(maxsc<cursc){
      maxsc=cursc;
      res=cres;
    }
  }

  for(auto &nx : res){
    cout << nx.b << " " << nx.m << " " << nx.e << "\n";
  }
  eval(res,true);
  return 0;
}
0