結果

問題 No.5007 Steiner Space Travel
ユーザー butsurizukibutsurizuki
提出日時 2022-07-03 05:28:11
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 917 ms / 1,000 ms
コード長 3,404 bytes
コンパイル時間 3,898 ms
実行使用メモリ 4,132 KB
スコア 7,441,859
最終ジャッジ日時 2022-07-30 13:33:01
合計ジャッジ時間 33,344 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge10
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 909 ms
4,016 KB
testcase_01 AC 912 ms
3,864 KB
testcase_02 AC 902 ms
3,880 KB
testcase_03 AC 902 ms
3,976 KB
testcase_04 AC 895 ms
4,024 KB
testcase_05 AC 903 ms
3,972 KB
testcase_06 AC 896 ms
3,868 KB
testcase_07 AC 899 ms
3,976 KB
testcase_08 AC 897 ms
4,024 KB
testcase_09 AC 903 ms
4,024 KB
testcase_10 AC 915 ms
3,980 KB
testcase_11 AC 896 ms
3,932 KB
testcase_12 AC 909 ms
3,944 KB
testcase_13 AC 906 ms
3,968 KB
testcase_14 AC 897 ms
3,928 KB
testcase_15 AC 901 ms
4,024 KB
testcase_16 AC 896 ms
3,948 KB
testcase_17 AC 899 ms
3,948 KB
testcase_18 AC 900 ms
3,944 KB
testcase_19 AC 901 ms
3,968 KB
testcase_20 AC 902 ms
3,940 KB
testcase_21 AC 915 ms
4,024 KB
testcase_22 AC 910 ms
3,880 KB
testcase_23 AC 917 ms
3,944 KB
testcase_24 AC 906 ms
4,024 KB
testcase_25 AC 900 ms
4,132 KB
testcase_26 AC 905 ms
3,944 KB
testcase_27 AC 898 ms
4,132 KB
testcase_28 AC 909 ms
3,884 KB
testcase_29 AC 903 ms
3,928 KB
権限があれば一括ダウンロードができます

ソースコード

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

  for(int tr=0;tr<25;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 rad=0;rad<500;rad+=15){
    for(int i=n;i<n+m;i++){
      x[i].first=(int)(500.5+((double)rad)*cos(deg*((double)i-n)));
      x[i].second=(int)(500.5+((double)rad)*sin(deg*((double)i-n)));
      cerr << x[i].first << ' ' << x[i].second << '\n';
    }

    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