結果

問題 No.5007 Steiner Space Travel
ユーザー fky_fky_
提出日時 2022-07-30 15:39:50
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 976 ms / 1,000 ms
コード長 7,506 bytes
コンパイル時間 2,367 ms
実行使用メモリ 6,952 KB
スコア 7,973,974
最終ジャッジ日時 2022-07-30 15:40:27
合計ジャッジ時間 34,373 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge10
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 976 ms
4,900 KB
testcase_01 AC 976 ms
4,908 KB
testcase_02 AC 976 ms
4,900 KB
testcase_03 AC 975 ms
5,156 KB
testcase_04 AC 976 ms
4,900 KB
testcase_05 AC 976 ms
5,160 KB
testcase_06 AC 976 ms
5,160 KB
testcase_07 AC 976 ms
4,904 KB
testcase_08 AC 976 ms
4,900 KB
testcase_09 AC 976 ms
4,900 KB
testcase_10 AC 976 ms
4,900 KB
testcase_11 AC 976 ms
5,160 KB
testcase_12 AC 976 ms
4,900 KB
testcase_13 AC 976 ms
4,904 KB
testcase_14 AC 975 ms
4,904 KB
testcase_15 AC 976 ms
4,904 KB
testcase_16 AC 976 ms
4,908 KB
testcase_17 AC 976 ms
4,904 KB
testcase_18 AC 976 ms
4,904 KB
testcase_19 AC 976 ms
4,900 KB
testcase_20 AC 976 ms
6,952 KB
testcase_21 AC 975 ms
4,904 KB
testcase_22 AC 975 ms
4,900 KB
testcase_23 AC 976 ms
4,904 KB
testcase_24 AC 976 ms
4,900 KB
testcase_25 AC 975 ms
4,904 KB
testcase_26 AC 976 ms
4,900 KB
testcase_27 AC 976 ms
6,952 KB
testcase_28 AC 976 ms
4,900 KB
testcase_29 AC 976 ms
4,900 KB
権限があれば一括ダウンロードができます

ソースコード

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);
    }

    // 長さ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 = 0.8;
	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(150, 850), Random.randint(150, 850)};
        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;
}
0