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

提出ソース

結果

問題	No.5007 Steiner Space Travel
ユーザー	Forested
提出日時	2022-07-30 17:59:28
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	953 ms / 1,000 ms
コード長	12,531 bytes
コンパイル時間	1,357 ms
実行使用メモリ	5,164 KB
スコア	8,686,514
最終ジャッジ日時	2022-07-30 18:00:33
合計ジャッジ時間	32,472 ms
ジャッジサーバーID （参考情報）	judge16 / judge13
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	952 ms 4,904 KB
testcase_01	AC	953 ms 4,904 KB
testcase_02	AC	953 ms 4,900 KB
testcase_03	AC	952 ms 4,904 KB
testcase_04	AC	952 ms 5,160 KB
testcase_05	AC	953 ms 4,904 KB
testcase_06	AC	952 ms 4,900 KB
testcase_07	AC	952 ms 4,900 KB
testcase_08	AC	953 ms 4,900 KB
testcase_09	AC	952 ms 4,900 KB
testcase_10	AC	952 ms 4,900 KB
testcase_11	AC	952 ms 4,904 KB
testcase_12	AC	952 ms 4,904 KB
testcase_13	AC	952 ms 4,904 KB
testcase_14	AC	953 ms 5,164 KB
testcase_15	AC	952 ms 5,160 KB
testcase_16	AC	952 ms 4,904 KB
testcase_17	AC	952 ms 4,904 KB
testcase_18	AC	953 ms 4,904 KB
testcase_19	AC	953 ms 4,904 KB
testcase_20	AC	953 ms 4,900 KB
testcase_21	AC	953 ms 4,900 KB
testcase_22	AC	952 ms 5,160 KB
testcase_23	AC	952 ms 4,904 KB
testcase_24	AC	952 ms 4,904 KB
testcase_25	AC	953 ms 4,900 KB
testcase_26	AC	952 ms 4,900 KB
testcase_27	AC	952 ms 5,156 KB
testcase_28	AC	951 ms 4,900 KB
testcase_29	AC	952 ms 4,904 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#ifndef LOCAL
#define FAST_IO
#endif

// ===== template.hpp =====
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define OVERRIDE(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32) (n); ++i)
#define REP3(i, m, n) for (i32 i = (i32) (m); i < (i32) (n); ++i)
#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER(i, n) for (i32 i = (i32) (n) - 1; i >= 0; --i)
#define ALL(x) begin(x), end(x)

using namespace std;

using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = __uint128_t;
using i32 = signed int;
using i64 = signed long long;
using i128 = __int128_t;
using f64 = double;
using f80 = long double;

template <typename T>
using Vec = vector<T>;

template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

istream &operator>>(istream &is, i128 &x) {
    i64 v;
    is >> v;
    x = v;
    return is;
}
ostream &operator<<(ostream &os, i128 x) {
    os << (i64) x;
    return os;
}
istream &operator>>(istream &is, u128 &x) {
    u64 v;
    is >> v;
    x = v;
    return is;
}
ostream &operator<<(ostream &os, u128 x) {
    os << (u64) x;
    return os;
}

[[maybe_unused]] constexpr i32 INF = 1000000100;
[[maybe_unused]] constexpr i64 INF64 = 3000000000000000100;
struct SetUpIO {
    SetUpIO() {
#ifdef FAST_IO
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
#endif
        cout << fixed << setprecision(15);
    }
} set_up_io;
// ===== template.hpp =====

#ifdef DEBUGF
#include "cpl/template/debug.hpp"
#else
#define DBG(x) (void) 0
#endif

// ===== timer.hpp =====

#include <chrono>

class Timer {
    std::chrono::high_resolution_clock::time_point st;
    
public:
    Timer() : st(std::chrono::high_resolution_clock::now()) {}
    
    void reset() {
        st = std::chrono::high_resolution_clock::now();
    }
    
    int elapsed() {
        auto ed = std::chrono::high_resolution_clock::now();
        return (int) std::chrono::duration_cast<std::chrono::milliseconds>(ed - st).count();
    }
};
// ===== timer.hpp =====
// ===== xorshift.hpp =====

class XorShift64 {
    unsigned long long x;
    
public:
    XorShift64(unsigned long long seed) : x((seed + 14213124131ull) ^ 103920984124ull) {}
    
    unsigned long long operator()() {
        x = x ^ (x << 13);
        x = x ^ (x >> 7);
        x = x ^ (x << 17);
        return x;
    }
    
    template <typename T>
    T uniform(T mn, T mx) {
        return mn + (T) ((*this)() % (mx - mn + 1));
    }
    
    double as_f64() {
        return (double) (*this)() / ~0ull;
    }
};
// ===== xorshift.hpp =====

constexpr i32 N = 100;
constexpr i32 M = 8;
constexpr i32 POS_MIN = 0;
constexpr i32 POS_MAX = 1000;
[[maybe_unused]] constexpr i32 V_MIN = 1;
[[maybe_unused]] constexpr i32 V_MAX = 100000;

int dist_two(int x, int y, int p, int q) {
    return (x - p) * (x - p) + (y - q) * (y - q);
}

struct Input {
    i32 n, m;
    Vec<i32> a, b;
};

struct Output {
    Vec<i32> c, d;
    i32 v;
    Vec<i32> t, r;
};

Input read_input() {
    auto &fin = cin;
    i32 n, m;
    fin >> n >> m;
    assert(n == N);
    assert(m == M);
    Vec<i32> a(n), b(n);
    REP(i, n) {
        fin >> a[i] >> b[i];
        assert(POS_MIN <= a[i] && a[i] <= POS_MAX);
        assert(POS_MIN <= b[i] && b[i] <= POS_MAX);
    }
    return Input{n, m, a, b};
}

i32 calc_energey(const Input &input, const Output &output, i32 i, i32 j) {
    i32 x, y, p, q;
    if (output.t[i] == 0) {
        x = input.a[output.r[i]];
        y = input.b[output.r[i]];
    } else {
        x = output.c[output.r[i]];
        y = output.d[output.r[i]];
    }
    if (output.t[j] == 0) {
        p = input.a[output.r[j]];
        q = input.b[output.r[j]];
    } else {
        p = output.c[output.r[j]];
        q = output.d[output.r[j]];
    }
    i32 dist = dist_two(p, q, x, y);
    if (output.t[i] == 0 && output.t[j] == 0) {
        return 25 * dist;
    } else if (output.t[i] == 1 && output.t[j] == 1) {
        return dist;
    } else {
        return 5 * dist;
    }
}

i64 calc_energey_sum(const Input &input, const Output &output) {
    i64 s = 0;
    REP(i, output.v - 1) {
        s += calc_energey(input, output, i, i + 1);
    }
    return s;
}

pair<Vec<i32>, Vec<i32>> compute_stations_position(const Input &input, XorShift64 &rd) {
    const auto score = [&input](const Vec<i32> &c, const Vec<i32> &d) -> i64 {
        i64 sum = 0;
        REP(i, input.n) {
            i32 mn = INF;
            REP(j, input.m) {
                chmin(mn, dist_two(input.a[i], input.b[i], c[j], d[j]));
            }
            sum += 5 * mn;
        }
        REP(i, input.m) {
            i32 mn = INF;
            REP(j, input.m) {
                chmin(mn, dist_two(c[i], c[j], c[j], d[j]));
            }
            sum += mn;
        }
        return sum;
    };
    
    Vec<i32> c(input.m), d(input.m);
    REP(i, input.m) {
        c[i] = rd.uniform(POS_MIN, POS_MAX);
        d[i] = rd.uniform(POS_MIN, POS_MAX);
    }
    i64 cur_score = score(c, d);
    
    constexpr i32 TL = 300;
    Timer timer;
    i32 iter = 0;
    while (true) {
        if (iter % 64 == 0) {
            if (timer.elapsed() > TL) {
                break;
            }
        }
        
        i32 stt = rd.uniform(0, input.m - 1);
        i32 dx = rd.uniform(-80, 80);
        i32 dy = rd.uniform(-80, 80);
        i32 old_x = c[stt], old_y = d[stt];
        c[stt] = clamp(c[stt] + dx, POS_MIN, POS_MAX);
        d[stt] = clamp(d[stt] + dy, POS_MIN, POS_MAX);
        i64 new_score = score(c, d);
        i64 diff = new_score - cur_score;
        if (diff <= 0) {
            cur_score = new_score;
        } else {
            c[stt] = old_x;
            d[stt] = old_y;
        }
        
        ++iter;
    }
    cerr << "iteration: " << iter << '\n';
    return make_pair(c, d);
}

Output solve(Input input) {
    constexpr i32 TL = 950;
    Timer timer;
    XorShift64 rd(998244353);
    
    Output output;
    output.c.resize(input.m, 0);
    output.d.resize(input.m, 0);
    output.v = 0;
    
    tie(output.c, output.d) = compute_stations_position(input, rd);
    
    output.v = input.n + 1;
    output.t.resize(input.n + 1, 0);
    output.r.resize(input.n + 1, 0);
    iota(output.r.begin(), output.r.begin() + input.n, 0);
    
    auto uniform_range = [&rd](i32 n) -> pair<i32, i32> {
        i32 l = rd.uniform(0, n);
        i32 r = rd.uniform(0, n);
        while (l == r) {
            l = rd.uniform(0, n);
            r = rd.uniform(0, n);
        }
        if (l > r) {
            swap(l, r);
        }
        return pair<i32, i32>(l, r);
    };
    
    auto try_reverse = [&](double temp) -> void {
        auto [l, r] = uniform_range(output.v - 2);
        ++l;
        ++r;
        
        i32 diff = 0;
        diff -= calc_energey(input, output, l - 1, l);
        diff -= calc_energey(input, output, r - 1, r);
        diff += calc_energey(input, output, l - 1, r - 1);
        diff += calc_energey(input, output, l, r);
        if (diff <= 0 || rd.as_f64() < exp(-diff / temp)) {
            reverse(output.t.begin() + l, output.t.begin() + r);
            reverse(output.r.begin() + l, output.r.begin() + r);
        }
    };
    
    auto try_insert = [&]([[maybe_unused]] double temp) -> void {
        i32 stt = rd.uniform(0, input.m - 1);
        i32 pos = rd.uniform(0, output.v - 2);
        i32 diff = 0;
        diff -= calc_energey(input, output, pos, pos + 1);
        if (output.t[pos] == 0) {
            diff += 5 * dist_two(input.a[output.r[pos]], input.b[output.r[pos]], output.c[stt], output.d[stt]);
        } else {
            diff += dist_two(output.c[output.r[pos]], output.d[output.r[pos]], output.c[stt], output.d[stt]);
        }
        if (output.t[pos + 1] == 0) {
            diff += 5 * dist_two(input.a[output.r[pos + 1]], input.b[output.r[pos + 1]], output.c[stt], output.d[stt]);
        } else {
            diff += dist_two(output.c[output.r[pos + 1]], output.d[output.r[pos + 1]], output.c[stt], output.d[stt]);
        }
        if (diff < 0 || rd.as_f64() < exp(-diff / temp)) {
            output.v += 1;
            output.t.insert(output.t.begin() + pos + 1, 1);
            output.r.insert(output.r.begin() + pos + 1, stt);
        }
    };
    
    auto try_remove = [&]([[maybe_unused]] double temp) -> void {
        Vec<i32> stt_pos;
        REP(i, output.v) {
            if (output.t[i] == 1) {
                stt_pos.push_back(i);
            }
        }
        if (stt_pos.empty()) {
            return;
        }
        i32 pos = stt_pos[rd.uniform(0, (i32) stt_pos.size() - 1)];
        i32 stt = output.r[pos];
        i32 diff = 0;
        diff += calc_energey(input, output, pos - 1, pos + 1);
        if (output.t[pos] == 0) {
            diff -= 5 * dist_two(input.a[output.r[pos]], input.b[output.r[pos]], output.c[stt], output.d[stt]);
        } else {
            diff -= dist_two(output.c[output.r[pos]], output.d[output.r[pos]], output.c[stt], output.d[stt]);
        }
        if (output.t[pos + 1] == 0) {
            diff -= 5 * dist_two(input.a[output.r[pos + 1]], input.b[output.r[pos + 1]], output.c[stt], output.d[stt]);
        } else {
            diff -= dist_two(output.c[output.r[pos + 1]], output.d[output.r[pos + 1]], output.c[stt], output.d[stt]);
        }
        if (diff < 0 || rd.as_f64() < exp(-diff / temp)) {
            output.v -= 1;
            output.t.erase(output.t.begin() + pos);
            output.r.erase(output.r.begin() + pos);
        }
    };
    
    auto optimize = [&](i32 stt) -> void {
        Vec<i32> pos;
        REP(i, output.v) {
            if (output.t[i] == 1 && output.r[i] == stt) {
                pos.push_back(i);
            }
        }
        if (pos.empty()) {
            return;
        }
        i64 sq = 0, ln_x = 0, ln_y = 0;
        for (i32 p : pos) {
            if (output.t[p - 1] == 0) {
                sq += 5;
                ln_x -= 10 * input.a[output.r[p - 1]];
                ln_y -= 10 * input.b[output.r[p - 1]];
            } else if (output.r[p - 1] != stt) {
                sq += 1;
                ln_x -= 2 * output.c[output.r[p - 1]];
                ln_y -= 2 * output.d[output.r[p - 1]];
            }
            if (output.t[p + 1] == 0) {
                sq += 5;
                ln_x -= 10 * input.a[output.r[p + 1]];
                ln_y -= 10 * input.b[output.r[p + 1]];
            } else if (output.r[p + 1] != stt) {
                sq += 1;
                ln_x -= 2 * output.c[output.r[p + 1]];
                ln_y -= 2 * output.d[output.r[p + 1]];
            }
        }
        output.c[stt] = clamp((i32) round(-ln_x / 2.0 / sq), POS_MIN, POS_MAX);
        output.d[stt] = clamp((i32) round(-ln_y / 2.0 / sq), POS_MIN, POS_MAX);
    };
    
    // atode chanto kimeru
    constexpr double BEGIN_TEMP = 30;
    constexpr double END_TEMP = 0.01;
    double temp = BEGIN_TEMP;
    i32 iter = 0;
    while (true) {
        if (iter % 64 == 0) {
            double t = 1.0 * timer.elapsed() / TL;
            if (t > 1) {
                break;
            }
            temp = (1 - t) * BEGIN_TEMP + t * END_TEMP;
        }
        i32 type = rd.uniform(0, 9);
        if (type >= 0 && type <= 7) {
            try_reverse(temp);
        } else if (type == 8) {
            try_insert(temp);
        } else {
            try_remove(temp);
        }
        if (iter % 4096 == 0) {
            REP(i, input.m) {
                optimize(i);
            }
        }
        ++iter;
    }
    cerr << "iteration: " << iter << '\n';
    
    REP(i, input.m) {
        optimize(i);
    }
    
    return output;
}

int main() {
    Input input = read_input();
    Output output = solve(input);
    REP(i, input.m) {
        cout << output.c[i] << ' ' << output.d[i] << '\n';
    }
    cout << output.v << '\n';
    REP(i, output.v) {
        cout << output.t[i] + 1 << ' ' << output.r[i] + 1 << '\n';
    }
    //cerr << "score: " << 1e9 / (1000.0 + sqrt(calc_energey_sum(input, output))) << '\n';
}

yukicoder

結果

テストケース

ソースコード