結果

問題 No.5007 Steiner Space Travel
ユーザー butsurizuki
提出日時 2022-07-03 04:57:12
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 67 ms / 1,000 ms
コード長 3,045 bytes
コンパイル時間 4,599 ms
実行使用メモリ 4,008 KB
スコア 4,879,783
最終ジャッジ日時 2022-07-30 13:32:22
合計ジャッジ時間 6,285 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
#define alpha 5
using namespace std;
using pi=pair<int,int>;
int n,m;
int tt;
int dist(pi a,pi b){
  int res=(a.first-b.first)*(a.first-b.first);
  res+=(a.second-b.second)*(a.second-b.second);
  return res;
}
vector<pi> x;
pi g[111][111];
void init_g(){
  for(int i=0;i<tt;i++){
    for(int j=0;j<tt;j++){
      if(i==j){g[i][j]={0,i};}
      else{g[i][j]={1e9,-1};}
    }
  }
}
void gen_g(){
  for(int k=0;k<tt;k++){
    for(int i=0;i<tt;i++){
      for(int j=0;j<tt;j++){
        if(g[i][j].first>g[i][k].first+g[k][j].first){
          g[i][j].first=g[i][k].first+g[k][j].first;
          g[i][j].second=g[i][k].second;
        }
      }
    }
  }
}
bool distinct(int a,int b,int c,int d){
  if(a==b){return false;}
  if(a==c){return false;}
  if(a==d){return false;}
  if(b==c){return false;}
  if(b==d){return false;}
  if(c==d){return false;}
  return true;
}
int output_dis;
vector<pi> output_coord;
vector<int> output_route;
int solve(mt19937_64 &eg){
  vector<int> p(n);
  for(int i=0;i<n;i++){p[i]=i;}
  shuffle(p.begin()+1,p.end(),eg);
  p.push_back(0);
  for(int tr=0;tr<1000;tr++){
    for(int i=0;i<n;i++){
      for(int j=i+2;j<n;j++){
        int ni=p[i+1];
        int nj=p[j+1];
        if(!distinct(i,j,ni,nj)){continue;}
        int bef=g[i][ni].first+g[j][nj].first;
        int aft=g[i][j].first+g[ni][nj].first;
        if(bef>aft){
          int l=(i+1)%n;
          int r=j;
          while(l<r){
            swap(p[l],p[r]);
            l++;r--;
          }
        }
      }
    }
  }
  int res=0;
  for(int i=0;i<n;i++){
    res+=g[p[i]][p[i+1]].first;
  }
  if(output_dis>res){
    output_dis=res;
    for(int i=n;i<n+m;i++){output_coord[i-n]=x[i];}
    output_route.clear();
    int cp=p[0];
    for(int i=0;i<n;i++){
      while(cp!=p[i+1]){
        output_route.push_back(cp);
        cp=g[cp][p[i+1]].second;
      }
    }
    output_route.push_back(p[n]);
  }
  return res;
}
int main(){
  random_device seed_gen;
  mt19937_64 engine(seed_gen());
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  output_dis=2e9;
  output_coord.resize(m);
  tt=n+m;
  x.resize(n+m);
  for(int i=0;i<n;i++){
    cin >> x[i].first >> x[i].second;
  }
  double deg=(2.0*3.1415926535897932384)/((double)m);
  for(int i=n;i<n+m;i++){
    x[i].first=(int)(500.5+300.0*cos(deg*((double)i-n)));
    x[i].second=(int)(500.5+300.0*sin(deg*((double)i-n)));
    cerr << x[i].first << ' ' << x[i].second << '\n';
  }
  for(int tr=0;tr<1;tr++){
    for(int i=0;i<tt;i++){
      for(int j=0;j<tt;j++){
        int ce=1;
        if(i<n){ce*=alpha;}
        if(j<n){ce*=alpha;}
        g[i][j]={ce*dist(x[i],x[j]),j};
      }
    }
    gen_g();
    solve(engine);
  }
  cerr << output_dis << "\n";
  for(auto &nx : output_coord){
    cout << nx.first << ' ' << nx.second << '\n';
  }
  cout << output_route.size() << '\n';
  for(auto &nx : output_route){
    if(nx<n){
      cout << "1 " << nx+1 << "\n";
    }
    else{
      cout << "2 " << nx-n+1 << "\n";
    }
  }
  return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0