結果

問題 No.5007 Steiner Space Travel
ユーザー fky_fky_
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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_pair
int 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 seed
void 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);
}
// nk ... generate a random permutation of size n, and return the first k
vector<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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0