結果

問題 No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
ユーザー butsurizukibutsurizuki
提出日時 2022-10-02 08:40:44
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,145 ms / 2,000 ms
コード長 3,511 bytes
コンパイル時間 4,093 ms
実行使用メモリ 6,952 KB
スコア 1,125,764,506,398,078
最終ジャッジ日時 2022-10-14 21:20:14
合計ジャッジ時間 72,420 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge10
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,118 ms
4,900 KB
testcase_01 AC 1,143 ms
4,904 KB
testcase_02 AC 1,122 ms
6,948 KB
testcase_03 AC 1,100 ms
6,948 KB
testcase_04 AC 1,120 ms
4,900 KB
testcase_05 AC 1,116 ms
4,900 KB
testcase_06 AC 1,112 ms
4,900 KB
testcase_07 AC 1,093 ms
4,900 KB
testcase_08 AC 1,138 ms
6,952 KB
testcase_09 AC 1,118 ms
4,900 KB
testcase_10 AC 1,098 ms
4,904 KB
testcase_11 AC 1,128 ms
4,904 KB
testcase_12 AC 1,112 ms
6,952 KB
testcase_13 AC 1,118 ms
6,948 KB
testcase_14 AC 1,121 ms
4,900 KB
testcase_15 AC 1,113 ms
4,904 KB
testcase_16 AC 1,119 ms
6,948 KB
testcase_17 AC 1,120 ms
4,904 KB
testcase_18 AC 1,128 ms
4,900 KB
testcase_19 AC 1,121 ms
4,904 KB
testcase_20 AC 1,129 ms
6,948 KB
testcase_21 AC 1,107 ms
4,900 KB
testcase_22 AC 1,128 ms
4,900 KB
testcase_23 AC 1,110 ms
4,900 KB
testcase_24 AC 1,137 ms
6,948 KB
testcase_25 AC 1,107 ms
6,948 KB
testcase_26 AC 1,115 ms
4,904 KB
testcase_27 AC 1,122 ms
4,904 KB
testcase_28 AC 1,113 ms
4,900 KB
testcase_29 AC 1,113 ms
6,952 KB
testcase_30 AC 1,099 ms
4,908 KB
testcase_31 AC 1,105 ms
4,904 KB
testcase_32 AC 1,113 ms
6,952 KB
testcase_33 AC 1,113 ms
4,904 KB
testcase_34 AC 1,106 ms
4,900 KB
testcase_35 AC 1,107 ms
4,904 KB
testcase_36 AC 1,097 ms
4,900 KB
testcase_37 AC 1,115 ms
6,948 KB
testcase_38 AC 1,113 ms
4,904 KB
testcase_39 AC 1,112 ms
6,948 KB
testcase_40 AC 1,114 ms
4,900 KB
testcase_41 AC 1,119 ms
6,948 KB
testcase_42 AC 1,111 ms
4,904 KB
testcase_43 AC 1,111 ms
4,900 KB
testcase_44 AC 1,100 ms
4,900 KB
testcase_45 AC 1,107 ms
4,908 KB
testcase_46 AC 1,107 ms
4,904 KB
testcase_47 AC 1,145 ms
6,948 KB
testcase_48 AC 1,111 ms
4,904 KB
testcase_49 AC 1,102 ms
4,900 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;}

  vector<pendulum> ans;
  vector<pendulum> plis;
  for(int b=1;b<=7;b++){
    for(int m=1;m<=b;m++){
      for(int e=1;e<=max(1,b-m);e++){
        plis.push_back({b,m,e});
      }
    }
  }

  long long maxsc=-1;
  vector<pendulum> res;
  for(int i=0;i<plis.size();i++){
    for(int j=0;j<i;j++){
      vector<pendulum> cres;
      for(int k=0;k<n;k++){
        if(k%2){cres.push_back(plis[i]);}
        else{cres.push_back(plis[j]);}
      }
      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