結果

問題 No.5007 Steiner Space Travel
ユーザー iehniehn
提出日時 2022-07-30 15:01:47
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 981 ms / 1,000 ms
コード長 5,615 bytes
コンパイル時間 3,233 ms
実行使用メモリ 4,816 KB
スコア 5,158,352
最終ジャッジ日時 2022-07-30 15:02:22
合計ジャッジ時間 35,559 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize "O3,omit-frame-pointer,inline,unroll-loops"
#pragma GCC target "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2"
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include "bits/stdc++.h"
#include <sys/time.h>
#include <emmintrin.h>
#include <string>
#include <bitset>
#include <unistd.h>

using namespace std;

#ifdef LOCAL
inline double GetSeconds() {
  return static_cast<double>(chrono::duration_cast<chrono::nanoseconds>(
        chrono::steady_clock::now().time_since_epoch()).count())/1000000000;
}
#else
inline long long GetTSC() {
  long long lo, hi;
  asm volatile ("rdtsc": "=a"(lo), "=d"(hi));
  return lo + (hi << 32);
}
inline double GetSeconds() {
  return GetTSC() / 3.0e9;
}
#endif

struct XorShift {
  uint64_t x = 88172645463325252ULL;
  double nl[65536];
  XorShift() {}

  void init(){
    double n2 = 1.0 / 65536*2;
    for(int i=0; i<65536; i++) nl[i] = log(i / 65536.0 + n2);
  }

  void setSeed(uint64_t seed) { x = seed; init(); }

  uint64_t next() {
    x ^= x << 13; x ^= x >> 7; x ^= x << 17;
    return x;
  }

  int nextInt(int n) {
    uint64_t upper = 0xFFFFFFFFFFFFFFFFULL / n * n;
    uint64_t v = next();
    while (v >= upper) v = next();
    return v % n;
  }

  double nextDouble() {
    uint64_t v = next() >> 11; // 53bit
    return (double)v / (1ULL << 53);
  }

  double nextLog() {
    return nl[nextInt(65536)];
  }
};


XorShift xs;
#ifdef LOCAL
const double TO = 0.9 * 1.2e-0;
#else
const double TO = 0.9 / 1.2;
#endif

double starttime, gt;
int att,btt,ctt,dtt,ett,ftt,gtt,htt;

const int N = 100;
const int M = 8;
const int NM = 108;
const int AL = 5;
const int AL2 = 25;

int A[NM];
int B[NM];
int D[NM][NM];
int E[NM][NM];
int R[N + 1];

void init(){
  int n,m;
  cin >> n >> m;

  for(int i=0; i<N; i++) cin >> A[i] >> B[i];

  for(int i=0; i<N; i++){
    E[i][i] = D[i][i] = 0;
    for(int j=i+1; j<N; j++){
      E[i][j] = E[j][i] = D[i][j] = D[j][i] = AL2 * (pow(A[i] - A[j], 2) + pow(B[i] - B[j], 2));
    }
  }
  for(int k=0; k<N; k++){
    for(int i=0; i<N; i++){
      for(int j=0; j<N; j++){
        if(D[i][j] > D[i][k] + D[k][j]){
          D[i][j] = D[i][k] + D[k][j];
        }
      }
    }
  }
}

void newD(int m){
  E[m][m] = D[m][m] = 0;
  int mm = 0, mc = 0, ma = 0, mb = 0;
  for(int t=0; t<1000; t++){
    A[m] = xs.nextInt(1001);
    B[m] = xs.nextInt(1001);

    for(int i=0; i<N; i++){
      D[i][m] = D[m][i] = AL * (pow(A[i] - A[m], 2) + pow(B[i] - B[m], 2));
    }
    for(int i=N; i<m; i++){
      D[i][m] = D[m][i] = pow(A[i] - A[m], 2) + pow(B[i] - B[m], 2);
    }
    int tc = 0, tm = 0;
    for(int i=0; i<N; i++){
      for(int j=i+1; j<N; j++){
        if(D[i][j] > D[i][m] + D[m][j]){
          tc++;
          tm += D[i][j] - (D[i][m] + D[m][j]);
        }
      }
    }
    if(tm > mm || (tm == mm && tc < mc)){
      mm = tm;
      mc = tc;
      ma = A[m];
      mb = B[m];
    }
  }

  cerr << "mab: " << ma << " " << mb << " mmc: " << mm << " " << mc << endl;
  A[m] = ma;
  B[m] = mb;
  for(int i=0; i<N; i++){
    E[i][m] = E[m][i] = D[i][m] = D[m][i] = AL * (pow(A[i] - A[m], 2) + pow(B[i] - B[m], 2));
  }
  for(int i=N; i<m; i++){
    E[i][m] = E[m][i] = D[i][m] = D[m][i] = pow(A[i] - A[m], 2) + pow(B[i] - B[m], 2);
  }

  for(int k=0; k<=m; k++){
    for(int i=0; i<=m; i++){
      for(int j=0; j<=m; j++){
        if(D[i][j] > D[i][k] + D[k][j]){
          D[i][j] = D[i][k] + D[k][j];
        }
      }
    }
  }
}

void solve(){
  for(int m=0; m<M; m++) newD(N+m);

  R[0] = R[N] = 0;
  bitset<N> u;
  for(int i=1; i<N; i++){
    int b = R[i - 1];
    int m = 1e9, mj = 0;
    for(int j=1; j<N; j++) if(!u[j]){
      if(m > D[b][j]){
        m = D[b][j];
        mj = j;
      }
    }
    R[i] = mj;
    u[mj] = 1;
  }

  while(1){
    gt = (TO - (GetSeconds() - starttime)) / TO;
    if(gt <= 0) break;

    int a = xs.nextInt(N - 1) + 1;
    int b = xs.nextInt(N - 2) + 1;
    if(b >= a) b++;
    else swap(a, b);

    int cc = D[R[a-1]][R[a]] + D[R[b]][R[b+1]];
    int nc = D[R[a-1]][R[b]] + D[R[a]][R[b+1]];
    int s = nc - cc;
    if(s <= 0 || s > xs.nextLog() * gt){
      btt++;
      while(a < b){
        swap(R[a++], R[b--]);
      }
    }
  }

  int ms = 0;
  for(int i=0; i<N; i++) ms += D[R[i]][R[i+1]];
  cerr << "ms: " << ms << " sc: " << round(1e9 / (1000 + pow(ms, 0.5))) << endl;

#ifdef DEBUG
  cerr << " time: " << (GetSeconds() - starttime);
  cerr << " att: " << att << " btt: " << btt;
  cerr << " ctt: " << ctt << " dtt: " << dtt << " ett: " << ett;
  cerr << " ftt: " << ftt << " gtt: " << gtt << " htt: " << htt << endl;
#endif
}

void output(){
  for(int i=0; i<M; i++){
    cout << A[N+i] << ' ' << B[N+i] << '\n';
  }

  vector<int> r;
  r.emplace_back(0);
  for(int i=0; i<N; i++){
    int c = R[i];
    int t = R[i + 1];
    int d = D[c][t];
    while(c != t){
      bool ok = 0;
      for(int i=0; i<N+M; i++){
        if(i != c && E[c][i] + D[i][t] == d){
          ok = 1;
          r.emplace_back(i);
          c = i;
          d = D[c][t];
          break;
        }
      }

      if(!ok){
        cerr << "err" << endl;
        return;
      }
    }
  }

  cout << r.size() << '\n';
  for(auto t : r){
    if(t < N){
      cout << "1 " << (t + 1) << '\n';
    }else{
      cout << "2 " << (t - N + 1) << '\n';
    }
  }

  cout << flush;
}

int main() {
  starttime = GetSeconds();
  srand((unsigned) time(NULL));
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  xs.setSeed(rand() % 65536 + 65537);
  cerr << "x: " << xs.x << endl;

  init();
  solve();
  output();

  return 0;
}
0