結果

問題 No.5007 Steiner Space Travel
ユーザー a9ua1i0na9ua1i0n
提出日時 2022-07-30 17:51:49
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 980 ms / 1,000 ms
コード長 8,196 bytes
コンパイル時間 1,262 ms
実行使用メモリ 6,956 KB
スコア 6,901,896
最終ジャッジ日時 2022-07-30 17:52:27
合計ジャッジ時間 33,041 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#if !__INCLUDE_LEVEL__
#include __FILE__

constexpr clock_t TL = 0.95*CLOCKS_PER_SEC;
constexpr int alpha = 5;
constexpr int N = 100;
constexpr int M = 8;

using output_t = vector<pair<int,int>>;
using stations_t = array<pair<int,int>,M>;
using pos_t = array<pair<int, int>, N>;

void output(const output_t &ans, const stations_t &stations){
    REP(i,M)cout << stations[i].first << " " << stations[i].second << "\n";
    cout << ans.size() << "\n";
    REP(i,ans.size())cout << ans[i].first << " " << ans[i].second+1 << "\n";
}

int calc_energy(const output_t &ans, const stations_t &stations, const array<pair<int,int>, N> &pos){
    int energy = 0;
    int prev_x = pos[0].first;
    int prev_y = pos[0].second;
    bool prev_is_planet = true;
    REP(i,ans.size()){
        if(i==0)continue;

        int cur_energy = 0;
        int idx = ans[i].second;
        if(ans[i].first==1){
            cur_energy += (prev_x-pos[idx].first)*(prev_x-pos[idx].first)
                            + (prev_y-pos[idx].second)*(prev_y-pos[idx].second);

            if(prev_is_planet){
                cur_energy *= 5*5;
            }
            else{
                cur_energy *= 5;
            }
            prev_x = pos[idx].first;
            prev_y = pos[idx].second;
            prev_is_planet=true;
        }
        else{
            cur_energy += (prev_x-stations[idx].first)*(prev_x-stations[idx].first)
                            + (prev_y-stations[idx].second)*(prev_y-stations[idx].second);

            if(prev_is_planet){
                cur_energy *= 5;
            }
            else{
                cur_energy *= 1;
            }
            prev_x = stations[idx].first;
            prev_y = stations[idx].second;
            prev_is_planet=false;
        }
        energy += cur_energy;
    }
    return energy;
}

// calc after swapped
int calc_energy_diff(const output_t &ans, const stations_t &stations, const array<pair<int,int>, N> &pos, const int prev_energy, const int swap_a, const int swap_b){

    pair<int,int> prev_a = ans[swap_a-1].first==1? pos[ans[swap_a-1].second]: stations[ans[swap_a-1].second];
    pair<int,int> curr_a = ans[swap_a-1].first==1? pos[ans[swap_a-1].second]: stations[ans[swap_a-1].second];
    pair<int,int> next_a = ans[swap_a-1].first==1? pos[ans[swap_a-1].second]: stations[ans[swap_a-1].second];

    pair<int,int> prev_b = ans[swap_b-1].first==1? pos[ans[swap_b-1].second]: stations[ans[swap_b-1].second];
    pair<int,int> curr_b = ans[swap_b-1].first==1? pos[ans[swap_b-1].second]: stations[ans[swap_b-1].second];
    pair<int,int> next_b = ans[swap_b-1].first==1? pos[ans[swap_b-1].second]: stations[ans[swap_b-1].second];

    int pa2ca = (prev_a.first-curr_a.first)*(prev_a.first-curr_a.first) + (prev_a.second-curr_a.second)*(prev_a.second-curr_a.second);
    int ca2na = (curr_a.first-next_a.first)*(curr_a.first-next_a.first) + (curr_a.second-next_a.second)*(curr_a.second-next_a.second);
    int pb2ca = (prev_b.first-curr_a.first)*(prev_b.first-curr_a.first) + (prev_b.second-curr_a.second)*(prev_b.second-curr_a.second);
    int ca2nb = (curr_a.first-next_b.first)*(curr_a.first-next_b.first) + (curr_a.second-next_b.second)*(curr_a.second-next_b.second);

    int pb2cb = (prev_b.first-curr_b.first)*(prev_b.first-curr_b.first) + (prev_b.second-curr_b.second)*(prev_b.second-curr_b.second);
    int cb2nb = (curr_b.first-next_b.first)*(curr_b.first-next_b.first) + (curr_b.second-next_b.second)*(curr_b.second-next_b.second);
    int pa2cb = (prev_a.first-curr_b.first)*(prev_a.first-curr_b.first) + (prev_a.second-curr_b.second)*(prev_a.second-curr_b.second);
    int cb2na = (curr_b.first-next_a.first)*(curr_b.first-next_a.first) + (curr_b.second-next_a.second)*(curr_b.second-next_a.second);

    int diff_a = (pa2ca+ca2na) - (pb2ca+ca2nb);
    int diff_b = (pb2cb+cb2nb) - (pa2cb+cb2na);

    return prev_energy - (diff_a + diff_b);
}


void simple_solution(output_t &ans, const pos_t &pos){
    vector<bool> seen(N);
    seen[0]=true;
    int upper = floor((N-1)/2.0);
    REP(i,upper){
        int least_len = 1e9;
        int idx = ans[i].second;
        int best_next_idx = 0;
        REP(j,N){
            if(seen[j])continue;
            int dist = (pos[j].first-pos[idx].first)*(pos[j].first-pos[idx].first)
                         + (pos[j].second-pos[idx].second)*(pos[j].second-pos[idx].second);
            if( dist < least_len){
                best_next_idx = j;
                least_len = dist;
            }
        }
        ans[1+i].second = best_next_idx;
        seen[best_next_idx] = true;
    }
    int lower = ceil((N-1)/2.0);
    REP(i,lower){
        int least_len = 1e9;
        int idx = ans[N-i].second;
        int best_next_idx = 0;
        REP(j,N){
            if(seen[j])continue;
            int dist = (pos[j].first-pos[idx].first)*(pos[j].first-pos[idx].first)
                        + (pos[j].second-pos[idx].second)*(pos[j].second-pos[idx].second);
            if( dist < least_len){
                best_next_idx = j;
                least_len = dist;
            }
        }
        ans[N-i-1].second = best_next_idx;
        seen[best_next_idx] = true;
    }
}

void mauntain(output_t &ans, stations_t &stations, const pos_t &pos, const clock_t TL){
    mt19937_64 rng(0);
    int best_energy = calc_energy(ans, stations, pos);

    int loop = 0;
    while(true){
        if(loop%75 && clock() > TL){
            break;
        }

        {
            int swap_a = rng()%(ans.size()-2) +1;
            int swap_b = rng()%(ans.size()-2) +1;

            swap(ans[swap_a], ans[swap_b]);

            int energy = calc_energy_diff(ans, stations, pos, best_energy, swap_a, swap_b);

            if(energy < best_energy){
                best_energy = energy;
            }
            else{
                swap(ans[swap_a], ans[swap_b]);
            }
        }

        loop += 1;
    }
    #if LOCAL
        cerr << "loop: " << setw(9) << loop << "\n";
    #endif
}

void add_stations_to_midpoint(output_t &ans, stations_t &stations, const pos_t &pos){
    vector<pair<int,pair<pair<int,int>,pair<int, int>>>> lens(ans.size()-1); 
    REP(i,ans.size()-1){
        int prev_x = ans[i].first==1? pos[ans[i].second].first: stations[ans[i].second].first;
        int prev_y = ans[i].first==1? pos[ans[i].second].second: stations[ans[i].second].second;
        int next_x = ans[i+1].first==1? pos[ans[i+1].second].first: stations[ans[i+1].second].first;
        int next_y = ans[i+1].first==1? pos[ans[i+1].second].second: stations[ans[i+1].second].second;
        lens[i].first = (prev_x-next_x)*(prev_x-next_x) + (prev_y-next_y)*(prev_y-next_y);
        lens[i].second.first = pair<int,int>((prev_x+next_x)/2, (prev_y+next_y)/2);
        lens[i].second.second = ans[i];
    }
    sort(ALL(lens), greater<pair<int,pair<pair<int,int>,pair<int, int>>>>());
    REP(i,M){
        stations[i] = lens[i].second.first;
        ans.insert(find(ALL(ans), lens[i].second.second)+1, pair<int,int>(2, i));
    }
}

void solve(pos_t &pos){
    output_t ans(N+1, pair<int,int>(1,0));
    REP(i,N)ans[i].second = i;
    array<pair<int, int>, M> stations;

    simple_solution(ans, pos);
    mauntain(ans, stations, pos, TL/2);
    add_stations_to_midpoint(ans, stations, pos);
    mauntain(ans, stations, pos, TL);

    output(ans, stations);
    cerr << calc_energy(ans, stations, pos) << "\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll _N,_M;
    cin >> _N >> _M;
    array<pair<int,int>, N> pos;
    REP(i,_N)cin >> pos[i].first >> pos[i].second;

    solve(pos);

    #if LOCAL
        cerr << ((double)clock()/CLOCKS_PER_SEC) << "\n";
    #endif

    return 0;
}


//====================temp====================
#else
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define RREP(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define REPITR(itr, ARRAY) for (auto itr = (ARRAY).begin(); itr != (ARRAY).end(); ++itr)
#define RREPITR(itr, ARRAY) for (auto itr = (ARRAY).rbegin(); itr != (ARRAY).end(); ++itr)
#define ALL(n) (n).begin(),(n).end()
using ll = long long;
using ull = unsigned long long;
#endif
0