結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0