結果
問題 | No.5011 Better Mo's Algorithm is Needed!! (Weighted) |
ユーザー | hitonanode |
提出日時 | 2022-12-17 01:45:16 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 4,763 ms / 5,000 ms |
コード長 | 22,689 bytes |
コンパイル時間 | 3,882 ms |
実行使用メモリ | 131,424 KB |
スコア | 35,153,874,636 |
最終ジャッジ日時 | 2022-12-17 01:55:39 |
合計ジャッジ時間 | 618,525 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge16 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4,757 ms
129,616 KB |
testcase_01 | AC | 4,758 ms
129,724 KB |
testcase_02 | AC | 4,758 ms
129,448 KB |
testcase_03 | AC | 4,762 ms
129,684 KB |
testcase_04 | AC | 4,759 ms
129,456 KB |
testcase_05 | AC | 4,757 ms
129,236 KB |
testcase_06 | AC | 4,758 ms
130,040 KB |
testcase_07 | AC | 4,757 ms
130,016 KB |
testcase_08 | AC | 4,757 ms
129,820 KB |
testcase_09 | AC | 4,758 ms
130,252 KB |
testcase_10 | AC | 4,758 ms
129,832 KB |
testcase_11 | AC | 4,757 ms
130,104 KB |
testcase_12 | AC | 4,757 ms
129,564 KB |
testcase_13 | AC | 4,759 ms
129,556 KB |
testcase_14 | AC | 4,756 ms
129,288 KB |
testcase_15 | AC | 4,759 ms
129,568 KB |
testcase_16 | AC | 4,756 ms
129,420 KB |
testcase_17 | AC | 4,758 ms
129,428 KB |
testcase_18 | AC | 4,757 ms
130,016 KB |
testcase_19 | AC | 4,759 ms
129,828 KB |
testcase_20 | AC | 4,757 ms
129,836 KB |
testcase_21 | AC | 4,760 ms
130,228 KB |
testcase_22 | AC | 4,759 ms
130,040 KB |
testcase_23 | AC | 4,760 ms
130,244 KB |
testcase_24 | AC | 4,757 ms
129,676 KB |
testcase_25 | AC | 4,758 ms
129,556 KB |
testcase_26 | AC | 4,757 ms
129,352 KB |
testcase_27 | AC | 4,757 ms
129,604 KB |
testcase_28 | AC | 4,759 ms
129,512 KB |
testcase_29 | AC | 4,756 ms
129,464 KB |
testcase_30 | AC | 4,759 ms
129,992 KB |
testcase_31 | AC | 4,756 ms
129,836 KB |
testcase_32 | AC | 4,757 ms
129,836 KB |
testcase_33 | AC | 4,757 ms
130,220 KB |
testcase_34 | AC | 4,758 ms
129,840 KB |
testcase_35 | AC | 4,757 ms
130,104 KB |
testcase_36 | AC | 4,758 ms
129,720 KB |
testcase_37 | AC | 4,757 ms
129,680 KB |
testcase_38 | AC | 4,758 ms
129,520 KB |
testcase_39 | AC | 4,758 ms
129,576 KB |
testcase_40 | AC | 4,758 ms
129,296 KB |
testcase_41 | AC | 4,757 ms
129,416 KB |
testcase_42 | AC | 4,757 ms
129,880 KB |
testcase_43 | AC | 4,759 ms
130,036 KB |
testcase_44 | AC | 4,758 ms
129,876 KB |
testcase_45 | AC | 4,758 ms
130,300 KB |
testcase_46 | AC | 4,757 ms
129,892 KB |
testcase_47 | AC | 4,758 ms
130,144 KB |
testcase_48 | AC | 4,756 ms
129,572 KB |
testcase_49 | AC | 4,757 ms
129,704 KB |
testcase_50 | AC | 4,757 ms
129,440 KB |
testcase_51 | AC | 4,757 ms
129,724 KB |
testcase_52 | AC | 4,757 ms
129,424 KB |
testcase_53 | AC | 4,757 ms
129,424 KB |
testcase_54 | AC | 4,760 ms
130,084 KB |
testcase_55 | AC | 4,757 ms
129,728 KB |
testcase_56 | AC | 4,760 ms
129,816 KB |
testcase_57 | AC | 4,757 ms
130,216 KB |
testcase_58 | AC | 4,758 ms
129,964 KB |
testcase_59 | AC | 4,757 ms
130,300 KB |
testcase_60 | AC | 4,759 ms
129,700 KB |
testcase_61 | AC | 4,760 ms
129,552 KB |
testcase_62 | AC | 4,758 ms
129,292 KB |
testcase_63 | AC | 4,757 ms
129,700 KB |
testcase_64 | AC | 4,757 ms
129,412 KB |
testcase_65 | AC | 4,758 ms
129,508 KB |
testcase_66 | AC | 4,757 ms
129,816 KB |
testcase_67 | AC | 4,759 ms
129,952 KB |
testcase_68 | AC | 4,759 ms
129,820 KB |
testcase_69 | AC | 4,760 ms
130,080 KB |
testcase_70 | AC | 4,759 ms
130,040 KB |
testcase_71 | AC | 4,758 ms
130,232 KB |
testcase_72 | AC | 4,757 ms
129,772 KB |
testcase_73 | AC | 4,757 ms
129,552 KB |
testcase_74 | AC | 4,756 ms
129,512 KB |
testcase_75 | AC | 4,763 ms
129,776 KB |
testcase_76 | AC | 4,758 ms
129,672 KB |
testcase_77 | AC | 4,758 ms
128,972 KB |
testcase_78 | AC | 4,757 ms
129,948 KB |
testcase_79 | AC | 4,759 ms
129,696 KB |
testcase_80 | AC | 4,758 ms
130,072 KB |
testcase_81 | AC | 4,759 ms
130,312 KB |
testcase_82 | AC | 4,757 ms
129,936 KB |
testcase_83 | AC | 4,759 ms
130,304 KB |
testcase_84 | AC | 4,757 ms
129,612 KB |
testcase_85 | AC | 4,759 ms
129,780 KB |
testcase_86 | AC | 4,757 ms
129,348 KB |
testcase_87 | AC | 4,758 ms
129,476 KB |
testcase_88 | AC | 4,758 ms
129,352 KB |
testcase_89 | AC | 4,756 ms
129,284 KB |
testcase_90 | AC | 4,758 ms
130,016 KB |
testcase_91 | AC | 4,758 ms
130,248 KB |
testcase_92 | AC | 4,759 ms
130,072 KB |
testcase_93 | AC | 4,762 ms
130,136 KB |
testcase_94 | AC | 4,759 ms
129,564 KB |
testcase_95 | AC | 4,757 ms
130,024 KB |
testcase_96 | AC | 4,760 ms
129,776 KB |
testcase_97 | AC | 4,758 ms
129,668 KB |
testcase_98 | AC | 4,758 ms
129,460 KB |
testcase_99 | AC | 4,758 ms
129,752 KB |
testcase_100 | AC | 4,758 ms
129,348 KB |
testcase_101 | AC | 4,758 ms
130,236 KB |
testcase_102 | AC | 4,758 ms
131,424 KB |
testcase_103 | AC | 4,759 ms
130,924 KB |
testcase_104 | AC | 4,757 ms
130,140 KB |
testcase_105 | AC | 4,759 ms
130,988 KB |
testcase_106 | AC | 4,756 ms
130,232 KB |
testcase_107 | AC | 4,758 ms
131,228 KB |
testcase_108 | AC | 4,756 ms
130,000 KB |
testcase_109 | AC | 4,756 ms
130,528 KB |
testcase_110 | AC | 4,755 ms
130,480 KB |
testcase_111 | AC | 4,759 ms
130,484 KB |
testcase_112 | AC | 4,757 ms
130,784 KB |
testcase_113 | AC | 4,757 ms
129,628 KB |
testcase_114 | AC | 4,758 ms
130,392 KB |
testcase_115 | AC | 4,756 ms
130,128 KB |
testcase_116 | AC | 4,757 ms
131,108 KB |
testcase_117 | AC | 4,756 ms
130,812 KB |
testcase_118 | AC | 4,758 ms
130,640 KB |
testcase_119 | AC | 4,757 ms
130,360 KB |
ソースコード
#include <algorithm> #include <array> #include <bitset> #include <cassert> #include <chrono> #include <cmath> #include <complex> #include <deque> #include <forward_list> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iostream> #include <limits> #include <list> #include <map> #include <numeric> #include <queue> #include <random> #include <set> #include <sstream> #include <stack> #include <string> #include <tuple> #include <type_traits> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> using namespace std; using lint = long long; using pint = pair<int, int>; using plint = pair<lint, lint>; struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_; #define ALL(x) (x).begin(), (x).end() #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++) #define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--) #define REP(i, n) FOR(i,0,n) #define IREP(i, n) IFOR(i,0,n) template <typename T, typename V> void ndarray(vector<T>& vec, const V& val, int len) { vec.assign(len, val); } template <typename T, typename V, typename... Args> void ndarray(vector<T>& vec, const V& val, int len, Args... args) { vec.resize(len), for_each(begin(vec), end(vec), [&](T& v) { ndarray(v, val, args...); }); } template <typename T> bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; } template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; } const std::vector<std::pair<int, int>> grid_dxs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); } template <class T1, class T2> T1 floor_div(T1 num, T2 den) { return (num > 0 ? num / den : -((-num + den - 1) / den)); } template <class T1, class T2> std::pair<T1, T2> operator+(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first + r.first, l.second + r.second); } template <class T1, class T2> std::pair<T1, T2> operator-(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first - r.first, l.second - r.second); } template <class T> std::vector<T> sort_unique(std::vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; } template <class T> int arglb(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); } template <class T> int argub(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); } template <class IStream, class T> IStream &operator>>(IStream &is, std::vector<T> &vec) { for (auto &v : vec) is >> v; return is; } template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec); template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr); template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec); template <class OStream, class T, class U> OStream &operator<<(OStream &os, const pair<T, U> &pa); template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec); template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec); template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec); template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec); template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa); template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp); template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp); template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl); template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; } template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr) { os << '['; for (auto v : arr) os << v << ','; os << ']'; return os; } template <class... T> std::istream &operator>>(std::istream &is, std::tuple<T...> &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); return is; } template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl) { os << '('; std::apply([&os](auto &&... args) { ((os << args << ','), ...);}, tpl); return os << ')'; } template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; } template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa) { return os << '(' << pa.first << ',' << pa.second << ')'; } template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; } template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; } #ifdef HITONANODE_LOCAL const string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m"; #define dbg(x) std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl #define dbgif(cond, x) ((cond) ? std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl : std::cerr) #else #define dbg(x) ((void)0) #define dbgif(cond, x) ((void)0) #endif #include <algorithm> #include <tuple> #include <utility> #include <vector> // 2次元の kd-tree // 矩形内の全頂点取得が可能 // Verified: abc234h https://atcoder.jp/contests/abc234/submissions/28456735 template <class T> struct kd_tree { std::vector<std::pair<T, T>> _ps; struct Node { T xmin, xmax, ymin, ymax; std::vector<int> ids; int lch, rch; template <class OStream> friend OStream &operator<<(OStream &os, const Node &n) { os << "{Node[" << n.xmin << ", " << n.xmax << "]x[" << n.ymin << ", " << n.ymax << "], ids=("; for (auto i : n.ids) os << i << ','; os << "), chs=" << n.lch << ',' << n.rch << '}'; return os; } }; std::vector<Node> _nodes; using Tpl = std::tuple<int, T, T>; std::vector<Tpl> _tmp; int _build(int l, int r, int nsplitx, int nsplity) { if (l >= r) return -1; T xmin = std::get<1>(_tmp[l]), xmax = xmin, ymin = std::get<2>(_tmp[l]), ymax = ymin; std::vector<int> ids(r - l); for (int i = l; i < r; ++i) { T x = std::get<1>(_tmp[i]), y = std::get<2>(_tmp[i]); if (x < xmin) xmin = x; if (x > xmax) xmax = x; if (y < ymin) ymin = y; if (y > ymax) ymax = y; ids[i - l] = std::get<0>(_tmp[i]); } const int _node_id = _nodes.size(); _nodes.push_back({xmin, xmax, ymin, ymax, ids, -1, -1}); // Decide which direction to split bool split_x = xmax - xmin > ymax - ymin; if (nsplitx > 3) split_x = false; // 同じ方向に何度も連続で切らない if (nsplity > 3) split_x = true; if (r - l > 1) { int c = (l + r) / 2; if (split_x) { // split x std::nth_element( _tmp.begin() + l, _tmp.begin() + c, _tmp.begin() + r, [&](const Tpl &l, const Tpl &r) { return std::get<1>(l) < std::get<1>(r); }); _nodes[_node_id].lch = _build(l, c, nsplitx + 1, 0); _nodes[_node_id].rch = _build(c, r, nsplitx + 1, 0); } else { // split y std::nth_element( _tmp.begin() + l, _tmp.begin() + c, _tmp.begin() + r, [&](const Tpl &l, const Tpl &r) { return std::get<2>(l) < std::get<2>(r); }); _nodes[_node_id].lch = _build(l, c, 0, nsplity + 1); _nodes[_node_id].rch = _build(c, r, 0, nsplity + 1); } } return _node_id; } void _initialize(const std::vector<std::pair<T, T>> &vs) { _ps = vs; _tmp.resize(_ps.size()); for (int i = 0; i < int(vs.size()); ++i) _tmp[i] = std::make_tuple(i, vs[i].first, vs[i].second); _build(0, _tmp.size(), 0, 0); } kd_tree(const std::vector<std::pair<T, T>> &vs) { _initialize(vs); } std::vector<int> get_rect(T xmin, T xmax, T ymin, T ymax) const { // [xmin, xmax] * [ymin, ymax] に含まれる全点取得 std::vector<int> ret; std::vector<int> _stack; if (_nodes.size()) _stack.push_back(0); while (!_stack.empty()) { const Node &now = _nodes[_stack.back()]; _stack.pop_back(); if (xmax < now.xmin or now.xmax < xmin or ymax < now.ymin or now.ymax < ymin) { ; } else if (xmin <= now.xmin and now.xmax <= xmax and ymin <= now.ymin and now.ymax <= ymax) { ret.insert(ret.end(), now.ids.begin(), now.ids.end()); } else { if (now.lch >= 0) _stack.push_back(now.lch); if (now.rch >= 0) _stack.push_back(now.rch); } } return ret; } }; // Mo's algorithm // - add_range(l, r) : Add [l, r) as query. // - run() : run Mo's algorithm. template <class Int, Int INF> class MosAlgorithm { Int nmin, nmax; public: struct Point { Int first, second; int qid; }; std::vector<Point> ranges; MosAlgorithm() : nmin(INF), nmax(-INF) {} void add_range(Int l, Int r, int q) { assert(l <= r); nmin = std::min(nmin, l); nmax = std::max(nmax, r); ranges.push_back(Point{l, r, q}); } std::vector<int> run() { const int Q = ranges.size(); const int nbbucket = std::max(1, std::min<int>(nmax - nmin, sqrt(Q))); const Int szbucket = (nmax - nmin + nbbucket - 1) / nbbucket; std::vector<int> qs(Q); std::iota(qs.begin(), qs.end(), 0); std::sort(qs.begin(), qs.end(), [&](int q1, int q2) { auto b1 = (ranges[q1].first - nmin) / szbucket, b2 = (ranges[q2].first - nmin) / szbucket; if (b1 != b2) return b1 < b2; else { return (b1 & 1) ? (ranges[q1].second > ranges[q2].second) : (ranges[q1].second < ranges[q2].second); } }); return qs; } }; uint32_t rand_int() // XorShift random integer generator { static uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123; uint32_t t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } double rand_double() { return (double)rand_int() / UINT32_MAX; } using Cost = lint; vector<plint> xs; Cost calc_dist(int i, int j) { auto dx = xs.at(j) - xs.at(i); return abs(dx.first) + abs(dx.second); } std::mt19937 mt(100); #include <optional> template <class T> struct SymmetricTSP { int _n; inline T dist(int s, int t) const noexcept { return calc_dist(s, t); } struct Solution { T primal; std::vector<int> path; template <class OStream> friend OStream &operator<<(OStream &os, const Solution &x) { os << "[primal sol=" << x.primal << ", path=("; if (!x.path.empty()) { for (int i : x.path) os << i << ">"; os << x.path.front() << ")]"; } return os; } }; std::vector<std::vector<std::pair<T, int>>> adjacents; void build_adjacent_info(std::vector<std::vector<std::pair<T, int>>> &info_) { adjacents = info_; } SymmetricTSP(int n) : _n(n) {} Solution nearest_neighbor(std::optional<int> init = std::nullopt) const { if (n() == 0) return {T(), {}}; int now = init.value_or(0); std::vector<int> ret{now}, alive(n(), 1); T len = T(); ret.reserve(n()); alive.at(now) = 0; while (int(ret.size()) < n()) { int nxt = -1; for (int i = 0; i < n(); ++i) { if (alive.at(i) and (nxt < 0 or dist(now, i) < dist(now, nxt))) nxt = i; } ret.push_back(nxt); alive.at(nxt) = 0; len += dist(now, nxt); now = nxt; } len += dist(ret.back(), ret.front()); return Solution{len, ret}; } void two_opt(Solution &sol) const { while (true) { bool updated = false; for (int i = 0; i + 1 < n() and !updated; ++i) { int u = sol.path.at(i), nxtu = sol.path.at(i + 1); for (int j = i + 2; j < n(); ++j) { int v = sol.path.at(j), nxtv = sol.path.at(j + 1 < n() ? j + 1 : 0); T diff = dist(u, v) + dist(nxtu, nxtv) - dist(u, nxtu) - dist(v, nxtv); if (diff < 0) { sol.primal += diff; std::reverse(sol.path.begin() + i + 1, sol.path.begin() + j + 1); updated = true; break; } } } if (!updated) break; } } template <class Clock> void two_opt_near(Solution &sol, Clock &START) { // if (adjacents.empty()) build_adjacent_info(20); static std::vector<int> v_to_i; v_to_i.resize(n()); while (true) { int64_t spent_ms = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - START).count(); if (spent_ms > 4700) break; // dbg(sol.primal); for (int i = 0; i < n(); ++i) v_to_i.at(sol.path.at(i)) = i; bool updated = false; for (int i = 0; i < n() and !updated; ++i) { int u = sol.path.at(i), nxtu = sol.path.at(modn(i + 1)); T dunxtu = dist(u, nxtu); for (auto [duv, v] : adjacents.at(u)) { if (v == nxtu) continue; int j = v_to_i.at(v), nxtv = sol.path.at(modn(j + 1)); T diff = duv + dist(nxtu, nxtv) - dunxtu - dist(v, nxtv); if (diff < 0) { sol.primal += diff; if (i < j) { std::reverse(sol.path.begin() + i + 1, sol.path.begin() + j + 1); } else { std::reverse(sol.path.begin() + j + 1, sol.path.begin() + i + 1); } updated = true; break; } } if (updated) break; for (auto [dnxtunxtv, nxtv] : adjacents.at(nxtu)) { if (nxtv == u) continue; int j = modn(v_to_i.at(nxtv) - 1), v = sol.path.at(j); T diff = dist(u, v) + dnxtunxtv - dunxtu - dist(v, nxtv); if (diff < 0) { sol.primal += diff; if (i < j) { std::reverse(sol.path.begin() + i + 1, sol.path.begin() + j + 1); } else { std::reverse(sol.path.begin() + j + 1, sol.path.begin() + i + 1); } updated = true; break; } } } if (!updated) break; } } bool three_opt(Solution &sol, const int max_size = 0) const { for (int s = 1; s < (max_size > 0 ? max_size : n()); ++s) { for (int i = 0; i < n(); ++i) { for (int l = s + 1; l < n(); ++l) { int u = sol.path.at(modn(i - 1)), nxtu = sol.path.at(i); int v = sol.path.at(modn(i + s - 1)), nxtv = sol.path.at(modn(i + s)); int w = sol.path.at(modn(i + l - 1)), nxtw = sol.path.at(modn(i + l)); T current = dist(u, nxtu) + dist(v, nxtv) + dist(w, nxtw); if (T diff = dist(u, nxtv) + dist(w, nxtu) + dist(v, nxtw) - current; diff < T()) { sol.primal += diff; std::rotate(sol.path.begin(), sol.path.begin() + i, sol.path.end()); std::rotate(sol.path.begin(), sol.path.begin() + s, sol.path.begin() + l); return true; } if (T diff = dist(u, w) + dist(nxtv, nxtu) + dist(v, nxtw) - current; diff < T()) { sol.primal += diff; std::rotate(sol.path.begin(), sol.path.begin() + i, sol.path.end()); std::rotate(sol.path.begin(), sol.path.begin() + s, sol.path.begin() + l); std::reverse(sol.path.begin(), sol.path.begin() + (l - s)); return true; } if (T diff = dist(u, nxtv) + dist(w, v) + dist(nxtu, nxtw) - current; diff < T()) { sol.primal += diff; std::rotate(sol.path.begin(), sol.path.begin() + i, sol.path.end()); std::rotate(sol.path.begin(), sol.path.begin() + s, sol.path.begin() + l); std::reverse(sol.path.begin() + (l - s), sol.path.begin() + l); return true; } if (T diff = dist(u, v) + dist(nxtu, w) + dist(nxtv, nxtw) - current; diff < T()) { sol.primal += diff; std::rotate(sol.path.begin(), sol.path.begin() + i, sol.path.end()); std::reverse(sol.path.begin(), sol.path.begin() + s); std::reverse(sol.path.begin() + s, sol.path.begin() + l); return true; } } } } return false; } bool double_bridge(Solution &sol, std::mt19937 &mt) const { if (n() < 8) return false; std::vector<int> &p = sol.path; int rand_rot = std::uniform_int_distribution<int>(0, n() - 1)(mt); std::rotate(p.begin(), p.begin() + rand_rot, p.end()); static std::array<int, 3> arr; for (int &y : arr) y = std::uniform_int_distribution<int>(2, n() - 6)(mt); std::sort(arr.begin(), arr.end()); const int i = arr.at(0), j = arr.at(1) + 2, k = arr.at(2) + 4; static std::array<T, 2> diffs; for (int d = 0; d < 2; ++d) { int u = p.at(n() - 1), nxtu = p.at(0); int v = p.at(i - 1), nxtv = p.at(i); int w = p.at(j - 1), nxtw = p.at(j); int x = p.at(k - 1), nxtx = p.at(k); diffs.at(d) = dist(u, nxtu) + dist(v, nxtv) + dist(w, nxtw) + dist(x, nxtx); if (d == 1) break; std::reverse(p.begin(), p.begin() + i); std::reverse(p.begin() + i, p.begin() + j); std::reverse(p.begin() + j, p.begin() + k); std::reverse(p.begin() + k, p.end()); } sol.primal += diffs.at(1) - diffs.at(0); return true; } int n() const noexcept { return _n; } int modn(int x) const noexcept { if (x < 0) return x + n(); if (x >= n()) return x - n(); return x; } }; Cost eval(const vector<int> &seq) { Cost cost = 0; FOR(i, 1, seq.size()) cost += calc_dist(seq.at(i - 1), seq.at(i)); return cost; } #include <chrono> int main() { auto START = std::chrono::system_clock::now(); int N, Q, WT, ST; cin >> N >> Q >> WT >> ST; vector<lint> W(N); cin >> W; vector<lint> scale(N); FOR(i, 1, N) scale.at(i) = scale.at(i - 1) + W.at(i - 1) + W.at(i); xs.resize(Q); for (auto &[x, y] : xs) { cin >> x >> y; --x, --y; x = scale.at(x), y = scale.at(y); } // dbg(xs); vector<plint> uvs(Q); REP(q, Q) { auto [x, y] = xs.at(q); uvs.at(q) = make_pair(x + y, x - y); } kd_tree<lint> tree(uvs); vector<vector<pair<lint, int>>> neis(Q); constexpr int AS = 4; dbg("KD BUILD"); REP(q, Q) { lint w = 1 << 7; const auto [u, v] = uvs.at(q); vector<int> nei_q; while (nei_q.size() < AS and nei_q.size() < Q) { w *= 2; nei_q = tree.get_rect(u - w, u + w + 1, v - w, v + w + 1); } for (auto i : nei_q) { if (i != q) neis.at(q).emplace_back(calc_dist(q, i), i); } sort(neis.at(q).begin(), neis.at(q).end()); while (neis.at(q).size() > AS) neis.at(q).pop_back(); } dbg("KD BUILD DONE"); MosAlgorithm<lint, 1LL << 60> mo; REP(q, Q) mo.add_range(xs.at(q).first, xs.at(q).second, q); SymmetricTSP<Cost>::Solution sol{Cost(0), mo.run()}; dbg("INIT SOL BUILD"); // dbg(neis); SymmetricTSP<Cost> tsp(Q); tsp.build_adjacent_info(neis); dbg("Solve 2-opt"); dbg(eval(sol.path)); tsp.two_opt_near(sol, START); dbg(eval(sol.path)); for (auto q : sol.path) cout << q + 1 << " "; cout << endl; }