#783145 (C++17) No.5007 Steiner Space Travel

• 問題: No.5007 Steiner Space Travel
• ユーザー: highjump
• 提出日時: 2022-07-30 16:41:23
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 915 ms / 1,000 ms
• コード長: 12,121 bytes
• コンパイル時間: 1,960 ms
• 実行使用メモリ: 24,116 KB
• スコア: 7,454,054
• 最終ジャッジ日時: 2022-07-30 16:41:55
• 合計ジャッジ時間: 31,999 ms
• ジャッジサーバーID （参考情報）: judge13 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	913 ms; 23,816 KB
testcase_01	AC	915 ms; 23,912 KB
testcase_02	AC	912 ms; 24,036 KB
testcase_03	AC	913 ms; 23,828 KB
testcase_04	AC	914 ms; 23,852 KB
testcase_05	AC	914 ms; 24,116 KB
testcase_06	AC	913 ms; 24,016 KB
testcase_07	AC	913 ms; 23,932 KB
testcase_08	AC	915 ms; 23,836 KB
testcase_09	AC	911 ms; 23,880 KB
testcase_10	AC	912 ms; 23,984 KB
testcase_11	AC	914 ms; 23,916 KB
testcase_12	AC	912 ms; 23,928 KB
testcase_13	AC	914 ms; 23,796 KB
testcase_14	AC	911 ms; 23,860 KB
testcase_15	AC	913 ms; 24,024 KB
testcase_16	AC	913 ms; 23,392 KB
testcase_17	AC	913 ms; 23,160 KB
testcase_18	AC	913 ms; 23,976 KB
testcase_19	AC	914 ms; 23,828 KB
testcase_20	AC	914 ms; 23,912 KB
testcase_21	AC	914 ms; 23,880 KB
testcase_22	AC	914 ms; 24,032 KB
testcase_23	AC	914 ms; 24,020 KB
testcase_24	AC	913 ms; 24,004 KB
testcase_25	AC	914 ms; 23,956 KB
testcase_26	AC	912 ms; 23,796 KB
testcase_27	AC	913 ms; 24,032 KB
testcase_28	AC	913 ms; 23,928 KB
testcase_29	AC	913 ms; 23,920 KB

ソースコード

#pragma GCC optimize("Ofast")
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <cctype>
#include <sstream>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_map>  
#include <chrono>
#include <random>

using namespace std;

using ll = long long;
using P = pair<int, int>;
template <class T>using V = vector<T>;
template <class T>using VV = V<V<T>>;
template <class T, class U>bool chmin(T& t, const U& u) { if (t > u) { t = u; return 1; } else return 0; }
template <class T, class U>bool chmax(T& t, const U& u) { if (t < u) { t = u; return 1; } else return 0; }

#define REP(i,n) for(int i=0;i<int(n);i++)
#define FOR(i,a,b) for(int i=int(a);i<=int(b);i++)
#define FORD(i,a,b) for(int i=int(a);i>=int(b);i--)
#define MP make_pair
#define SZ(x) int(x.size())
#define ALL(x) x.begin(),x.end()
#define INF 10001000
#define endl "\n"

chrono::system_clock::time_point t_start;
const double TIME_LIMIT1 = 500, TIME_LIMIT = 900;
double last_update = 0, t_diff;
double start_temp, end_temp;

mt19937 rng;
using uni_int = uniform_int_distribution<>;
using uni_real = uniform_real_distribution<>;
using u64 = uint64_t;
using u32 = uint32_t;

V<int> y_vec = { 0, 1,0, -1 };
V<int> x_vec = { -1, 0,1, 0 };

class XorInt {
public:
    uint32_t x = 2463534242;

    XorInt() {};

    XorInt(uint32_t seed) {
        x = 2463534242 + seed;
    };

    uint32_t next() {
        x ^= x << 13; x ^= x >> 17; x ^= x << 5;
        return x;
    }

    uint32_t operator()(uint32_t l, uint32_t r) {
        return (this->next() % (r - l)) + l;
    }

    uint32_t operator()(uint32_t d) {
        return this->next() % d;
    }
};

XorInt xs;

class Xor64 {
public:
    uint64_t x = 88172645463325252ULL;

    Xor64() {};

    Xor64(uint64_t seed) {
        x = 88172645463325252ULL + seed;
    }

    uint64_t next() {
        x ^= x << 13; x ^= x >> 7; x ^= x << 17;
        return x;
    }

    uint64_t operator()(uint64_t l, uint64_t r) {
        return (this->next() % (r - l)) + l;
    }

    uint64_t operator()(uint64_t d) {
        return this->next() % d;
    }
};

Xor64 xx;

void get_time() {
    auto t_now = chrono::system_clock::now();
    t_diff = chrono::duration_cast<chrono::milliseconds>(t_now - t_start).count();
}

int N, M;
const int A = 5;
int score = 0;
int bestScore = 0;
int cnt = 0;
class Pos {
public:
    int x=0;
    int y=0;
    int kind = 0;
    int order = 0;

    Pos() {};
    Pos(int sx, int sy) :x(sx), y(sy) {};
    Pos(int sx, int sy,int o) :x(sx), y(sy),order(o) {};


};

class Planet :public Pos{
public:

    Planet() { kind = 1; };
    Planet(int sx, int sy, int o) :Pos(sx, sy,o) { kind = 1; };
    
};

class Station :public Pos {
public:

    Station() { kind = 2; };
    Station(int sx, int sy,int o) :Pos(sx, sy,o) { kind = 2; };

};

int getFuel(Pos& l, Pos& r) {
    int dis = (l.x - r.x) * (l.x - r.x) + (l.y - r.y) * (l.y - r.y);
    if (l.kind != r.kind)
        return dis * A;
    if (l.kind == 1)
        return dis * A * A;
    return dis;
}

V<Planet> planets;
V<Station> stations;

Pos& setPos(int k) {
    if (k < N)return planets[k];
    return stations[k % N];
}

int getScore(V<int>& route) {
    int sumFuel = 0;
    FOR(i, 1, route.size() - 1) {
        Pos& current = setPos(route[i - 1]);
        Pos& target = setPos(route[i]);
        sumFuel += getFuel(current, target);
    }

    return int(round(1000000000.0 / (1000.0 + sqrt(sumFuel))));
}

class State {
public:
    int fuel=0;
    int counter=0;
    V<int> route;

    State() {};
    State(int f, int c, V<int> r) :fuel(f), counter(c), route(r) {};
};

bool operator < (const State& l, const State& r) {
    return l.fuel > r.fuel;
}

class Ship {
public:
    V<bool> visited;
    int counter = 0;
    int last = 0;
    int fuel = 0;

    Ship(){};

    void play(int target) {
        if (target < N) {
            visited[target] = true;
            counter++;
        }
        Pos& temp = setPos(last);
        Pos& next = setPos(target);
        fuel += getFuel(temp, next);
        last = target;
    }

    void play(V<int>& route) {
        FOR(i, 1, route.size() - 1)
            play(route[i]);
    }

    void back(int target,int prev) {
        last = prev;
        Pos& temp = setPos(last);
        Pos& next = setPos(target);
        fuel -= getFuel(temp, next);
        if (target < N) {
            visited[target] = false;
            counter--;
        }
    }

    void back(V<int>& route) {
        FORD(i, route.size() - 1, 1)
            back(route[i], route[i - 1]);
    }
};

Ship ship;

//State beamSearch(State& state, int beam_width, int beam_depth) {
//    priority_queue<State> now_beam;
//    State best_state;
//
//    now_beam.push(state);
//    REP(t, beam_depth) {
//        priority_queue<State> next_beam;
//        REP(i, beam_width) {
//            if (now_beam.empty())break;
//            //多様性もいつか考える
//            State now_state = now_beam.top(); now_beam.pop();
//            ship.play(now_state.route);
//            if (ship.counter == N - 1) {
//                ship.play(0);
//                State newState = State(ship.fuel, ship.counter, now_state.route);
//                newState.route.push_back(0);
//                if (best_state.counter < best_state.counter)best_state.counter;
//                ship.back(0);
//            }
//            else {
//
//            }
//            /*auto legal_actions = now_state.legalActions();
//            for (const auto& action : legal_actions) {
//                State next_state = now_state;
//                next_state.advance(action);
//                next_state.evaluateScore();
//                if (t == 0)next_state.first_action_ = action;
//                next_beam.push(next_state);
//            }*/
//        }
//
//        now_beam = next_beam;
//        if (now_beam.empty())break;
//        best_state = now_beam.top();
//    }
//    return best_state;
//}

V<int> chokudaiSearch(int beam_width) {
    int beam_depth = N;
    auto beam = V<priority_queue<State>>(beam_depth + 1);
    REP(t, beam_depth + 1) {
        beam[t] = priority_queue<State>();
    }
    State initState = State(0, 0, V<int>());
    initState.route.push_back(0);
    beam[0].push(initState);
    while (t_diff < TIME_LIMIT) {
        REP(t, beam_depth) {
            auto& now_beam = beam[t];
            auto& next_beam = beam[t + 1];
            //cerr << "[" << t << "]" << now_beam.size() << endl;
            //中身が多すぎるときに減らす(多様性は考えていない)
            int max_load = 1000;
            if (SZ(now_beam) > max_load) {
                priority_queue<State> pool;
                REP(i, max_load/2) {
                    pool.push(now_beam.top());
                    now_beam.pop();
                }
                now_beam.swap(pool);
            }
            REP(i, beam_width) {
                if (now_beam.empty())break;
                State now_state = now_beam.top();
                //cerr << "Yes" << endl;
                ship.play(now_state.route);
                //if (now_state.isDone()) {
                //    break;
                //}
                now_beam.pop();
                if (t == N - 1) {
                    ship.play(0);
                    now_state.route.push_back(0);
                    State newState = State(ship.fuel, ship.counter, now_state.route);
                    next_beam.push(newState);
                    now_state.route.pop_back();
                    ship.back(0,now_state.route.back());
                    /*REP(a, M) {
                        ship.play(N + a);
                        now_state.route.push_back(N+a);
                        ship.play(0);
                        now_state.route.push_back(0);
                        State newState = State(ship.fuel, ship.counter, now_state.route);
                        next_beam.push(newState);
                        now_state.route.pop_back();
                        ship.back(0, now_state.route.back());
                        now_state.route.pop_back();
                        ship.back(N + a, now_state.route.back());
                    }*/

                }
                else {
                    FOR(npos, 1, N - 1) {
                        if (ship.visited[npos])continue;
                        ship.play(npos);
                        now_state.route.push_back(npos);
                        State newState = State(ship.fuel, ship.counter, now_state.route);
                        next_beam.push(newState);
                        now_state.route.pop_back();
                        ship.back(npos, now_state.route.back());
                        /*REP(a, M) {
                            ship.play(N + a);
                            now_state.route.push_back(N + a);
                            ship.play(npos);
                            now_state.route.push_back(npos);
                            State newState = State(ship.fuel, ship.counter, now_state.route);
                            next_beam.push(newState);
                            now_state.route.pop_back();
                            ship.back(npos, now_state.route.back());
                            now_state.route.pop_back();
                            ship.back(N + a, now_state.route.back());
                        }*/
                    }
                }
                ship.back(now_state.route);

                //auto legal_actions = now_state.legalActions();
                //for (auto& action : legal_actions) {
                //    State next_state = now_state;
                //    next_state.advance(action);
                //    next_state.evaluateScore();
                //    if (t == 0)next_state.first_action_ = action;
                //    next_beam.push(next_state);
                //}
            }
            get_time();
            if (t_diff > TIME_LIMIT)break;
        }
        cnt++;
        if (t_diff > TIME_LIMIT)break;
        //cerr << "Yes" << endl;
    }
    return beam[N].top().route;
    /*FORD(t, beam_depth, 0) {
        auto& now_beam = beam[t];
        if (!now_beam.empty()) {
            return now_beam.top().first_action;
        }
    }*/
    //return -1;
}

void out(V<int>& route) {
    REP(i, M) {
        cout << stations[i].x << " " << stations[i].y << endl;
    }
    cout << route.size() << endl;
    for(auto p:route) {
        Pos& pos = setPos(p);
        cout << pos.kind << " " << pos.order << endl;
    }
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(15);
    t_start = chrono::system_clock::now();

    get_time();
    cin >> N >> M;
    planets = V<Planet>(N);
    stations = V<Station>(M);
    ship.visited = V<bool>(N);
    REP(i, N) {
        int x, y; cin >> x >> y;
        planets[i] = Planet(x, y,i+1);
    }

    V<int> xpos = { 250,500,750,250,750,250,500,750 };
    V<int> ypos = { 250,250,250,500,500,750,750,750 };

    REP(i, M) {
        int x = xpos[i];
        int y = ypos[i];
        stations[i] = Station(x, y, i + 1);
    }

    V<int> route;
    //REP(i, N)route.push_back(i);
    //route.push_back(0);
    route = chokudaiSearch(1);

    V<int>new_route;
    new_route.push_back(0);

    FOR(i, 1, N) {
        Pos& temp = setPos(route[i - 1]);
        Pos& next = setPos(route[i]);
        int now = getFuel(temp, next);
        int ans = -1;
        REP(j, M) {
            Pos& mid = stations[j];
            if (chmin(now, getFuel(temp, mid) + getFuel(mid, next)))ans = j + N;
        }
        if (ans > 0)new_route.push_back(ans);
        new_route.push_back(route[i]);
    }

    score = getScore(new_route);
    out(new_route);
    get_time();

    cerr << "time=" << int(t_diff) << " ms" << endl;
    cerr << "score=" << score << endl;
    //cerr << "last=" << last_update << endl;
    cerr << "cnt=" << cnt << endl;
    //cerr << "update=" << update_cnt << endl;
    return 0;
}