結果

問題 No.5007 Steiner Space Travel
ユーザー butsurizukibutsurizuki
提出日時 2022-07-03 04:57:12
言語 C++23
(gcc 12.3.0 + boost 1.83.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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 62 ms
3,764 KB
testcase_01 AC 65 ms
3,840 KB
testcase_02 AC 65 ms
3,880 KB
testcase_03 AC 29 ms
3,852 KB
testcase_04 AC 61 ms
3,896 KB
testcase_05 AC 32 ms
3,808 KB
testcase_06 AC 64 ms
3,820 KB
testcase_07 AC 26 ms
3,800 KB
testcase_08 AC 67 ms
3,760 KB
testcase_09 AC 26 ms
3,828 KB
testcase_10 AC 39 ms
3,852 KB
testcase_11 AC 32 ms
4,008 KB
testcase_12 AC 22 ms
3,864 KB
testcase_13 AC 30 ms
3,896 KB
testcase_14 AC 65 ms
3,904 KB
testcase_15 AC 63 ms
3,848 KB
testcase_16 AC 66 ms
3,852 KB
testcase_17 AC 24 ms
3,828 KB
testcase_18 AC 24 ms
3,768 KB
testcase_19 AC 42 ms
3,760 KB
testcase_20 AC 61 ms
3,828 KB
testcase_21 AC 64 ms
3,796 KB
testcase_22 AC 25 ms
3,824 KB
testcase_23 AC 66 ms
3,764 KB
testcase_24 AC 63 ms
3,760 KB
testcase_25 AC 23 ms
3,760 KB
testcase_26 AC 62 ms
3,836 KB
testcase_27 AC 62 ms
3,876 KB
testcase_28 AC 65 ms
3,844 KB
testcase_29 AC 37 ms
3,836 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()+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;
}
0