#783884 (C++14) No.5007 Steiner Space Travel

提出ソース
結果

問題	No.5007 Steiner Space Travel
ユーザー	yunix
提出日時	2022-08-02 23:24:11
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	985 ms / 1,000 ms
コード長	23,001 bytes
コンパイル時間	1,875 ms
実行使用メモリ	5,016 KB
スコア	8,898,975
最終ジャッジ日時	2022-08-02 23:24:45
合計ジャッジ時間	34,139 ms
ジャッジサーバーID （参考情報）	judge14 / judge12
	純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	985 ms 4,812 KB
testcase_01	AC	985 ms 4,784 KB
testcase_02	AC	984 ms 4,724 KB
testcase_03	AC	985 ms 4,744 KB
testcase_04	AC	984 ms 4,776 KB
testcase_05	AC	984 ms 4,860 KB
testcase_06	AC	984 ms 4,904 KB
testcase_07	AC	985 ms 4,784 KB
testcase_08	AC	984 ms 4,828 KB
testcase_09	AC	985 ms 4,812 KB
testcase_10	AC	985 ms 4,800 KB
testcase_11	AC	984 ms 4,828 KB
testcase_12	AC	985 ms 5,016 KB
testcase_13	AC	985 ms 4,712 KB
testcase_14	AC	985 ms 4,728 KB
testcase_15	AC	984 ms 4,856 KB
testcase_16	AC	985 ms 4,796 KB
testcase_17	AC	984 ms 4,752 KB
testcase_18	AC	984 ms 4,668 KB
testcase_19	AC	984 ms 4,904 KB
testcase_20	AC	985 ms 4,816 KB
testcase_21	AC	985 ms 4,756 KB
testcase_22	AC	985 ms 4,672 KB
testcase_23	AC	984 ms 4,832 KB
testcase_24	AC	984 ms 4,740 KB
testcase_25	AC	984 ms 4,864 KB
testcase_26	AC	985 ms 4,740 KB
testcase_27	AC	984 ms 4,752 KB
testcase_28	AC	984 ms 4,832 KB
testcase_29	AC	984 ms 4,748 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <iostream>
#include <string>
#include <vector>
#include <tuple>
#include <chrono>
#include <algorithm>
#include <random>
#include <map>
#include <set>
#include <queue>
#include <random>
#include <chrono>
#include <cmath>
#include <climits>
using namespace std;
using vec_int = vector<int>;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using ll = long long;
// using PQ = priority_queue<pair<float, int>, vector<pair<float,int>>, greater<pair<float, int>>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

float initial_T_STATION = 15000;
float final_T_STATION = 100;
float initial_T = 15000;
float final_T = 100;
float TIME_LIMIT = 1000;
float TIME_LIMIT_STATION = 1000;
float TIME_LIMIT_TSP = 30;
float TIME_LIMIT_TSP2 = 600;

int RAND_ARR_LEN = 100000;
int RAND_RANGE = 1000000000;

vector<P> DIRS = {make_pair(0, -1), make_pair(-1, 0), make_pair(0, 1), make_pair(1, 0)};

bool is_in(int x, int y, int N)
{
    if (x >= 0 && x < N && y >= 0 && y < N)
        return true;
    return false;
}

// std::mt19937 mt{ std::random_device{}() };
std::mt19937 mt{12345};
std::uniform_int_distribution<int> dist(1, RAND_RANGE);
float get_time(bool init)
{
    static std::chrono::system_clock::time_point start;
    if (init)
    {
        start = std::chrono::system_clock::now();
    }
    std::chrono::system_clock::time_point end = std::chrono::system_clock::now();
    return std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); //処理に要した時間をミリ秒に変換
}


class Rand
{
private:
    int count = 0;
    vec_int rand_arr;

public:
    Rand(){
        rep(i, RAND_ARR_LEN){
            rand_arr.push_back(dist(mt));
}
}
;
int get();
int get_rand(int from, int to);
float get_float();
}
;

int Rand::get()
{
    int num = rand_arr.at(count);
    count += 1;
    count %= RAND_ARR_LEN;
    return num;
}

int Rand::get_rand(int from, int to)
{
    int diff = to - from;
    int num = get() % diff;
    return num + from;
}

float Rand::get_float()
{
    // 0~1の間の一様乱数
    return (float)get() / (float)RAND_RANGE;
}

Rand ro;

float current_tmp_station(float current_time)
{
    return final_T_STATION + (initial_T_STATION - final_T_STATION) * (TIME_LIMIT_STATION - current_time) / TIME_LIMIT_STATION;
}

bool is_valid_transition_station(int diff, float current_time)
{
    float t = current_tmp_station(current_time);
    float rand = ro.get_float();
    // cerr<<"tmperature"<<t<<" "<<diff<<endl;
    return rand < exp(((float)diff) / t);
}

float current_tmp_tsp(float current_time)
{
    return final_T + (initial_T - final_T) * (TIME_LIMIT - current_time) / TIME_LIMIT;
}

bool is_valid_transition_tsp(int diff, float current_time)
{
    float t = current_tmp_tsp(current_time);
    float rand = ro.get_float();
    return rand < exp(((float)diff) / t);
}


float current_tmp_tsp2(float current_time)
{
    return final_T + (initial_T - final_T) * (TIME_LIMIT_TSP2 - current_time) / TIME_LIMIT_TSP2;
}

bool is_valid_transition_tsp2(int diff, float current_time)
{
    float t = current_tmp_tsp2(current_time);
    float rand = ro.get_float();
    return rand < exp(((float)diff) / t);
}



int N, M; 
vec_int a, b;
int alpha=5;
int sq_alpha=25;


class SpaceStation{
    public:
    int x;
    int y;
    SpaceStation(){
        x=0;
        y=0;
    };
    SpaceStation(int xpos, int ypos){
        x=xpos;
        y=ypos;
    };
    int square_distance(int x2, int y2){
        return (x2-x)*(x2-x) + (y2-y)*(y2-y);
    };
    void set_pos(int xpos, int ypos){
        x=xpos;
        y=ypos;
    };

    void random_move(){
        int dx = ro.get_rand(-20, 21);
        int dy = ro.get_rand(-20, 21);
        int x2 = x+dx;
        int y2 = y+dy;
        x2 = max(0, x2);
        y2 = max(0, y2);
        x2 = min(1000, x2);
        y2 = min(1000, y2);
        x=x2;
        y=y2;
    };

    int intermediate_distance(int city1, int city2){
        int result = 0;
        result += square_distance(a.at(city1), b.at(city1))*alpha;
        result += square_distance(a.at(city2), b.at(city2))*alpha;
        return result;

    }
};

int tot_distance(vector<SpaceStation> &stations, vec_int &excluded){
    int result = 0;
    rep(i, N){
        if(excluded.at(i)==1)continue;
        int tmp_dist = INT_MAX;
        rep(j, M){
            tmp_dist = min(tmp_dist, stations.at(j).square_distance(a.at(i), b.at(i)));
        }
        result += tmp_dist;
    }
    return result;
}

int sq_dist_between_cities(int i, int j){
    int result = 0;
    result += (a.at(i)-a.at(j))*(a.at(i)-a.at(j));
    result += (b.at(i)-b.at(j))*(b.at(i)-b.at(j));
    return result;

}

vector<vector<pair<int, vector<P>>>> make_dist_map(){
    vector<vector<pair<int, vector<P>>>> result(N, vector<pair<int, vector<P>>>(N));

    vector<vector<int>> visited(N, vec_int(N, 0));
    for(int i=0;i<N;i++){
        // 都市iをstartにする

        priority_queue<T, vector<T>, greater<T>> pq;
        pq.emplace(0, i, -1);

        while(!pq.empty()){
            int dist, pos, prev; tie(dist, pos, prev) = pq.top(); pq.pop();
            if(visited.at(i).at(pos)==1)continue;
            // 都市にたどり着いた時
            visited.at(i).at(pos) = 1;
            visited.at(pos).at(i) = 1;
            vector<P> route;
            if(prev!=-1){
                route = result.at(i).at(prev).second;
            }
            route.push_back(make_pair(1, pos));
            result.at(i).at(pos) = make_pair(dist, route);
            vector<P> route2 = route;
            reverse(route2.begin(), route2.end());
            result.at(pos).at(i) = make_pair(dist, route2);

            for(int j=0;j<N;j++){
                // 都市にいく時
                if(visited.at(i).at(j)==1)continue;
                int add_dist = sq_dist_between_cities(pos, j) * sq_alpha;
                pq.emplace(dist+add_dist, j, pos);
            }
        }
    }
    return result;
}

int calc_dist(vector<SpaceStation> &stations, vector<P> &tmp_ans){
    int result = 0;
    for(int i=1;i<tmp_ans.size();i++){
        int type, pos; tie(type, pos) = tmp_ans.at(i);
        int prev_type, prev_pos;  tie(prev_type, prev_pos) = tmp_ans.at(i-1);

        if(type==1&&prev_type==1){
            result += sq_dist_between_cities(pos, prev_pos)*sq_alpha;
        }else if(type==1&&prev_type==2){
            result += stations.at(prev_pos).square_distance(a.at(pos), b.at(pos))*alpha;
        }else if(type==2 && prev_type==1){
            result += stations.at(pos).square_distance(a.at(prev_pos), b.at(prev_pos))*alpha;
        }else{
            result += stations.at(pos).square_distance(stations.at(prev_pos).x, stations.at(prev_pos).y);
        }
    }
    return result;
}

int check_keiyu(vector<SpaceStation> &stations, vec_int &keiyu_flag, vec_int &routes, vector<vector<pair<int, vector<P>>>> &dist_map){
    int result = 0;

    rep(i, N){
        int prev = routes.at(i);
        int current = routes.at(i+1);
        int original_distance = dist_map.at(prev).at(current).first;

        int after_distance = INT_MAX;
        int keiyu = -1;
        rep(j, M){
            int dist = 0;
            dist += stations.at(j).square_distance(a.at(prev), b.at(prev))*5;
            dist += stations.at(j).square_distance(a.at(current), b.at(current))*5;
            if(after_distance>dist){
                after_distance = dist;
                keiyu = j;
            }
        }
        if(after_distance<original_distance){
            result += original_distance - after_distance;
            keiyu_flag.at(i) = keiyu;
        }
    }
    return result;

}


int greedy_strategy(vector<P> &ans, vector<SpaceStation> &stations, vector<vector<pair<int, vector<P>>>> &dist_mat){
    // 訪れていない場所の中で一番コストが小さくいけそうなところにいく
    int result = 0;

    int pos = 0;
    ans.push_back(make_pair(1, 0));

    vec_int visited(N, 0);
    while(true){
        visited.at(pos) = 1;
        
        int min_dist = INT_MAX;
        int next_pos = -1;
        for(int i=0;i<N;i++){
            if(visited.at(i)==1)continue;
            int tmp_dist = dist_mat.at(pos).at(i).first;
            if(min_dist>tmp_dist){
                min_dist = tmp_dist;
                next_pos = i;
            }
        }


        if(next_pos==-1)break;

        int tmp_dist2 = calc_dist(stations, ans);

        for(auto p_pos: dist_mat.at(pos).at(next_pos).second){
            // if(p_pos.second == pos&&p_pos.first==1)continue;
            if(ans.at(ans.size()-1)==p_pos)continue;
            ans.push_back(p_pos);
        }
        int tmp_dist3 = calc_dist(stations, ans);
        pos = next_pos;
        result += min_dist;
    }

    for(auto p_pos: dist_mat.at(pos).at(0).second){
        ans.push_back(p_pos);
    }
    result += dist_mat.at(pos).at(0).first;

    return result;
}

void adjust_station_pos(vector<SpaceStation> &stations, vector<P> &tmp_ans){

    vector<vec_int> station_connections(M);

    rep(i, tmp_ans.size()){
        if(tmp_ans.at(i).first==2){
            int st = tmp_ans.at(i).second;
            if(tmp_ans.at(i-1).first==1){
                station_connections.at(st).push_back(tmp_ans.at(i-1).second);
            }
            if(tmp_ans.at(i+1).first==1){
                station_connections.at(st).push_back(tmp_ans.at(i+1).second);
            }
        }
    }
    
    for(int station = 0;station<M;station++){
        int x = stations.at(station).x;
        int y = stations.at(station).y;

        int min_dist = INT_MAX;
        int best_x = x;
        int best_y = y;

        for(int dx=-100;dx<=100;dx+=2){
        for(int dy=-100;dy<=100;dy+=2){
            int tot_dist = 0;
            int x2 = x+dx;
            int y2 = y+dy;
            if(!(0<=x2 && x2<=1000 && 0<=y2 && y2<=1000))continue;
            stations.at(station).x = x2;
            stations.at(station).y = y2;

            for(auto star: station_connections.at(station)){
                tot_dist += stations.at(station).square_distance(a.at(star), b.at(star));
            }

            if(tot_dist<min_dist){
                min_dist = tot_dist;
                best_x = x2;
                best_y = y2;
            }
        }
        }
        stations.at(station).x=best_x;
        stations.at(station).y=best_y;
    }
}

vector<int> find_initial_route(vector<vector<pair<int, vector<P>>>> &dist_map){
    int pos = 0;
    vec_int visited(N, 0);
    vec_int result;

    while(true){
        result.push_back(pos);
        visited.at(pos) = 1;
        int min_dist = INT_MAX;
        int min_pos = -1;
        for(int i=0;i<N;i++){
            if(visited.at(i)==1)continue;
            if(min_dist>dist_map.at(pos).at(i).first){
                min_dist = dist_map.at(pos).at(i).first;
                min_pos = i;
            }
        }
        if(min_pos==-1)break;
        pos=min_pos;
    }
    result.push_back(0);
    return result;
}


void cout_ans(vector<int> &route, vector<vector<pair<int, vector<P>>>> &dist_map, vec_int &keiyu_flag){

    vector<P> result;
    for(int i=1;i<route.size();i++){
        int prev = route.at(i-1);
        int current = route.at(i);
        if(keiyu_flag.at(i-1)==-1){
            for(auto pos: dist_map.at(prev).at(current).second){
                result.push_back(pos);
            }
        }else{
            result.push_back(make_pair(1, prev));
            result.push_back(make_pair(2, keiyu_flag.at(i-1)));
            result.push_back(make_pair(1, current));
        }
    }
    cout<<result.size()<<endl;
    rep(i, result.size()){
        cout<<result.at(i).first<<" "<<result.at(i).second+1<<endl;
    }
}

void tsp(vec_int &route, vector<vector<pair<int, vector<P>>>> &dist_map){
    float start_time = get_time(false);

    int current_length = 0;
    rep(i, N){
        current_length += dist_map.at(route.at(i)).at(route.at(i+1)).first;
    }

    while(true){
        float ct = get_time(false)-start_time;
        if(ct>TIME_LIMIT_TSP)break;
        int ind1 = ro.get_rand(0, N);
        int ind2 = ro.get_rand(0, N);
        int tmp = max(ind1, ind2);
        ind1 = min(ind1, ind2);
        ind2 = tmp;
        if(ind1==ind2)continue;

        int length1 = dist_map.at(route.at(ind1)).at(route.at(ind1+1)).first;
        int length2 = dist_map.at(route.at(ind2)).at(route.at(ind2+1)).first;

        int length1_2 = dist_map.at(route.at(ind1)).at(route.at(ind2)).first;
        int length2_2 = dist_map.at(route.at(ind1+1)).at(route.at(ind2+1)).first;
        int diff = length1_2 + length2_2 - length1-length2;

        if(is_valid_transition_tsp(-1*diff, ct)){
            vec_int route2 = route;
            for(int i=ind1+1; i<=ind2;i++){
                route.at(i) = route2.at(ind2-(i-(ind1+1)));
            }
        }
    }

    return;
}

void tsp2(vec_int &route, vector<vector<pair<int, vector<P>>>> &dist_map, vec_int &keiyu_flag, vector<SpaceStation> &stations){
    float start_time = get_time(false);


    // int current_length = check_keiyu
    int current_length = check_keiyu(stations, keiyu_flag, route, dist_map);

    while(true){
        float ct = get_time(false)-start_time;
        if(ct>TIME_LIMIT_TSP)break;
        int ind1 = ro.get_rand(0, N);
        int ind2 = ro.get_rand(0, N);
        if(ind1==ind2)continue;

        int length1 = dist_map.at(route.at(ind1)).at(route.at(ind1+1)).first;
        int length2 = dist_map.at(route.at(ind2)).at(route.at(ind2+1)).first;

        int length1_2 = dist_map.at(route.at(ind1)).at(route.at(ind2)).first;
        int length2_2 = dist_map.at(route.at(ind1+1)).at(route.at(ind2+1)).first;
        int diff = length1_2 + length2_2 - length1-length2;

        if(is_valid_transition_tsp2(-1*diff, ct)){
            vec_int route2 = route;
            for(int i=ind1+1; i<=ind2;i++){
                route.at(i) = route2.at(ind2-(i-(ind1+1)));
            }
        }
    }

    return;
}


vec_int annealing(vec_int &route, vector<SpaceStation> &stations, vector<vector<pair<int, vector<P>>>> &dist_map){

    vec_int distance(N);
    vec_int keiyu(N, -1);

    for(int i=0;i<N;i++){
        // i - i+1の間で何処か別のところを経由させると良いことがあるかをチェックする
        int prev = route.at(i);
        int current = route.at(i+1);
        int original_distance = dist_map.at(prev).at(current).first;

        int after_dist = INT_MAX;
        int keiyu_station = -1;
        for(int j=0;j<M;j++){
            int tmp = stations.at(j).intermediate_distance(prev, current);
            if(after_dist>tmp){
                after_dist = tmp;
                keiyu_station = j;
            }
        }

        if(after_dist>original_distance){
            distance.at(i) = original_distance;
        }else{
            distance.at(i) = after_dist;
            keiyu.at(i) = keiyu_station;
        }
    }

    int tot_distance = 0;
    rep(i, N)tot_distance += distance.at(i);

    int count = 0;
    while(true){
        // cerr<<"count:"<<count<<endl;
        float ct = get_time(false);
        if(ct>=TIME_LIMIT*0.98)break;
        if(count%2==0){
        // if(ct>=TIME_LIMIT*0.80){
            // 2-opt
            int a = ro.get_rand(0, N);
            int b = ro.get_rand(0, N);
            if(abs(a-b)<=1)continue;
            int ind1 = min(a, b);
            int ind2 = max(a, b);
            // cerr<<city1<<" "<<city2<<endl;

            int original_distance = distance.at(ind1);
            original_distance += distance.at(ind2);

            int after1 = dist_map.at(route.at(ind1)).at(route.at(ind2)).first;
            int keiyu1 = -1;
            for(int j=0;j<M;j++){
                int tmp1 = stations.at(j).intermediate_distance(route.at(ind1), route.at(ind2));
                if(after1>tmp1){
                    after1 = tmp1;
                    keiyu1 = j;
                }
            }
            int after2 = dist_map.at(route.at(ind1+1)).at(route.at(ind2+1)).first;
            int keiyu2 = -1;
            for(int j=0;j<M;j++){
                int tmp2 = stations.at(j).intermediate_distance(route.at(ind1+1), route.at(ind2+1));
                if(after2>tmp2){
                    after2 = tmp2;
                    keiyu2 = j;
                }
            }
            int diff = (original_distance-(after1+after2));
            if(is_valid_transition_tsp(diff, ct)){
                tot_distance -= original_distance;
                tot_distance += after1+after2;
                vec_int route2 = route;
                vec_int keiyu_vec2 = keiyu;
                vec_int distance2 = distance;
                for(int i=ind1+1;i<=ind2;i++){
                    route.at(i) = route2.at(ind2-(i-(ind1+1)));
                    if(i<ind2){
                        keiyu.at(i) = keiyu_vec2.at(ind2-(i-(ind1+1))-1);
                        distance.at(i) = distance2.at(ind2-(i-(ind1+1))-1);
                    }

                    keiyu.at(ind1) = keiyu1;
                    distance.at(ind1) = after1;
                    keiyu.at(ind2) = keiyu2;
                    distance.at(ind2) = after2;
                }
            }
        }else{
            // stationを少し動かす
            int index = ro.get_rand(0, M);
            int x2, y2;
            int original_x = stations.at(index).x;
            int original_y = stations.at(index).y;
            if(count%11!=0){
                int dx = ro.get_rand(-150, 151);
                int dy = ro.get_rand(-150, 151);
                x2 = original_x + dx;
                y2 = original_y + dy;
                x2 = min(1000, x2);
                x2 = max(0, x2);
                y2 = min(1000, y2);
                y2 = max(0, y2);
            }else{
                x2 = ro.get_rand(0, 1001);
                y2 = ro.get_rand(0, 1001);
            }
            stations.at(index).x = x2;
            stations.at(index).y = y2;

            int diff = 0; //after - before
            for(int i=0;i<N;i++){
                int prev = route.at(i);
                int current = route.at(i+1);

                if(keiyu.at(i)==index){
                    int dist1 = distance.at(i);
                    int tmp = stations.at(index).intermediate_distance(prev, current);
                    tmp = min(tmp, dist_map.at(prev).at(current).first);
                    diff += tmp-dist1;
                }else{
                    int dist1 = distance.at(i);
                    int tmp = stations.at(index).intermediate_distance(prev, current);
                    if(dist1>tmp){
                        diff += tmp-dist1;
                    }
                }
            }

            if(is_valid_transition_station(-1*diff, ct)){
                // cerr<<"diff:"<<-1*diff<<endl;

                for(int i=0;i<N;i++){
                    int prev = route.at(i);
                    int current = route.at(i+1);

                    if(keiyu.at(i)==index){
                        int dist1 = distance.at(i);
                        int tmp = stations.at(index).intermediate_distance(prev, current);
                        // tmp = min(tmp, dist_map.at(prev).at(current).first);
                        // diff += tmp-dist1;
                        if(tmp<dist_map.at(prev).at(current).first){
                            distance.at(i) = tmp;
                            keiyu.at(i) = index;
                        }else{
                            distance.at(i) = dist_map.at(prev).at(current).first;
                            keiyu.at(i) = -1;
                        }
                        tot_distance -= dist1;
                        tot_distance += distance.at(i);
                    }else{
                        int dist1 = distance.at(i);
                        int tmp = stations.at(index).intermediate_distance(prev, current);
                        if(dist1>tmp){
                            distance.at(i) = tmp;
                            keiyu.at(i) = index;
                        }
                        tot_distance -= dist1;
                        tot_distance += distance.at(i);
                    }
                }
            }else{
                stations.at(index).x = original_x;
                stations.at(index).y = original_y;
            }
        }
        count++;
        // if(count==300)count=0;
    }
    /*
    for(int i=0;i<N;i++){
        // i - i+1の間で何処か別のところを経由させると良いことがあるかをチェックする
        int prev = route.at(i);
        int current = route.at(i+1);
        int original_distance = dist_map.at(prev).at(current).first;

        int after_dist = INT_MAX;
        int keiyu_station = -1;
        for(int j=0;j<M;j++){
            int tmp = stations.at(j).intermediate_distance(prev, current);
            if(after_dist>tmp){
                after_dist = tmp;
                keiyu_station = j;
            }
        }

        if(after_dist>original_distance){
            distance.at(i) = original_distance;
        }else{
            distance.at(i) = after_dist;
            keiyu.at(i) = keiyu_station;
        }
    }
    */


    cerr<<"final_count:"<<count<<endl;

    return keiyu;

}




int main(){
    get_time(true);
    cin>>N>>M;
    rep(i, N){
        int aa, bb; cin>>aa>>bb;
        a.push_back(aa);
        b.push_back(bb);
    }

    vector<vector<pair<int, vector<P>>>> dist_map = make_dist_map();

    vec_int route = find_initial_route(dist_map);
    tsp(route, dist_map);

    vector<SpaceStation> stations(M);
    rep(i, M){
        stations.at(i) = SpaceStation(ro.get_rand(0, 1001), ro.get_rand(0, 1001));
    }

    vec_int keiyu_flag = annealing(route, stations, dist_map);

    /*
    int current_reduction = check_keiyu(stations, keiyu_flag, route, dist_map);
    vec_int best_keiyu;
    while(true){
        float ct = get_time(false);
        if(ct>180)break;

        int ind = ro.get_rand(0, M);
        int original_x = stations.at(ind).x;
        int original_y = stations.at(ind).y;
        int dx = ro.get_rand(-50, 51);
        int dy = ro.get_rand(-50, 51);
        int x2 = original_x + dx;
        int y2 = original_y + dy;
        x2 = min(1000, x2);
        y2 = min(1000, y2);
        x2 = max(0, x2);
        y2 = max(0, y2);
        stations.at(ind).x = x2;
        stations.at(ind).y = y2;

        int after_reduction = check_keiyu(stations, keiyu_flag, route, dist_map);
        int diff = after_reduction - current_reduction;
        if(diff>=0){
            current_reduction = after_reduction;
            best_keiyu = keiyu_flag;
        }else{
            stations.at(ind).x = original_x;
            stations.at(ind).y = original_y;
        }
    }
    */


    rep(i, M){
        cout<<stations.at(i).x<<" "<<stations.at(i).y<<endl;
    }

    cout_ans(route, dist_map, keiyu_flag);
    /*
    rep(i, N){
        cerr<<"i:"<<i<<" "<<route.at(i)<<" "<<keiyu_flag.at(i)<<endl;
    }
    */

    return 0;
}
yukicoder

結果

テストケース

ソースコード
