結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
![]() |
提出日時 | 2022-07-30 14:38:38 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 5,123 bytes |
コンパイル時間 | 2,142 ms |
実行使用メモリ | 3,560 KB |
スコア | 6,057,324 |
最終ジャッジ日時 | 2022-07-30 14:38:42 |
合計ジャッジ時間 | 3,972 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge10 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef long double ld;#define FOR(i, a, b) for (int i = a; i < (b); i++)#define RFOR(i, a, b) for (int i = a; i >= (b); i--)#define range(a) a.begin(), a.end()#define endl "\n"#define Yes() cout << "Yes" << endl#define No() cout << "No" << endl#define MP make_pairint dx[4] = {-1, 0, 1, 0};int dy[4] = {0, -1, 0, 1};using P = pair<int, int>;const long long INF = 1LL<<60;void chmin(long long &a, long long b) { if (a > b) a = b; }void chmax(long long &a, long long b) { if (a < b) a = b; }struct xorshift128{const unsigned int ini_x = 123456789, ini_y = 362436069, ini_z = 521288629, ini_w = 88675123;unsigned int x, y, z, w;xorshift128() {}// シードによってx,y,z,wを初期化 ... initialize x,y,z,w by seedvoid set_seed(unsigned int seed){x = ini_x, y = ini_y, z = ini_z, w = ini_w ^ seed;}unsigned int randint(){unsigned int t = x ^ (x << 11);x = y;y = z;z = w;return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));}// [0,r)の範囲の整数で乱数発生 ... generate random integer in [0,r)unsigned int randint(unsigned int r){assert(r != 0);return randint() % r;}// [l,r)の範囲の整数で乱数発生 ... generate random integer in [l,r)unsigned int randint(unsigned int l, unsigned int r){assert(r > l);return l + randint(r-l);}// 長さnの順列をランダムに生成し、その前k個分を出力する ... generate a random permutation of size n, and return the first kvector<int> randperm(int n, int k){assert(k >= 0 && k <= n);vector<int> ret(n);for(int i = 0; i < n; i++){ret[i] = i;}for(int i = 0; i < k; i++){swap(ret[i], ret[randint(i, n)]);}return vector<int>(ret.begin(), ret.begin() + k);}// [0,1]の範囲の実数で乱数発生 ... generate random real number in [0,1]double uniform(){return double(randint()) * 2.3283064370807974e-10;}// [0,r]の範囲の実数で乱数発生 ... generate random real number in [0,r]double uniform(double r){assert(r >= 0.0);return uniform() * r;}// [l,r]の範囲の実数で乱数発生 ... generate random real number in [l,r]double uniform(double l, double r){assert(r >= l);return l + uniform(r - l);}};xorshift128 Random;const int64_t CYCLES_PER_SEC = 2800000000;struct Timer {int64_t start;Timer() { reset(); }void reset() { start = getCycle(); }void plus(double a) { start -= (a * CYCLES_PER_SEC); }inline double get() { return (double)(getCycle() - start) / CYCLES_PER_SEC; }inline int64_t getCycle() {uint32_t low, high;__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));return ((int64_t)low) | ((int64_t)high << 32);}};Timer timer;ll get_dist(P a, P b){return round(hypot(abs(a.first - b.first), abs(a.second - b.second)));}int N = 100, M = 8, alpha = 5;vector<pair<int, int>> planet(100);struct Game{vector<pair<int, int>> station;vector<int> next;ll score;Game() { init(); }void init(){cin >> N >> M;FOR(i,0,N){cin >> planet[i].first >> planet[i].second;}station.resize(M, {-1, -1});next.resize(N, -1);score = 0LL;}void first_route(){// 初期化next[0] = 1, next[1] = 0;score = 2 * get_dist(planet[0], planet[1]);// 挿入FOR(s,2,N){ll dlt_dis = INF, min_bdx = -1;int bdx = 0;while(bdx > 0 || min_bdx == -1){// i, i + 1の間に挿入int adx = next[bdx];ll n_dis = get_dist(planet[bdx], planet[s]) + get_dist(planet[s], planet[adx]) - get_dist(planet[bdx], planet[adx]);if(n_dis < dlt_dis){dlt_dis = n_dis;min_bdx = bdx;}// cerr << bdx << " " << n_dis << endl;bdx = next[bdx];}// cerr << endl;next[s] = next[min_bdx], next[min_bdx] = s;}int now = 0;do{score = pow(alpha, 2) * get_dist(planet[now], planet[next[now]]);now = next[now];} while (now > 0);return;}void output(){FOR(i,0,M){cout << "0 0" << endl;}cout << N + 1 << endl;int now = 0;do{cout << 1 << " " << now + 1 << endl;now = next[now];} while (now > 0);cout << "1 1" << endl;}};int main(void){ios::sync_with_stdio(0);cin.tie(0);timer.reset();double TIMELIMIT = 1.0;random_device rnd; // 非決定的な乱数生成器unsigned long long sd = (unsigned long long)rnd();Random.set_seed(sd);Game game;game.init();game.first_route();game.output();return 0;}