結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 a9ua1i0n
|
| 提出日時 | 2022-07-30 17:24:35 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 982 ms / 1,000 ms |
| コード長 | 6,021 bytes |
| コンパイル時間 | 1,473 ms |
| 実行使用メモリ | 6,952 KB |
| スコア | 6,972,174 |
| 最終ジャッジ日時 | 2022-07-30 17:25:15 |
| 合計ジャッジ時間 | 33,537 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge11 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
#if !__INCLUDE_LEVEL__
#include __FILE__
constexpr clock_t TL = 0.95*CLOCKS_PER_SEC;
constexpr int alpha = 5;
constexpr int N = 100;
constexpr int M = 8;
using output_t = vector<pair<int,int>>;
using stations_t = array<pair<int,int>,M>;
using pos_t = array<pair<int, int>, N>;
void output(const output_t &ans, const stations_t &stations){
REP(i,M)cout << stations[i].first << " " << stations[i].second << "\n";
cout << ans.size() << "\n";
REP(i,ans.size())cout << ans[i].first << " " << ans[i].second+1 << "\n";
}
int calc_score(const output_t &ans, const stations_t &stations, const array<pair<int,int>, N> &pos){
int energy = 0;
int prev_x = pos[0].first;
int prev_y = pos[0].second;
bool prev_is_planet = true;
REP(i,ans.size()){
if(i==0)continue;
int cur_energy = 0;
int idx = ans[i].second;
if(ans[i].first==1){
cur_energy += (prev_x-pos[idx].first)*(prev_x-pos[idx].first)
+ (prev_y-pos[idx].second)*(prev_y-pos[idx].second);
if(prev_is_planet){
cur_energy *= 5*5;
}
else{
cur_energy *= 5;
}
prev_x = pos[idx].first;
prev_y = pos[idx].second;
prev_is_planet=true;
}
else{
cur_energy += (prev_x-stations[idx].first)*(prev_x-stations[idx].first)
+ (prev_y-stations[idx].second)*(prev_y-stations[idx].second);
if(prev_is_planet){
cur_energy *= 5;
}
else{
cur_energy *= 1;
}
prev_x = stations[idx].first;
prev_y = stations[idx].second;
prev_is_planet=false;
}
energy += cur_energy;
}
return round(1e9/(1000+sqrt(energy)));
}
void simple_solution(output_t &ans, const pos_t &pos){
vector<bool> seen(N);
seen[0]=true;
int upper = floor((N-1)/2.0);
REP(i,upper){
int least_len = 1e9;
int idx = ans[i].second;
int best_next_idx = 0;
REP(j,N){
if(seen[j])continue;
int dist = (pos[j].first-pos[idx].first)*(pos[j].first-pos[idx].first)
+ (pos[j].second-pos[idx].second)*(pos[j].second-pos[idx].second);
if( dist < least_len){
best_next_idx = j;
least_len = dist;
}
}
ans[1+i].second = best_next_idx;
seen[best_next_idx] = true;
}
int lower = ceil((N-1)/2.0);
REP(i,lower){
int least_len = 1e9;
int idx = ans[N-i].second;
int best_next_idx = 0;
REP(j,N){
if(seen[j])continue;
int dist = (pos[j].first-pos[idx].first)*(pos[j].first-pos[idx].first)
+ (pos[j].second-pos[idx].second)*(pos[j].second-pos[idx].second);
if( dist < least_len){
best_next_idx = j;
least_len = dist;
}
}
ans[N-i-1].second = best_next_idx;
seen[best_next_idx] = true;
}
}
void mauntain(output_t &ans, stations_t &stations, const pos_t &pos, const clock_t TL){
mt19937_64 rng(0);
int best_score = calc_score(ans, stations, pos);
int loop = 0;
while(true){
if(loop%100 && clock() > TL){
break;
}
{
int swap_a = rng()%(ans.size()-2) +1;
int swap_b = rng()%(ans.size()-2) +1;
swap(ans[swap_a], ans[swap_b]);
int score = calc_score(ans, stations, pos);
if(score > best_score){
best_score = score;
}
else{
swap(ans[swap_a], ans[swap_b]);
}
}
loop += 1;
}
}
void add_stations_to_midpoint(output_t &ans, stations_t &stations, const pos_t &pos){
vector<pair<int,pair<pair<int,int>,pair<int, int>>>> lens(ans.size()-1);
REP(i,ans.size()-1){
int prev_x = ans[i].first==1? pos[ans[i].second].first: stations[ans[i].second].first;
int prev_y = ans[i].first==1? pos[ans[i].second].second: stations[ans[i].second].second;
int next_x = ans[i+1].first==1? pos[ans[i+1].second].first: stations[ans[i+1].second].first;
int next_y = ans[i+1].first==1? pos[ans[i+1].second].second: stations[ans[i+1].second].second;
lens[i].first = (prev_x-next_x)*(prev_x-next_x) + (prev_y-next_y)*(prev_y-next_y);
lens[i].second.first = pair<int,int>((prev_x+next_x)/2, (prev_y+next_y)/2);
lens[i].second.second = ans[i];
}
sort(ALL(lens), greater<pair<int,pair<pair<int,int>,pair<int, int>>>>());
REP(i,M){
stations[i] = lens[i].second.first;
ans.insert(find(ALL(ans), lens[i].second.second)+1, pair<int,int>(2, i));
}
}
void solve(pos_t &pos){
output_t ans(N+1, pair<int,int>(1,0));
REP(i,N)ans[i].second = i;
array<pair<int, int>, M> stations;
simple_solution(ans, pos);
mauntain(ans, stations, pos, TL/2);
add_stations_to_midpoint(ans, stations, pos);
mauntain(ans, stations, pos, TL);
output(ans, stations);
cerr << calc_score(ans, stations, pos) << "\n";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll _N,_M;
cin >> _N >> _M;
array<pair<int,int>, N> pos;
REP(i,_N)cin >> pos[i].first >> pos[i].second;
solve(pos);
#if LOCAL
cerr << ((double)clock()/CLOCKS_PER_SEC) << "\n";
#endif
return 0;
}
//====================temp====================
#else
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define RREP(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define REPITR(itr, ARRAY) for (auto itr = (ARRAY).begin(); itr != (ARRAY).end(); ++itr)
#define RREPITR(itr, ARRAY) for (auto itr = (ARRAY).rbegin(); itr != (ARRAY).end(); ++itr)
#define ALL(n) (n).begin(),(n).end()
using ll = long long;
using ull = unsigned long long;
#endif