結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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 annealingconstexpr double temp_start = 1.0;constexpr double temp_end = 0.00001;constexpr int climb_loop = 1000000;ll a[N], b[N];// randomint seed = 12345;mt19937 eng(seed);uniform_real_distribution<> uniform_01;// timerclass 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;// inputint 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 sequencell best_score = score;vector<int> best_seq = seq;// two optrep(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;}