結果

問題 No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
ユーザー butsurizuki
提出日時 2022-10-02 08:59:55
言語 C++23
(gcc 13.3.0 + boost 1.87.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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

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