結果

問題 No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
コンテスト
ユーザー butsurizuki
提出日時 2022-10-02 09:13:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,489 ms / 2,000 ms
コード長 3,427 bytes
コンパイル時間 4,642 ms
実行使用メモリ 6,952 KB
スコア 1,331,083,020,006,872
最終ジャッジ日時 2022-10-14 21:20:31
合計ジャッジ時間 87,626 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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;}

  vector<pendulum> res;
  for(int i=0;i<n;i++){
    int b=1+get_rand(5,engine);
    int m=b;
    int e=1;
    res.push_back({b,m,e});
  }
  long long maxsc=eval(res,false);

  for(int i=0;i<2000;i++){
    int tg=get_rand(n,engine);
    int nb=1+get_rand(5,engine);
    int nm=nb;
    int ne=1;
    pendulum old=res[tg];
    pendulum newp={nb,nm,ne};
    res[tg]=newp;
    long long cursc=eval(res,false);
    if(maxsc<=cursc){
      maxsc=cursc;
    }
    else{res[tg]=old;}
  }

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