結果

問題 No.5007 Steiner Space Travel
ユーザー monnumonnu
提出日時 2022-07-30 15:44:34
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 828 ms / 1,000 ms
コード長 3,366 bytes
コンパイル時間 3,530 ms
実行使用メモリ 5,160 KB
スコア 8,128,181
最終ジャッジ日時 2022-07-30 15:45:05
合計ジャッジ時間 30,048 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 805 ms
4,904 KB
testcase_01 AC 804 ms
4,900 KB
testcase_02 AC 805 ms
4,904 KB
testcase_03 AC 805 ms
4,908 KB
testcase_04 AC 805 ms
4,904 KB
testcase_05 AC 805 ms
4,904 KB
testcase_06 AC 805 ms
4,900 KB
testcase_07 AC 805 ms
4,904 KB
testcase_08 AC 805 ms
4,900 KB
testcase_09 AC 805 ms
5,160 KB
testcase_10 AC 805 ms
4,904 KB
testcase_11 AC 805 ms
4,904 KB
testcase_12 AC 805 ms
4,900 KB
testcase_13 AC 806 ms
4,900 KB
testcase_14 AC 805 ms
4,904 KB
testcase_15 AC 805 ms
4,904 KB
testcase_16 AC 805 ms
4,900 KB
testcase_17 AC 807 ms
4,900 KB
testcase_18 AC 810 ms
4,904 KB
testcase_19 AC 812 ms
5,160 KB
testcase_20 AC 812 ms
4,904 KB
testcase_21 AC 817 ms
5,156 KB
testcase_22 AC 812 ms
4,900 KB
testcase_23 AC 804 ms
5,156 KB
testcase_24 AC 823 ms
4,904 KB
testcase_25 AC 805 ms
4,904 KB
testcase_26 AC 828 ms
4,900 KB
testcase_27 AC 806 ms
5,160 KB
testcase_28 AC 827 ms
4,904 KB
testcase_29 AC 805 ms
4,900 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll=long long;
using Graph=vector<vector<int>>;
#define INF 1000000000
#define MOD 998244353
#define MAX 500

random_device seed;
mt19937 engine(seed());
uniform_real_distribution<> uniform_real_dist(0.0,1.0);
clock_t start_t,end_t;
double elapsed_time;
//実行制限時間-ε
double time_limit=0.8;
//初期温度
double T0=1e8;
//最終温度
double T1=1e2;

void two_opt(vector<int> &path, vector<vector<int>> &dist, int &S)
{
  int n=path.size();
  end_t=clock();
  elapsed_time=(double)(end_t-start_t)/CLOCKS_PER_SEC;
  // path[1, n-2]の順番を変更
  while (elapsed_time <= time_limit) {
    double T=pow(T0,1.0-elapsed_time/time_limit)*pow(T1,elapsed_time/time_limit);
    int left  = rand()%(n-2) + 1;
    int right = rand()%(n-2) + 1;
    if (left == right) {
      continue;
    }
    if (right < left) {
      swap(left, right);
    }
    int deltaS = 0.0;
    deltaS -= dist[path[left-1]][path[left]] + dist[path[right]][path[right+1]];
    deltaS += dist[path[left-1]][path[right]] + dist[path[left]][path[right+1]];
    int diff = round(1.0e9/(1.0e3 + sqrt(S+deltaS))) - round(1.0e9/(1.0e3 + sqrt(S)));
    //遷移確率
    double p=min<double>(1.0,exp(diff/T));
    if(uniform_real_dist(engine)<=p){
      S += deltaS;
      reverse(path.begin() + left, path.begin() + (right+1));
    }
    end_t=clock();
    elapsed_time=(double)(end_t-start_t)/CLOCKS_PER_SEC;
  }
}

int main(){
  int N,M;
  cin>>N>>M;
  vector<int> a(N), b(N);
  for(int i=0;i<N;i++){
    cin>>a[i]>>b[i];
  }

  start_t=clock();
  int alpha = 5;
  vector<int> x={800, 800, 500, 200, 200, 200, 500, 800};
  vector<int> y={500, 800, 800, 800, 500, 200, 200, 200};
  vector<vector<int>> dist(N+M,vector<int>(N+M,INF));
  vector<vector<int>> nextNode(N+M,vector<int>(N+M));
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      dist[i][j] = alpha*alpha * ((a[i]-a[j])*(a[i]-a[j]) + (b[i]-b[j])*(b[i]-b[j]));
    }
  }
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      dist[i][N+j] = alpha * ((a[i]-x[j])*(a[i]-x[j]) + (b[i]-y[j])*(b[i]-y[j]));
      dist[N+j][i] = alpha * ((a[i]-x[j])*(a[i]-x[j]) + (b[i]-y[j])*(b[i]-y[j]));
    }
  }
  for(int i=0;i<M;i++){
    for(int j=0;j<M;j++){
      dist[N+i][N+j] = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
    }
  }
  for(int i=0;i<N+M;i++){
    for(int j=0;j<N+M;j++){
      nextNode[i][j]=j;
    }
  }

  for(int k=0;k<N+M;k++){
    for(int i=0;i<N+M;i++){
      for(int j=0;j<N+M;j++){
        if(dist[i][k]+dist[k][j]<dist[i][j]){
          dist[i][j]=dist[i][k]+dist[k][j];
          nextNode[i][j]=nextNode[i][k];
        }
      }
    }
  }
  vector<int> path;
  for(int i=0;i<=N;i++){
    path.push_back(i%N);
  }
  int S=0;
  for(int i=0;i<N;i++){
    S+=dist[path[i]][path[i+1]];
  }

  two_opt(path, dist, S);

  // ans
  for(int i=0;i<M;i++){
    cout<<x[i]<<" "<<y[i]<<'\n';
  }
  vector<int> ans;
  ans.push_back(path[0]);
  for(int i=0;i<N;i++){
    int v=path[i];
    while(v!=path[i+1]){
      v=nextNode[v][path[i+1]];
      ans.push_back(v);
    }
  }
  cout<<ans.size()<<'\n';
  for(int i=0;i<ans.size();i++){
    if(ans[i]<N){
      cout<<"1 "<<ans[i]+1<<'\n';
    }else{
      cout<<"2 "<<(ans[i]-N)+1<<'\n';
    }
  }

  //int score = round(1.0e9/(1.0e3 + sqrt(S)));
  //cout<<score<<'\n';
}
0