結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー kens
提出日時 2022-07-30 15:34:11
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 108 ms / 1,000 ms
コード長 2,275 bytes
コンパイル時間 3,963 ms
実行使用メモリ 4,104 KB
スコア 6,098,586
最終ジャッジ日時 2022-07-30 15:34:20
合計ジャッジ時間 8,069 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)n; i++)
using ll = long long;
using P = pair<ll,ll>;
constexpr int N = 100;
constexpr int M = 8;
constexpr ll A = 5;
constexpr int time_limit = 900;

// simulated annealing
constexpr double temp_start = 1.0;
constexpr double temp_end = 0.00001; 
constexpr int climb_loop = 1000000;

ll a[N], b[N];

// random
int seed = 12345;
mt19937 eng(seed);
uniform_real_distribution<> uniform_01;

// timer
class Timer {
private:
  chrono::system_clock::time_point start;
public:
  Timer() {
    start = chrono::system_clock::now();
  }

  int get_ms() {
    auto end = chrono::system_clock::now();
    auto t = chrono::duration_cast<chrono::milliseconds>(end-start).count();
    return t;
  }
};

inline ll dist2(int u, int v, ll alpha) {
  ll dx = a[u]-a[v], dy = b[u]-b[v];
  return alpha*(dx*dx + dy*dy);
}

void solve() {
  Timer timer;

  // input
  int hello;
  cin >> hello >> hello;
  rep(i,N) cin >> a[i] >> b[i];

  vector<int> seq(N+1);
  rep(i,N) seq[i] = i;
  seq[N] = 0;

  ll score = 0;
  for(int u = 1; u <= N; u++) score += dist2(seq[u],seq[u-1],A*A);

  // best sequence
  ll best_score = score;
  vector<int> best_seq = seq;

  // two opt
  rep(cn,climb_loop) {
    if(timer.get_ms() > time_limit) break;
    double temp = temp_start + (temp_end - temp_start)*cn/climb_loop;
    int s = eng() % (N-1) + 1;
    int t = eng() % (N-1) + 1;

    if(s == t) continue;
    if(s > t) swap(s,t);

    ll score_diff = dist2(seq[t],seq[s-1],A*A) + dist2(seq[s],seq[t+1],A*A) - dist2(seq[s],seq[s-1],A*A) - dist2(seq[t],seq[t+1],A*A);
    if(score_diff < 0 || uniform_01(eng) < exp((double)-score_diff/temp)) {
      score += score_diff;
      reverse(seq.begin()+s,seq.begin()+t+1);

      if(score < best_score) {
        best_score = score;
        best_seq = seq;
      }
    }
  }

  int final_score = round(1e9/(1000.0+sqrt((double)best_score)));  

  // cerr << best_score << endl;
  
  cerr << "Time " << timer.get_ms() << endl;
  cerr << "Score " << final_score << endl;

  rep(i,M) cout << 0 << " " << 0 << endl;
  cout << N+1 << endl;
  rep(i,N+1) cout << 1 << " " << best_seq[i]+1 << endl;
}

int main() {
  solve();
  return 0;
}
0