結果
| 問題 | 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;
}