結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー butsurizuki
提出日時 2022-07-03 05:10:19
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 99 ms / 1,000 ms
コード長 3,371 bytes
コンパイル時間 3,500 ms
実行使用メモリ 4,012 KB
スコア 7,251,201
最終ジャッジ日時 2022-07-30 13:32:29
合計ジャッジ時間 8,239 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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(),p.end(),eg);

  for(int tr=0;tr<100;tr++){
    vector<pi> vp;
    for(int i=0;i<n;i++){
      for(int j=i+1;j<n;j++){vp.push_back({i,j});}
    }
    shuffle(vp.begin(),vp.end(),eg);
    for(auto &nx : vp){
      int i=nx.first;
      int j=nx.second;

      set<int> st;
      st.insert((i+n-1)%n);
      st.insert(i);
      st.insert((j+n-1)%n);
      st.insert(j);
      int del=0;
      for(auto &nx : st){
        del-=g[p[nx]][p[(nx+1)%n]].first;
      }
      swap(p[i],p[j]);
      for(auto &nx : st){
        del+=g[p[nx]][p[(nx+1)%n]].first;
      }

      if(del>0){swap(p[i],p[j]);}
    }
  }

  {
    vector<int> np;
    int tg=-1;
    for(int i=0;i<n;i++){
      if(p[i]==0){tg=i;break;}
    }
    for(int i=0;i<n;i++){
      np.push_back(p[(i+tg)%n]);
    }
    np.push_back(0);
    p=np;
  }
  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;
}
0