結果
| 問題 | No.5007 Steiner Space Travel |
| ユーザー |
 fky_
|
| 提出日時 | 2022-07-30 15:23:09 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,506 bytes |
| コンパイル時間 | 2,419 ms |
| スコア | 0 |
| 最終ジャッジ日時 | 2022-07-30 15:23:52 |
| 合計ジャッジ時間 | 42,039 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge10 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | TLE | - |
| testcase_02 | TLE | - |
| testcase_03 | TLE | - |
| testcase_04 | TLE | - |
| testcase_05 | TLE | - |
| testcase_06 | TLE | - |
| testcase_07 | TLE | - |
| testcase_08 | TLE | - |
| testcase_09 | TLE | - |
| testcase_10 | TLE | - |
| testcase_11 | TLE | - |
| testcase_12 | TLE | - |
| testcase_13 | TLE | - |
| testcase_14 | TLE | - |
| testcase_15 | TLE | - |
| testcase_16 | TLE | - |
| testcase_17 | TLE | - |
| testcase_18 | TLE | - |
| testcase_19 | TLE | - |
| testcase_20 | TLE | - |
| testcase_21 | TLE | - |
| testcase_22 | TLE | - |
| testcase_23 | TLE | - |
| testcase_24 | TLE | - |
| testcase_25 | TLE | - |
| testcase_26 | TLE | - |
| testcase_27 | TLE | - |
| testcase_28 | TLE | - |
| testcase_29 | TLE | - |
ソースコード
#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);
}
// 長さnの順列をランダムに生成し、その前k個分を出力する ... 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;
vector<pair<int, int>> via;
ll score;
Game() { init(); }
void init(){
cin >> N >> M;
FOR(i,0,N){
cin >> planet[i].first >> planet[i].second;
}
station.resize(M);
FOR(i,0,M) station[i] = {Random.randint(250, 750), Random.randint(250, 750)};
via.resize(N, {-1, -1});
next.resize(N, -1);
score = 0LL;
}
void first_route(){
// 初期化
next[0] = 1, next[1] = 0;
// 挿入
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;
}
bdx = next[bdx];
}
next[s] = next[min_bdx], next[min_bdx] = s;
}
calc_score();
return;
}
void via_dicision(){
int now = 0;
do{
int nx = next[now];
ll dlt_dis = pow(alpha, 2) * get_dist(planet[now], planet[nx]);
P adopt = {-1, -1};
FOR(i,0,M){
ll n_dist = alpha * (get_dist(planet[now], station[i]) + get_dist(station[i], planet[nx]));
if(n_dist < dlt_dis){
dlt_dis = n_dist;
adopt = {i, -1};
}
}
FOR(i,0,M){
FOR(j,0,M){
if(i == j) continue;
ll n_dist = alpha * get_dist(planet[now], station[i]) + get_dist(station[i], station[j]) + alpha * get_dist(station[j], planet[nx]);
if(n_dist < dlt_dis){
dlt_dis = n_dist;
adopt = {i, j};
}
}
}
via[now] = adopt;
now = nx;
} while (now > 0);
return;
}
vector<pair<int, int>> get_route(){
int now = 0;
vector<P> res;
do{
res.push_back({1, now});
if(via[now].first != -1) res.push_back({2, via[now].first});
if(via[now].second != -1) res.push_back({2, via[now].second});
now = next[now];
} while (now > 0);
res.push_back({1, 0});
return res;
}
void calc_score(){
auto route = get_route();
score = 0;
FOR(i,0,(int)route.size()-1){
if(route[i].first == 1 && route[i + 1].first == 1){
score += alpha * alpha * get_dist(planet[route[i].second], planet[route[i + 1].second]);
}else if(route[i].first == 1 && route[i + 1].first == 2){
score += alpha * get_dist(planet[route[i].second], station[route[i + 1].second]);
}else if(route[i].first == 2 && route[i + 1].first == 1){
score += alpha * get_dist(station[route[i].second], planet[route[i + 1].second]);
}else{
score += get_dist(station[route[i].second], station[route[i + 1].second]);
}
}
return;
}
void output(){
FOR(i,0,M){
cout << station[i].first << " " << station[i].second << endl;
}
auto ans = get_route();
cout << (int)ans.size() << endl;
for(auto [a, b]: ans) cout << a << " " << b + 1 << endl;
return;
}
};
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();
while(timer.get() < TIMELIMIT){
Game new_game = game;
new_game.station[Random.randint(M)] = {Random.randint(250, 750), Random.randint(250, 750)};
new_game.via_dicision();
new_game.calc_score();
// cerr << game.score << " " << new_game.score << endl;
if(new_game.score < game.score) game = new_game;
}
game.output();
return 0;
}