#define CODETEST 0 #define OPTUNE 0 #define PERFORMANCE 0 #define EVAL 0 #define UNIT_TEST 0 #define TIME_LIMIT (2800) #define NOT_SUBMIT 0 #define VALIDATION 0 #define IO_FILE 0 #define OUTPUT_INFO 0 #define OUTPUT_FINAL_INFO 0 #define OUTPUT_LOG 0 #define OUTPUT_VISUAL 0 #define FIX_RESULT 0 #define TIME_LIMIT_US (TIME_LIMIT * 1000) #ifdef __clang_version__ #pragma clang diagnostic ignored "-Wunknown-pragmas" #pragma clang diagnostic ignored "-Wunknown-warning-option" #pragma clang diagnostic ignored "-Wmissing-braces" #endif #ifndef _MSC_VER #pragma GCC target ("avx2") #pragma GCC optimize "O3,omit-frame-pointer,inline" #pragma GCC optimize ("unroll-loops") #pragma GCC diagnostic ignored "-Wunused-parameter" #pragma GCC diagnostic ignored "-Wsign-compare" #pragma GCC diagnostic ignored "-Wunused-variable" #pragma GCC diagnostic ignored "-Wunused-function" #pragma GCC diagnostic ignored "-Wunused-but-set-variable" #endif #define _USE_MATH_DEFINES #ifdef __clang_version__ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #else #include #endif using namespace std; #define FOR(i, s, e) for (int i = int(s); i < int(e); ++i) #define RFOR(i, s, e) for (int i = int(e) - 1; i >= int(s); --i) #define REP(i, n) for (int i = 0, i##_size = int(n); i < i##_size; ++i) #define RREP(i, n) for (int i = int(n) - 1; i >= 0; --i) #define ALL(x) (x).begin(),(x).end() template inline void chmin(T& a, U&& b) { if (b < a) { a = b; } } template inline void chmax(T& a, U&& b) { if (a < b) { a = b; } } template inline void clip(T& v, U&& lower, V&& upper) { if (v < lower) { v = lower; } else if (v > upper) { v = upper; } } template inline constexpr T square(T v) { return v * v; } template constexpr int len(const T(&)[SIZE]) { return SIZE; } #define cauto const auto #include using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; using s8 = int8_t; using s16 = int16_t; using s32 = int32_t; using s64 = int64_t; using TimePoint = chrono::high_resolution_clock::time_point; struct ChronoTimer { private: TimePoint startTime_; TimePoint endTime_; public: inline void Init() { startTime_ = chrono::high_resolution_clock::now(); endTime_ = startTime_; } inline void Start(int limit) { endTime_ = startTime_ + chrono::milliseconds(limit); } inline void StartMs(int limit) { endTime_ = startTime_ + chrono::milliseconds(limit); } inline void StartUs(int limit) { endTime_ = startTime_ + chrono::microseconds(limit); } inline void Join() { } inline bool IsOver() const { return chrono::high_resolution_clock::now() >= endTime_; } inline int ElapseTimeMs() const { return (int)chrono::duration_cast(chrono::high_resolution_clock::now() - startTime_).count(); } inline int ElapseTimeUs() const { return (int)chrono::duration_cast(chrono::high_resolution_clock::now() - startTime_).count(); } void SetElapseTimeMs(int ms) { auto now = chrono::high_resolution_clock::now(); auto limit = endTime_ - startTime_; startTime_ = now - chrono::milliseconds(ms); endTime_ = startTime_ + limit; } inline int LeftToUS(const TimePoint& limit) const { return (int)chrono::duration_cast(limit - chrono::high_resolution_clock::now()).count(); } inline double NowRate() const { return (chrono::high_resolution_clock::now() - startTime_).count() / (double)(endTime_ - startTime_).count(); } inline TimePoint Now() const { return chrono::high_resolution_clock::now(); } inline TimePoint StartTime() const { return startTime_; } inline TimePoint EndTime() const { return endTime_; } TimePoint GetLimitTimePointUs(int limit) const { return startTime_ + chrono::microseconds(limit); } }; TimePoint Now() { return chrono::high_resolution_clock::now(); } template void InstanceRun(int argc, const char* argv[]) { T* m = new T; m->Run(argc, argv); quick_exit(0); } struct Main; signed main(int argc, const char* argv[]) { cin.tie(0); ios::sync_with_stdio(0); InstanceRun
(argc, argv); } struct MemoryException {}; #define VALIDATE_ABORT() #define VALIDATE_ASSERT(exp) #define VABORT() VALIDATE_ABORT() #define VASSERT(exp) VALIDATE_ASSERT(exp) template struct pr { union { A a; A x; A first; }; union { B b; B y; B second; }; bool operator == (pr const& r) const { return a == r.a && b == r.b; } bool operator != (pr const& r) const { return !((*this) == r); } bool operator < (pr const& r) const { if (a == r.a) { return b < r.b; } return a < r.a; } bool operator > (pr const& r) const { return r < (*this); } pr& operator += (pr const& v) { a += v.a; b += v.b; return *this; } pr& operator -= (pr const& v) { a -= v.a; b -= v.b; return *this; } template auto operator + (pr const& v) const { return pr{ a + v.a, b + v.b }; } template auto operator - (pr const& v) const { return pr{ a - v.a, b - v.b }; } template explicit operator pr() const { return { C(a), D(b) }; } template auto operator * (T const& v) const -> pr { return { x * v, y * v }; } template auto operator / (T const& v) const -> pr { return { x / v, y / v }; } template pr& operator *= (T const& v) { x *= v; y *= v; return *this; } template pr& operator /= (T const& v) { x /= v; y /= v; return *this; } pr operator -() const { return pr{ -x, -y }; } void flip() { swap(x, y); } friend istream& operator>>(istream& is, pr& p) { is >> p.a >> p.b; return is; } friend ostream& operator<<(ostream& os, pr const& p) { os << p.a << " " << p.b; return os; } template auto get() const { if constexpr (I == 0) { return x; } else if constexpr (I == 1) { return y; } } }; using pint = pr; using pdouble = pr; static_assert(is_trivially_copyable::value, "not trivially_copyable"); template struct tuple_size> : integral_constant {}; template struct tuple_element<0, pr> { using type = A; }; template struct tuple_element<1, pr> { using type = B; }; inline pdouble ToDouble(const pint& p) { return pdouble{ double(p.x), double(p.y) }; } inline pint round(const pdouble& d) { return pint{ (int)round(d.x), (int)round(d.y) }; } inline double norm(const pdouble& d) { return sqrt((d.x * d.x) + (d.y * d.y)); } inline double norm(const pint& d) { return norm(ToDouble(d)); } inline int norm2(const pint& d) { return square(d.x) + square(d.y); } inline pdouble normalized(const pdouble& d) { return d / norm(d); } inline double dot(const pdouble& a, const pdouble& b) { return a.x * b.x + a.y * b.y; } inline double cross(const pdouble& a, const pdouble& b) { return a.x * b.y - a.y * b.x; } template class CapArr { private: friend class CapArr; static_assert(is_trivially_copyable::value); T array_[CAP]; int size_ = 0; public: bool operator == (const CapArr& r) const { if (size_ != r.size_) { return false; } REP(i, size_) { if (!(array_[i] == r.array_[i])) { return false; } } return true; } template bool operator != (const CapArr& r) const { return !(*this == r); } bool MemEqual(const CapArr& r) const { if (size_ != r.size_) { return false; } return memcmp(data(), r.data(), sizeof(T) * size_) == 0; } constexpr int capacity() const { return CAP; } int size() const { return size_; } bool empty() const { return size_ == 0; } void clear() { size_ = 0; } void resize(int size) { size_ = size; } void assign(int size, const T& e) { size_ = size; if constexpr (sizeof(T) == 1) { if constexpr (is_enum::value) { memset(data(), underlying_type::type(e), size); } else { memset(data(), *reinterpret_cast(&e), size); } } else { for (int i = 0; i < size; ++i) { array_[i] = e; } } } void AssignIota(int size) { resize(size); iota(begin(), end(), 0); } void Iota(int size) { resize(size); iota(begin(), end(), 0); } void MemAssign(int size, int byte) { size_ = size; memset(data(), byte, sizeof(T) * size); } void MemCopy(const CapArr& from) { size_ = from.size_; memcpy(data(), from.data(), sizeof(T) * from.size_); } const T* data() const { return &array_[0]; } T* data() { return &array_[0]; } T& front() { return array_[0]; } const T& front() const { return array_[0]; } T& back() { return array_[size_ - 1]; } const T& back() const { return array_[size_ - 1]; } T& operator[](int index) { return array_[index]; } const T& operator[](int index) const { return array_[index]; } T* begin() { return &array_[0]; } T* end() { return &array_[size_]; } const T* begin() const { return &array_[0]; } const T* end() const { return &array_[size_]; } [[nodiscard]] T& push() { auto& ref = array_[size_]; ++size_; return ref; } void push(const T& e) { array_[size_] = e; ++size_; } void pop() { --size_; } int find(const T& value) const { REP(i, size_) { if (array_[i] == value) { return i; } } return -1; } bool contains(const T& value) const { for (const auto& v : *this) { if (v == value) { return true; } } return false; } void insert(int index, const T& value) { insert(index, &value, 1); } void insert(int index, const T* mem, int size) { if (index == size_) { memcpy(data() + index, mem, sizeof(T) * size); size_ += size; } else { memmove(data() + index + size, data() + index, sizeof(T) * (size_ - index)); memcpy(data() + index, mem, sizeof(T) * size); size_ += size; } } template void append(const CapArr& r) { insert(size(), r.data(), r.size()); } void remove(int index) { remove(index, index + 1); } void remove(int start, int end) { int size = end - start; memmove(data() + start, data() + end, sizeof(T) * (size_ - end)); size_ -= size; } void RemoveSwap(int index) { array_[index] = array_[size_ - 1]; --size_; } void RemoveInsert(int start, int end, const T* p, int size) { int newEnd = start + size; if (size_ - end > 0 && newEnd != end) { memmove(data() + newEnd, data() + end, sizeof(T) * (size_ - end)); } memcpy(data() + start, p, sizeof(T) * size); size_ -= end - start; size_ += size; } void stable_sort() { ::stable_sort(begin(), end()); } template void stable_sort(LESS&& less) { ::stable_sort(begin(), end(), less); } void reverse() { ::reverse(begin(), end()); } }; template struct CapacityQueue { private: array ar_ = {}; int start_ = 0; int end_ = 0; public: inline void clear() { start_ = 0; end_ = 0; } inline void push(const T& v) { ar_[end_] = v; ++end_; } inline T* push() { T* ptr = &ar_[end_]; ++end_; return ptr; } inline const T& get() const { return ar_[start_]; } inline T pop() { return ar_[start_++]; } inline bool empty() const { return start_ == end_; } inline bool exist() const { return start_ != end_; } inline int size() const { return end_ - start_; } inline int total_push_count() const { return end_; } const T& operator[](int i) const{ return ar_[i]; } int end_size() const { return end_; } int direct_start() const { return start_; } int direct_end() const { return end_; } inline auto begin() -> decltype(ar_.begin()) { return ar_.begin() + start_; } inline auto end() -> decltype(ar_.begin()) { return ar_.begin() + end_; } inline auto begin() const -> decltype(ar_.begin()) { return ar_.begin() + start_; } inline auto end() const -> decltype(ar_.begin()) { return ar_.begin() + end_; } const T& front() const { return ar_[start_]; } const T& back() const { return ar_[end_ - 1]; } }; template using CapQue = CapacityQueue; template struct CheckMapS { private: array checked_ = {}; u32 mark_ = 1; public: void Clear() { ++mark_; if (mark_ == 0) { checked_ = {}; ++mark_; } } bool IsChecked(int i) const { return checked_[i] == mark_; } void Check(int i) { checked_[i] = mark_; } void Reset(int i) { checked_[i] = mark_ - 1; } bool operator[](int i) const { return checked_[i] == mark_; } bool operator == (const CheckMapS& r) const { REP(i, S) { if (this->IsChecked(i) != r.IsChecked(i)) { return false; } } return true; } }; template struct CheckMapDataS { private: array data_; array checked_ = {}; u32 mark_ = 1; public: void Clear() { ++mark_; if (mark_ == 0) { checked_ = {}; ++mark_; } } bool IsChecked(int i) const { return checked_[i] == mark_; } void Check(int i) { checked_[i] = mark_; } void Set(int i, const T& value) { checked_[i] = mark_; data_[i] = value; } void Reset(int i) { checked_[i] = mark_ - 1; } const T& Get(int i) const { VASSERT(checked_[i] == mark_); return data_[i]; } T& Ref(int i) { VASSERT(checked_[i] == mark_); return data_[i]; } const T& Ref(int i) const { VASSERT(checked_[i] == mark_); return data_[i]; } T& operator[](int i) { VASSERT(checked_[i] == mark_); return data_[i]; } const T& operator[](int i) const { VASSERT(checked_[i] == mark_); return data_[i]; } T GetIf(int i, const T& defaultValue) const { if (checked_[i] == mark_) { return data_[i]; } return defaultValue; } }; template struct CapacitySet { private: CapArr elemens; CheckMapDataS indexTable; public: CapacitySet() { } bool operator == (const CapacitySet& r) const { if (elemens.size() != r.elemens.size()) { return false; } for (int i : elemens) { if (!r.IsContain(i)) { return false; } } return true; } constexpr int capacity() { return CAP; } void Fill() { indexTable.Clear(); elemens.resize(CAP); iota(ALL(elemens), 0); REP(i, CAP) { indexTable.Set(i, i); } } void Clear() { elemens.clear(); indexTable.Clear(); } void Add(T ai) { indexTable.Set(ai, elemens.size()); elemens.push(ai); } void ForceAdd(T ai) { if (indexTable.IsChecked(ai)) { return; } indexTable.Set(ai, elemens.size()); elemens.push(ai); } void Remove(int ai) { T removeIndex = indexTable[ai]; T lastIndex = elemens.size() - 1; if (removeIndex != lastIndex) { elemens[removeIndex] = elemens[lastIndex]; indexTable.Set(elemens[lastIndex], removeIndex); } elemens.pop(); indexTable.Reset(ai); } void ForceRemove(T ai) { if (!indexTable.IsChecked(ai)) { return; } T removeIndex = indexTable[ai]; T lastIndex = elemens.size() - 1; if (removeIndex != lastIndex) { elemens[removeIndex] = elemens[lastIndex]; indexTable.Set(elemens[lastIndex], removeIndex); } elemens.pop(); indexTable.Reset(ai); } bool contains(T i) const { return indexTable.IsChecked(i); } bool IsContain(T i) const { return contains(i); } int size() const { return elemens.size(); } bool empty() const { return elemens.empty(); } T At(int index) const { return elemens[index]; } T operator[](int index) const { return elemens[index]; } auto begin() -> decltype(elemens.begin()) { return elemens.begin(); } auto end() -> decltype(elemens.begin()) { return elemens.end(); } auto begin() const -> decltype(elemens.begin()) { return elemens.begin(); } auto end() const -> decltype(elemens.begin()) { return elemens.end(); } }; template using CapSet = CapacitySet; template struct CapacityMap { private: CapArr, CAP> elemens; CheckMapDataS indexTable; public: CapacityMap() { indexTable.Clear(); } void Clear() { elemens.clear(); indexTable.Clear(); } inline void Add(int i, const T& value) { indexTable.Set(i, elemens.size()); elemens.push({ i, value }); } inline void ForceAdd(int i, const T& value) { if (indexTable.IsChecked(i)) { return; } indexTable.Set(i, elemens.size()); elemens.push({ i, value }); } inline void Remove(int i) { int removeIndex = indexTable[i]; int lastIndex = elemens.GetCount() - 1; if (removeIndex != lastIndex) { elemens[removeIndex] = elemens[lastIndex]; indexTable[elemens[lastIndex].a] = removeIndex; } elemens.pop(); indexTable.Reset(i); } inline void ForceRemove(int i) { if (!indexTable.IsChecked(i)) { return; } int removeIndex = indexTable[i]; int lastIndex = elemens.size() - 1; if (removeIndex != lastIndex) { elemens[removeIndex] = elemens[lastIndex]; indexTable[elemens[lastIndex].a] = removeIndex; } elemens.pop(); indexTable.Reset(i); } inline bool IsContain(int i) const { return indexTable.IsChecked(i); } inline int GetCount() const { return elemens.size(); } inline auto begin() -> decltype(elemens.begin()) { return elemens.begin(); } inline auto end() -> decltype(elemens.begin()) { return elemens.end(); } inline auto begin() const -> decltype(elemens.begin()) { return elemens.begin(); } inline auto end() const -> decltype(elemens.begin()) { return elemens.end(); } }; template using CapMap = struct CapacityMap; template struct CapPriorityQueue { CapArr buf_; void clear() { buf_.clear(); } bool empty() const { return buf_.empty(); } bool exist() const { return !buf_.empty(); } const T& top() { return buf_.front(); } template void push(const T& v, CMP&& cmp) { buf_.push(v); push_heap(ALL(buf_), cmp); } template T pop(CMP&& cmp) { pop_heap(ALL(buf_), cmp); T ret = buf_.back(); buf_.pop(); return ret; } void PushNoHeap(const T& v) { buf_.push(v); } void MakeHeap() { make_heap(ALL(buf_)); } }; template void Shuffle(IT&& begin, IT&& end, RAND&& rand) { int size = int(end - begin); if (size <= 1) { return; } REP(i, size - 1) { int j = i + rand() % (size - i); swap(*(begin + i), *(begin + j)); } } #include struct Xor64 { using result_type = uint64_t; static constexpr result_type min() { return 0; } static constexpr result_type max() { return UINT64_MAX; } private: Xor64(const Xor64& r) = delete; Xor64& operator =(const Xor64& r) = delete; public: uint64_t x; inline Xor64(uint64_t seed = 0) { x = 88172645463325252ULL + seed; } inline uint64_t operator()() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline uint64_t operator()(uint64_t l, uint64_t r) { return ((*this)() % (r - l)) + l; } template inline T operator()(T r) { return (*this)() % r; } inline double GetDouble() { return (*this)() / (double)UINT64_MAX; } inline bool GetProb(double E) { return GetDouble() <= E; } }; enum class Dir : int8_t { L = 0, U, R, D, N, Invalid, }; constexpr array Dir4 = { Dir::L, Dir::U, Dir::R, Dir::D, }; constexpr array Around4 = { pint{-1, 0}, pint{0, -1}, pint{1, 0}, pint{0, 1} }; constexpr array Around5 = { pint{-1, 0}, pint{0, -1}, pint{1, 0}, pint{0, 1}, pint{0, 0} }; inline Dir RotateRight(Dir d) { constexpr Dir nexts[4] = { Dir::U, Dir::R, Dir::D, Dir::L, }; return nexts[(int8_t)d]; } inline Dir RotateLeft(Dir d) { constexpr Dir nexts[4] = { Dir::D, Dir::L, Dir::U, Dir::R, }; return nexts[(int8_t)d]; } inline Dir Back(Dir d) { return Dir(s8(d) ^ 2); } bool IsHorizontal(Dir dir) { return dir == Dir::L || dir == Dir::R; } bool IsVertical(Dir dir) { return dir == Dir::U || dir == Dir::D; } inline Dir CalcDir(const pint& from, const pint& to) { if (from.x > to.x) { return Dir::L; } else if (from.y > to.y) { return Dir::U; } else if (from.x < to.x) { return Dir::R; } else if (from.y < to.y) { return Dir::D; } else { return Dir::N; } } inline const string& DirString(Dir dir) { static const string strs[6] = { "LEFT", "UP", "RIGHT", "DOWN", "WAIT", "INVALID", }; return strs[(int)dir]; } inline char DirToChar(Dir dir) { static const char chars[6] = { 'L', 'U', 'R', 'D', 'N', '*', }; return chars[(int)dir]; } inline Dir CharToDir(char c) { if (c == 'L') { return Dir::L; } else if (c == 'U') { return Dir::U; } else if (c == 'R') { return Dir::R; } else if (c == 'D') { return Dir::D; } else if (c == 'N') { return Dir::N; } VABORT(); return Dir::Invalid; } template struct GridSystemS { inline constexpr int ToId(int x, int y) const { return x + W * y; } inline constexpr int ToId(const pint& p) const { return p.x + W * p.y; } inline constexpr pint ToPos(int id) const { return pint{ id % W, id / W }; } inline int CalcL1Dist(const pint& a, const pint& b) const { return abs(a.x - b.x) + abs(a.y - b.y); } inline int CalcL1Dist(int a, int b) const { return CalcL1Dist(ToPos(a), ToPos(b)); } inline int CalcL2Dist2(const pint& a, const pint& b) const { return square(a.x - b.x) + square(a.y - b.y); } inline int CalcL2Dist2(int a, int b) const { return CalcL2Dist2(ToPos(a), ToPos(b)); } inline double CalcL2Dist(const pint& a, const pint& b) const { return sqrt(CalcL2Dist2(a, b)); } inline double CalcL2Dist(int a, int b) const { return CalcL2Dist(ToPos(a), ToPos(b)); } inline bool IsOut(int x, int y) const { if (x < 0 || x >= W || y < 0 || y >= H) { return true; } return false; } inline bool IsOut(const pint& p) const { return IsOut(p.x, p.y); } inline bool IsIn(const pint& p) const { return !IsOut(p); } inline int RotateRight90(int id) const { pint p = ToPos(id); return ToId(W - 1 - p.y, p.x); } inline Dir CalcDir(int from, int to) const { if (from - 1 == to) { return Dir::L; } else if (from - W == to) { return Dir::U; } else if (from + 1 == to) { return Dir::R; } else if (from + W == to) { return Dir::D; } else if (from == to) { return Dir::N; } else { VABORT(); } return Dir::Invalid; } }; template struct CCA { private: T ar[CAP]; int s; public: inline constexpr void push(const T& v) { ar[s++] = v; } inline constexpr void pop() { --s; } inline constexpr const T* begin() const { return &ar[0]; } inline constexpr const T* end() const { return &ar[s]; } inline constexpr const T& operator ()(int i) const { VASSERT(i >= 0 && i < CAP); return ar[i]; } inline constexpr const T& operator [](int i) const { VASSERT(i >= 0 && i < CAP); return ar[i]; } inline constexpr int size() const { return s; } }; template struct AroundMapS { using CA = CCA; CA table[W * H]; constexpr AroundMapS(const array& aroundDirs) : table{} { REP(cellId, W * H) { pint p = { cellId % W, cellId / W }; for (const pint& a : aroundDirs) { int x = p.a + a.a; int y = p.b + a.b; if (x >= 0 && x < W && y >= 0 && y < H) { table[cellId].push(x + y * W); } } } } inline constexpr const CA& operator ()(int id) const { return table[id]; } inline constexpr const CA& operator [](int id) const { return table[id]; } }; template struct DirMapS { using CA = CCA; CA table[W * H]; constexpr DirMapS(const array& aroundDirs) : table{} { REP(cellId, W * H) { pint p = { cellId % W, cellId / W }; for (const pint& a : aroundDirs) { int x = p.a + a.a; int y = p.b + a.b; int n = -1; if (x >= 0 && x < W && y >= 0 && y < H) { n = x + y * W; } table[cellId].push(n); } } } inline constexpr const CA& operator ()(int id) const { return table[id]; } inline constexpr const CA& operator [](int id) const { return table[id]; } }; template struct JointAroundMapS { using CA = CCA; CA table[W * H]; constexpr JointAroundMapS() : table{} { REP(cellId, W * H) { pint p = { cellId % W, cellId / W }; FOR(oy, -1, 2) { FOR(ox, -1, 2) { if (oy == 0 && ox == 0) { continue; } int x = p.a + ox; int y = p.b + oy; int n = -1; if (x >= 0 && x < W && y >= 0 && y < H) { n = x + y * W; } table[cellId].push(n); } } } } inline constexpr const CA& operator ()(int id) const { return table[id]; } inline constexpr const CA& operator [](int id) const { return table[id]; } }; constexpr GridSystemS<50, 50> gs; constexpr AroundMapS<50, 50, 4> aroundMap(Around4); constexpr DirMapS<50, 50, 4> dirMap(Around4); constexpr int N = 50; constexpr int M = 20; constexpr int NN = N*N; constexpr int NNM = NN * M; constexpr int FireRange = 20; constexpr int TurnMax = 2000; template using NArr = CapArr; template using NNArr = CapArr; template using MArr = CapArr; template using NNMArr = CapArr; template using NQue = CapQue; template using NNQue = CapQue; template using MQue = CapQue; template using NNMQue = CapQue; template using NSet = CapSet; template using NNSet = CapSet; template using MSet = CapSet; template using NNMSet = CapSet; struct Bomb { int cost_; NNArr ps_; NNArr flags_; bool CanBomb(const pint& p) const { int x = p.x + FireRange; int y = p.y + FireRange; if (gs.IsOut(x, y)) { return false; } return flags_[gs.ToId(x, y)]; } bool CanBomb(int putPos, int targetPos) const { auto relPos = gs.ToPos(targetPos) - gs.ToPos(putPos); return CanBomb(relPos); } }; struct Input { NNArr grid_; MArr bombs_; NNArr shops_; int buildingCount_; bool IsShop(int p) const { return grid_[p] == '@'; } bool IsBuilding(int p) const { return grid_[p] == '#'; } bool IsBlank(int p) const { return grid_[p] == '.'; } }; Input input_; #define PARAM_CATEGORY(NAME, VALUE, ...) int NAME = VALUE; #define PARAM_INT(NAME, VALUE, LOWER_VALUE, UPPER_VALUE) int NAME = VALUE; #define PARAM_DOUBLE(NAME, VALUE, LOWER_VALUE, UPPER_VALUE) double NAME = VALUE; #define PARAM_LOWER(v) #define PARAM_UPPER(v) #define START_TUNING #define END_TUNING #define PARAM_GROUP(NAME) #define PARAM_GROUP_END template struct InputParam { T minValue_; T maxValue_; T value_; InputParam(T minValue, T maxValue) { minValue_ = minValue; maxValue_ = maxValue; } void SetValue(T value) { value_ = value; } double GetRate(double strong) const { double r = (value_ - minValue_) / (double)(maxValue_ - minValue_) * 2.0 - 1.0; return r * strong; } }; static double BlendDoubleParam(double baseValue, double minValue, double maxValue, initializer_list rates) { double totalRate = 1; for (double rate : rates) { totalRate += rate; } double value = baseValue * totalRate; chmax(value, minValue); chmin(value, maxValue); return value; } static int BlendIntParam(double baseValue, int minValue, int maxValue, initializer_list rates) { double totalRate = 1; for (double rate : rates) { totalRate += rate; } int value = (int)round(baseValue * totalRate); chmax(value, minValue); chmin(value, maxValue); return value; } constexpr struct { START_TUNING; PARAM_DOUBLE(StartTemp, 35.185535922802856, 30, 40);PARAM_LOWER(0.0); PARAM_DOUBLE(EndTemp, 9.145687668837047, 5.0, 15.0);PARAM_LOWER(0.0); PARAM_INT(RemoveCountMin, 8, 5, 11);PARAM_LOWER(1); PARAM_INT(RemoveCountRange, 10, 7, 13);PARAM_LOWER(1); PARAM_INT(CutOtherShopDist, 3, 0, 6);PARAM_LOWER(0); PARAM_DOUBLE(ShopDistRate, 0.12789448608513482, 0.05, 0.2); PARAM_DOUBLE(LastShopDistRate, 0.5, -0.1, 1.0); END_TUNING; } HP; enum class CommandType : s8 { Empty = 0, Move = 1, Buy = 2, Fire = 3, }; struct IOCommand { CommandType type_; s8 value_; void SetMove(Dir dir) { type_ = CommandType::Move; value_ = (s8)dir; } void SetBuy(s8 bi) { type_ = CommandType::Buy; value_ = bi; } void SetFire(s8 bi) { type_ = CommandType::Fire; value_ = bi; } void SetEmpty() { type_ = CommandType::Empty; value_ = -1; } void Output(ostream& os) const { if (type_ == CommandType::Move) { os << (int)type_ << " " << DirToChar(Dir(value_)) << endl; } else { os << (int)type_ << " " << (int)value_ + 1 << endl; } } }; struct IOResult { CapArr commands_; IOCommand& push() { return commands_.push(); } void Output(ostream& os) const { os << commands_.size() << endl; REP(i, commands_.size()) { commands_[i].Output(os); } } }; struct PutPoint { int p_; int bi_; }; struct TargetSystem { PutPoint putPoints_[NNM]; constexpr TargetSystem() : putPoints_ {} { REP(p, NN) { REP(bi, M) { auto& pp = putPoints_[p * M + bi]; pp.p_ = p; pp.bi_ = bi; } } } int ToId(int p, int bi) const { return p * M + bi; } int ToId(const PutPoint& pp) const { return pp.p_ * M + pp.bi_; } const PutPoint& ToPP(int tid) const { VASSERT(tid >= 0 && tid < NNM); return putPoints_[tid]; } }; constexpr TargetSystem ts; struct FireMap { using CA = CapArr; array table; void Init() { REP(p, NN) { REP(bi, M) { int tid = ts.ToId(p, bi); for (int op : input_.bombs_[bi].ps_) { pint pos = gs.ToPos(op); pos.x -= FireRange; pos.y -= FireRange; pos += gs.ToPos(p); if (gs.IsOut(pos)) { continue; } int id = gs.ToId(pos); if (input_.IsBlank(id)) { continue; } table[tid].push(id); } } } } inline const CA& operator [](int tid) const { return table[tid]; } }; constexpr int FireMapSize = sizeof(FireMap); struct FromFireMap { using CA = CapArr; array table; void Init() { REP(p, NN) { if (input_.IsBlank(p)) { continue; } REP(bi, M) { for (int op : input_.bombs_[bi].ps_) { pint pos = gs.ToPos(op); pos.x -= FireRange; pos.y -= FireRange; pos = -pos; pos += gs.ToPos(p); if (gs.IsOut(pos)) { continue; } int tid = ts.ToId(gs.ToId(pos), bi); table[p].push(tid); } } } } inline const CA& operator [](int p) const { return table[p]; } }; constexpr int FromFireMapSize = sizeof(FromFireMap); FireMap fireMap; FromFireMap fromFireMap; struct IOServer { void InitInput(ChronoTimer& timer) { istream& is = cin; int dummy; is >> dummy >> dummy; timer.Init(); input_.buildingCount_ = 0; auto& grid = input_.grid_; grid.resize(NN); REP(i, NN) { is >> grid[i]; if (grid[i] == '@') { input_.shops_.push(i); } if (grid[i] == '#') { ++input_.buildingCount_; } } auto& bombs = input_.bombs_; bombs.resize(M); REP(i, M) { auto& bomb = bombs[i]; is >> bomb.cost_; int L; is >> L; bomb.ps_.resize(L); bomb.flags_.assign(NN, false); REP(j, L) { int a, b; is >> a >> b; a += FireRange; b += FireRange; int id = gs.ToId(b, a); bomb.ps_[j] = id; bomb.flags_[id] = true; } } fireMap.Init(); fromFireMap.Init(); } void Output(const IOResult& result) { ostream& os = cout; result.Output(os); } void Finalize() { } }; IOServer server; #define USE_SA_POINT_FILTER 0 #define USE_SA_ROLLBACK 0 #define USE_ACCEPT_SCORE 1 constexpr int InitialStateCount = 1; struct RandomTable { vector table_; void push(int value, int count) { table_.reserve(table_.size() + count); REP(i, count) { table_.emplace_back(value); } } template int operator()(ENGINE& engine) { return table_[engine() % table_.size()]; } }; struct SAChecker { Xor64* rand_ = nullptr; double* totalMaxScore_ = nullptr; double temp = 0; double divTemp = 0; double currentScore = 0; double maxScore = 0; int noMaxUpdateCount = 0; int nextRollbackCheckCount = INT_MAX; inline bool operator()(double newScore, bool forceUpdate = false) { ++noMaxUpdateCount; if (newScore > currentScore) { currentScore = newScore; if (newScore > maxScore) { maxScore = newScore; noMaxUpdateCount = 0; if (newScore > *totalMaxScore_) { *totalMaxScore_ = newScore; } } return true; } else if (newScore == currentScore) { return true; } else { if (forceUpdate || exp((newScore - currentScore) * divTemp) * UINT32_MAX > (*rand_)(UINT32_MAX)) { currentScore = newScore; return true; } else { return false; } } } double AcceptScore() { static_assert(numeric_limits::is_iec559); return currentScore + temp * log(rand_->GetDouble()); } void SetRevert() { ++noMaxUpdateCount; } }; template struct SATransition { const char* name; F func; int weight; }; template auto MakeTransition(const char* name, F&& func, int weight) { return SATransition{ name, func, weight }; } #define MAKE_TRANS(func, weight) MakeTransition(#func, [&](SAChecker& sac, State& state) { func(sa, sac, state); }, weight) struct SimulatedAnnealing { vector checkers; double totalMaxScore = 0; double timeRate = 0; double temp = 0; double divTemp = 0; Xor64 rand_; double startTemp_ = 200; double endTemp_ = 1; int stepLoopCount = 1000; double rollbackStartRate_ = 999.0; int rollbackCount_ = INT_MAX; double rollbackNextMulti_ = 1.1; int minRollbackCount_ = 1; public: template void Run2(ChronoTimer& timer, vector& states, tuple...>& transitions) { checkers.resize(states.size()); totalMaxScore = states[0].EvalScore(); REP(pi, checkers.size()) { auto& checker = checkers[pi]; checker.rand_ = &rand_; checker.totalMaxScore_ = &totalMaxScore; checker.temp = 0; checker.divTemp = 0; checker.currentScore = states[pi].EvalScore(); checker.maxScore = checker.currentScore; checker.noMaxUpdateCount = 0; checker.nextRollbackCheckCount = rollbackCount_; chmax(totalMaxScore, checker.maxScore); } RandomTable randTable; TupleLoop(transitions, [&](auto&& e, size_t i) { randTable.push((int)i, e.weight); }); const auto startTime = timer.Now(); const auto endTime = timer.EndTime(); const double subTimeCountDiv = 1.0 / (double)(endTime - startTime).count(); vector pis(states.size()); iota(ALL(pis), 0); bool forceEnd = false; while (!timer.IsOver()) { timeRate = (timer.Now() - startTime).count() * subTimeCountDiv; temp = startTemp_ * std::pow(endTemp_ / startTemp_, timeRate); divTemp = 1.0 / temp; for (auto& checker : checkers) { checker.temp = temp; checker.divTemp = divTemp; } for (int rp = 0; rp < stepLoopCount; ++rp) { int ti = (int)randTable(rand_); auto exec = [&](auto&& e, size_t i) { for (int pi : pis) { auto& checker = checkers[pi]; e.func(checker, states[pi]); } }; TupleAccess(transitions, ti, exec); } if (forceEnd) { break; } } } void ForceUpdate() { } private: template void TupleLoop(Tuple & t, Func && f) { TupleLoop2(t, forward(f), make_index_sequence::value>{}); } template void TupleLoop2(Tuple & t, Func && f, index_sequence) { using swallow = int[]; (void)swallow { (TupleLoop3(t, f), 0)... }; } template void TupleLoop3(Tuple & t, Func & f) { f(get(t), Index); } template void TupleAccess(Tuple & t, int i, Func && f) { TupleAccess2(t, i, forward(f), make_index_sequence::value>{}); } template void TupleAccess2(Tuple & t, int i, Func && f, index_sequence) { using swallow = int[]; (void)swallow { (TupleAccess3(t, i, f), 0)... }; } template void TupleAccess3(Tuple & t, int i, Func & f) { if (i == Index) { f(get(t), Index); } } }; Xor64 rand_; struct ShopMap { NNArr dist_; NNArr nearSi_; void Init(const NNArr& orderdSis) { dist_.resize(NN); nearSi_.resize(NN); REP(p, NN) { int nearD = INT_MAX; int nearSi = -1; RREP(sii, orderdSis.size()) { int si = orderdSis[sii]; int shop = input_.shops_[si]; int d = gs.CalcL1Dist(p, shop); if (d < nearD) { nearD = d; nearSi = si; } } dist_[p] = nearD; nearSi_[p] = nearSi; } } }; struct Backup { NNMArr breakableCount_; NNMSet breakableTids_; NNMSet tids_; NNArr firedCount_; }; static constexpr int BackupSize = sizeof(Backup); struct PlanState { NNArr orderdSis_; ShopMap shopMap_; NNMArr breakableCount_; NNMSet breakableTids_; NNMSet tids_; NNArr firedCount_; void Save(Backup& backup) { backup.breakableCount_ = breakableCount_; backup.breakableTids_ = breakableTids_; backup.tids_ = tids_; backup.firedCount_ = firedCount_; } void Restore(const Backup& backup) { breakableCount_ = backup.breakableCount_; breakableTids_ = backup.breakableTids_; tids_ = backup.tids_; firedCount_ = backup.firedCount_; } void Init() { orderdSis_.clear(); orderdSis_.Iota(input_.shops_.size()); breakableCount_.assign(NNM, 0); breakableTids_.Clear(); REP(i, NN) { if (!input_.IsBlank(i)) { UpdateRefCountWithBuild(i); } } tids_.Clear(); firedCount_.assign(NN, 0); } bool IsEnd() const { return breakableTids_.empty(); } void Put(int tid) { tids_.Add(tid); for (int id : fireMap[tid]) { VASSERT(!input_.IsBlank(id)); if (firedCount_[id] == 0) { UpdateRefCountWithBreak(id); } ++firedCount_[id]; } } void Remove(int tid) { for (int id : fireMap[tid]) { VASSERT(!input_.IsBlank(id)); --firedCount_[id]; if (firedCount_[id] == 0) { UpdateRefCountWithBuild(id); } } tids_.Remove(tid); } void UpdateRefCountWithBreak(int p) { VASSERT(!input_.IsBlank(p)); for (int tid : fromFireMap[p]) { --breakableCount_[tid]; VASSERT(breakableCount_[tid] >= 0); if (breakableCount_[tid] == 0) { breakableTids_.Remove(tid); } } } void UpdateRefCountWithBuild(int p) { VASSERT(!input_.IsBlank(p)); for (int tid : fromFireMap[p]) { if (breakableCount_[tid] == 0) { breakableTids_.Add(tid); } ++breakableCount_[tid]; } } void RemoveUnnecessary() { auto IsRequire = [&](int tid) { cauto& pp = ts.ToPP(tid); for (int id : fireMap[tid]) { VASSERT(!input_.IsBlank(id)); if (firedCount_[id] == 1) { return true; } } return false; }; static NNMArr notRequires; notRequires.clear(); for (int tid : tids_) { if (!IsRequire(tid)) { notRequires.push(tid); } } Shuffle(ALL(notRequires), rand_); while (true) { bool updated = false; for (int tid : notRequires) { if (tids_.IsContain(tid)) { if (!IsRequire(tid)) { Remove(tid); updated = true; } } } if (!updated) { break; } } } void FillGreedy() { const int lastShop = input_.shops_[orderdSis_.back()]; bool brokenLastShop = firedCount_[lastShop] > 0; static NNMArr tidBreakLastShop; tidBreakLastShop.resize(NNM); for (int tid : breakableTids_) { cauto& pp = ts.ToPP(tid); tidBreakLastShop[tid] = input_.bombs_[pp.bi_].CanBomb(pp.p_, lastShop); } while (!breakableTids_.empty()) { int bestTid = -1; bool bestBreakLastShop = false; double bestEval = -1e100; for (int tid : breakableTids_) { bool breakLastShop = tidBreakLastShop[tid]; if (brokenLastShop && breakLastShop) { continue; } double eval = 0; cauto& pp = ts.ToPP(tid); { int count = breakableCount_[tid]; eval += count; VASSERT(count > 0); } { int d = shopMap_.dist_[pp.p_]; eval -= d * HP.ShopDistRate; } if (breakLastShop) { int d = gs.CalcL1Dist(lastShop, pp.p_); eval -= d * HP.LastShopDistRate; } eval /= input_.bombs_[pp.bi_].cost_; if (eval > bestEval) { bestEval = eval; bestTid = tid; bestBreakLastShop = breakLastShop; } } VASSERT(bestTid >= 0); Put(bestTid); if (bestBreakLastShop) { brokenLastShop = true; } } RemoveUnnecessary(); } }; int LocalSearch2opt(const NNArr>& sortedTbl, NNArr& route, NNArr& order) { cauto& shops = input_.shops_; auto Cost = [&](int a, int b) { return gs.CalcL1Dist(shops[a], shops[b]); }; int totalCost = 0; REP(i, route.size() - 1) { totalCost += Cost(route[i], route[i + 1]); } auto Update = [&](int iA, int iC) { int iB = iA + 1; int iD = iC + 1; int A = route[iA]; int B = route[iB]; int C = route[iC]; int D = route[iD]; if (B == C || A == D || B == D) { return false; } if (Cost(A, B) + Cost(C, D) > Cost(A, C) + Cost(B, D)) { int newDist = totalCost - (Cost(A, B) + Cost(C, D)) + (Cost(A, C) + Cost(B, D)); totalCost = newDist; if (iB > iD) { swap(iB, iD); } reverse(route.begin() + iB, route.begin() + iD); FOR(i, iB, iD) { order[route[i]] = i; } return true; } return false; }; while (true) { bool update = false; REP(iA, shops.size() - 1) { int iB = iA + 1; for (u8 C : sortedTbl[route[iA]]) { int iC = order[C]; if (iC == iB) { break; } if (iC == shops.size() - 1) { continue; } if (Update(iA, iC)) { update = true; break; } } if (update) { break; } for (u8 D : sortedTbl[route[iB]]) { int iD = order[D]; if (iD == iA) { break; } if (iD == shops.size() - 1) { continue; } if (iD == 0) { continue; } int iC = iD - 1; if (Update(iA, iC)) { update = true; break; } } if (update) { break; } } if (!update) { break; } } return totalCost; } int CalcShopOrder(NNArr& orderdSis, int firstSi, int lastSi) { orderdSis.clear(); cauto& shops = input_.shops_; NNArr used; used.assign(shops.size(), false); int p = 0; orderdSis.push(firstSi); REP(loop, shops.size() - 2) { int bestD = INT_MAX; int bestI = -1; REP(i, shops.size()) { if (used[i]) { continue; } if (i == firstSi || i == lastSi) { continue; } int s = shops[i]; int d = gs.CalcL1Dist(p, shops[i]); if (d < bestD) { bestD = d; bestI = i; } } VASSERT(bestI >= 0); p = shops[bestI]; used[bestI] = true; orderdSis.push(bestI); } orderdSis.push(lastSi); static NNArr> aroundSortedSis; aroundSortedSis.resize(shops.size()); REP(siA, shops.size()) { auto& sis = aroundSortedSis[siA]; sis.clear(); REP(siB, shops.size()) { if (siA == siB) { continue; } sis.push(siB); } sis.stable_sort([&](int a, int b) { return gs.CalcL1Dist(shops[siA], shops[a]) < gs.CalcL1Dist(shops[siA], shops[b]); }); } NNArr order; order.resize(orderdSis.size()); REP(i, orderdSis.size()) { order[orderdSis[i]] = i; } return LocalSearch2opt(aroundSortedSis, orderdSis, order); } struct MoveState { int p_; NNArr grid_; int shopCount_; int buildingCount_; int bombCount_; MArr bombCounts_; s64 cost_; void Init() { p_ = 0; grid_ = input_.grid_; shopCount_ = input_.shops_.size(); buildingCount_ = input_.buildingCount_; bombCount_ = 0; bombCounts_.assign(M, 0); cost_ = 0; } s64 Score() const { if (shopCount_ > 0 || buildingCount_ > 0) { return 1; } return max(10LL, 1000000000000LL / (10000LL + cost_)); } bool IsEnd() const { return shopCount_ == 0 && buildingCount_ == 0; } void Move(int p) { pint cur = gs.ToPos(p_); pint to = gs.ToPos(p); int dx = to.x - cur.x; int dy = to.y - cur.y; Dir dirX = dx > 0 ? Dir::R : Dir::L; Dir dirY = dy > 0 ? Dir::D : Dir::U; if (dx > 0) { dx = 1; } else if (dx < 0) { dx = -1; } if (dy > 0) { dy = 1; } else if (dy < 0) { dy = -1; } while (cur.x != to.x) { cur.x += dx; if (grid_[gs.ToId(cur)] == '.') { cost_ += square(bombCount_ + 1); } else { cost_ += 2 * square(bombCount_ + 1); } } while (cur.y != to.y) { cur.y += dy; if (grid_[gs.ToId(cur)] == '.') { cost_ += square(bombCount_ + 1); } else { cost_ += 2 * square(bombCount_ + 1); } } p_ = p; } void EasyMove(int p) { int d = gs.CalcL1Dist(p_, p); if (grid_[p] != '.') { ++d; } cost_ += square(bombCount_ + 1) * d; p_ = p; } void SetPosAndCost(int p, s64 cost) { cost_ = cost; p_ = p; } void Buy(int bi) { VASSERT(grid_[p_] == '@'); ++bombCount_; ++bombCounts_[bi]; cost_ += input_.bombs_[bi].cost_; } void WarpBuy(int bi, int appendCost) { ++bombCount_; ++bombCounts_[bi]; cost_ += input_.bombs_[bi].cost_; cost_ += appendCost; } void Fire(int bi) { VASSERT(bombCounts_[bi] > 0); --bombCount_; --bombCounts_[bi]; WarpFire(p_, bi); } void WarpFire(int p, int bi) { for (int id : fireMap[ts.ToId(p, bi)]) { char c = grid_[id]; if (c != '.') { if (c == '@') { --shopCount_; } else { VASSERT(c == '#'); --buildingCount_; } grid_[id] = '.'; } } } }; void CalcRoute(const NNArr& grid, int start, int end, NNArr& route, int& costBlock) { route.clear(); costBlock = -1; struct Node { int point; int totalCost; bool operator < (Node const& n) const { return totalCost > n.totalCost; } }; auto Compare = [&](const Node& a, const Node& b) { return a < b; }; NNArr costs; NNArr froms; costs.assign(NN, INT_MAX); froms.resize(NN); CapPriorityQueue que; costs[start] = 0; froms[start] = -1; que.push(Node{ start, 0 }, Compare); while (!que.empty()) { Node node = que.top(); que.pop(Compare); if (costs[node.point] != node.totalCost) { continue; } for (int n : aroundMap[node.point]) { int cost = node.totalCost + 1; if (grid[n] != '.') { cost += 1; } if (cost < costs[n]) { Node newNode; newNode.point = n; newNode.totalCost = cost; costs[n] = cost; froms[n] = node.point; que.push(newNode, Compare); } } } int p = end; while (p >= 0) { route.push(p); p = froms[p]; } route.reverse(); costBlock = costs[end]; } bool MakeMove(const PlanState& plan, IOResult& result, s64& cost, s64 limitCost, bool easy) { result.commands_.clear(); MoveState state; state.Init(); int targetSii = 0; cauto& shops = input_.shops_; cauto& orderdSis = plan.orderdSis_; static NNMSet planTids; planTids = plan.tids_; static NNArr> shopTids; NNArr posToSiDist; { cauto& shopMap = plan.shopMap_; shopTids.resize(shops.size()); REP(i, shops.size()) { shopTids[i].clear(); } for (int tid : planTids) { cauto& pp = ts.ToPP(tid); int si = shopMap.nearSi_[pp.p_]; shopTids[si].push(tid); } posToSiDist = shopMap.dist_; } auto UpdateNearShop = [&](int targetSii) { VASSERT(state.grid_[shops[orderdSis.back()]] != '.') REP(baseSii, orderdSis.size()) { int baseSi = orderdSis[baseSii]; if (shopTids[baseSi].empty()) { continue; } if (baseSii < targetSii || state.grid_[shops[baseSi]] == '.') { for (int tid : shopTids[baseSi]) { if (!planTids.contains(tid)) { continue; } cauto& pp = ts.ToPP(tid); int nearD = INT_MAX; int nearSi = -1; RREP(sii, orderdSis.size()) { int si = orderdSis[sii]; if (sii < targetSii || state.grid_[shops[si]] == '.') { continue; } int shop = input_.shops_[si]; int d = gs.CalcL1Dist(pp.p_, shop); if (d < nearD) { nearD = d; nearSi = si; } } VASSERT(nearSi >= 0); shopTids[nearSi].push(tid); posToSiDist[pp.p_] = nearD; } shopTids[baseSi].clear(); } } }; struct Command { CommandType type_; int value_; }; struct MoveRecord { int bombCount; int costBlock; }; static CapArr commands; static CapArr, 300> buys; commands.clear(); buys.clear(); int lastShop = -1; int lastBuyCi = -1; NNArr moveFromLastShop; auto Move = [&](MoveState& state, int p) { if (easy) { state.EasyMove(p); } else { state.Move(p); } auto& c = commands.push(); c.type_ = CommandType::Move; c.value_ = p; }; auto CalcMoveCostBlock = [&](int start, int end) { if (easy) { int d = gs.CalcL1Dist(start, end); if (state.grid_[end] != '.') { d += 1; } return d; } else { NNArr route; int costBlock = 0; CalcRoute(state.grid_, start, end, route, costBlock); return costBlock; } }; auto Buy = [&](MoveState& state, int bi) { state.Buy(bi); auto& buy = buys.push(); buy.clear(); buy.push(bi); auto& c = commands.push(); c.type_ = CommandType::Buy; c.value_ = buys.size() - 1; lastShop = state.p_; lastBuyCi = commands.size() - 1; moveFromLastShop.clear(); }; auto UpdateBuy = [&](MoveState& state, int ci, int bi, int appendCost) { state.WarpBuy(bi, appendCost); cauto& c = commands[ci]; auto& buy = buys[c.value_]; buy.push(bi); }; auto Fire = [&](MoveState& state, int bi) { state.Fire(bi); auto& c = commands.push(); c.type_ = CommandType::Fire; c.value_ = bi; }; auto CalcToShopCost = [&](int tid, int targetShop) { cauto& pp = ts.ToPP(tid); int cost = 0; { int cb = CalcMoveCostBlock(state.p_, targetShop); cost += cb * square(1); } { int cb = CalcMoveCostBlock(targetShop, pp.p_); cost += cb * square(1 + 1); } return cost; }; auto CalcToNextCost = [&](int tid) { VASSERT(lastShop >= 0); cauto& pp = ts.ToPP(tid); int cost = 0; for (cauto& move : moveFromLastShop) { int oldCost = move.costBlock * square(move.bombCount + 1); int newCost = move.costBlock * square(move.bombCount + 1 + 1); cost += newCost - oldCost; } { int cb = CalcMoveCostBlock(state.p_, pp.p_); cost += cb * square(1 + 1); } return cost; }; auto MoveFire = [&](int tid, int targetShop) { cauto& pp = ts.ToPP(tid); s64 beforeCost = state.cost_; VASSERT(state.bombCount_ == 0); int toShopCost = INT_MAX; int toNextCost = INT_MAX; toShopCost = CalcToShopCost(tid, targetShop); if (lastShop >= 0) { toNextCost = CalcToNextCost(tid); } if (toShopCost <= toNextCost) { Move(state, targetShop); Buy(state, pp.bi_); auto& move = moveFromLastShop.push(); move.bombCount = 1; { int cb = CalcMoveCostBlock(targetShop, pp.p_); move.costBlock = cb; } Move(state, pp.p_); Fire(state, pp.bi_); if (easy) { VASSERT(state.cost_ == beforeCost + toShopCost + input_.bombs_[pp.bi_].cost_); } } else { int appendCost = 0; for (auto& move : moveFromLastShop) { int oldCost = move.costBlock * square(move.bombCount + 1); int newCost = move.costBlock * square(move.bombCount + 1 + 1); appendCost += newCost - oldCost; ++move.bombCount; } UpdateBuy(state, lastBuyCi, pp.bi_, appendCost); auto& move = moveFromLastShop.push(); move.bombCount = 1; { int cb = CalcMoveCostBlock(state.p_, pp.p_); move.costBlock = cb; } Move(state, pp.p_); Fire(state, pp.bi_); if (easy) { VASSERT(state.cost_ == beforeCost + toNextCost + input_.bombs_[pp.bi_].cost_); } } }; while (targetSii < orderdSis.size()) { const int targetSi = orderdSis[targetSii]; const int targetShop = shops[targetSi]; if (state.grid_[targetShop] == '.') { ++targetSii; continue; } UpdateNearShop(targetSii); NNArr enableTids; NNArr finalTids; for (int tid : shopTids[targetSi]) { if (!planTids.contains(tid)) { continue; } cauto& pp = ts.ToPP(tid); if (targetSii + 1 != orderdSis.size()) { int lastShop = shops[orderdSis.back()]; if (input_.bombs_[pp.bi_].CanBomb(pp.p_, lastShop)) { continue; } } if (input_.bombs_[pp.bi_].CanBomb(pp.p_, targetShop)) { finalTids.push(tid); } else { enableTids.push(tid); } } REP(si, shopTids.size()) { if (si == targetSi) { continue; } for (int tid : shopTids[si]) { if (!planTids.contains(tid)) { continue; } cauto& pp = ts.ToPP(tid); int d = gs.CalcL1Dist(targetShop, pp.p_); if (d >= HP.CutOtherShopDist) { continue; } if (targetSii + 1 != orderdSis.size()) { int lastShop = shops[orderdSis.back()]; if (input_.bombs_[pp.bi_].CanBomb(pp.p_, lastShop)) { continue; } } if (input_.bombs_[pp.bi_].CanBomb(pp.p_, targetShop)) { finalTids.push(tid); } else { enableTids.push(tid); } } } if (!enableTids.empty()) { while (!enableTids.empty()) { int nearD = INT_MAX; int bestTi = -1; REP(ti, enableTids.size()) { int tid = enableTids[ti]; cauto& pp = ts.ToPP(tid); int d = gs.CalcL1Dist(state.p_, pp.p_); if (d < nearD) { nearD = d; bestTi = ti; } } int tid = enableTids[bestTi]; if (lastShop >= 0) { int toShopCost = INT_MAX; int toNextCost = INT_MAX; toShopCost = CalcToShopCost(tid, targetShop); toNextCost = CalcToNextCost(tid); if (toShopCost < toNextCost) { nearD = INT_MAX; REP(ti, enableTids.size()) { int tid = enableTids[ti]; cauto& pp = ts.ToPP(tid); int d = gs.CalcL1Dist(targetShop, pp.p_); if (d < nearD) { nearD = d; bestTi = ti; } } tid = enableTids[bestTi]; } } MoveFire(tid, targetShop); if (state.cost_ >= limitCost) { return false; } planTids.Remove(tid); enableTids.RemoveSwap(bestTi); } continue; } VASSERT(targetSii + 1 != orderdSis.size() || finalTids.size() == 1); finalTids.stable_sort([&](int a, int b) { return posToSiDist[ts.ToPP(a).p_] > posToSiDist[ts.ToPP(b).p_]; }); for (int tid : finalTids) { MoveFire(tid, targetShop); if (state.cost_ >= limitCost) { return false; } planTids.Remove(tid); break; } ++targetSii; } VASSERT(state.IsEnd()); if (!easy) { s64 cost = 0; state.Init(); REP(ci, commands.size()) { cauto& c = commands[ci]; if (c.type_ == CommandType::Move) { NNArr route; int costBlock = 0; CalcRoute(state.grid_, state.p_, c.value_, route, costBlock); REP(i, route.size() - 1) { Dir dir = gs.CalcDir(route[i], route[i + 1]); VASSERT(dir != Dir::Invalid && dir != Dir::N); result.push().SetMove(dir); } int appendCost = costBlock * square(state.bombCount_ + 1); state.SetPosAndCost(c.value_, state.cost_ + appendCost); } else if (c.type_ == CommandType::Buy) { cauto& buy = buys[c.value_]; for (int bi : buy) { state.Buy(bi); result.push().SetBuy(bi); } } else { VASSERT(c.type_ == CommandType::Fire); state.Fire(c.value_); result.push().SetFire(c.value_); } } if (state.cost_ >= limitCost) { return false; } } cost = state.cost_; return true; } void MakePlan(PlanState& plan, s64& cost) { int firstSi = 0; FOR(si, 1, input_.shops_.size()) { if (gs.CalcL1Dist(0, input_.shops_[si]) < gs.CalcL1Dist(0, input_.shops_[firstSi])) { firstSi = si; } } plan.Init(); auto initedPlan = plan; s64 bestCost = INT64_MAX; int bestLastSi = -1; FOR(lastSi, 0, input_.shops_.size()) { if (lastSi == firstSi) { continue; } plan = initedPlan; CalcShopOrder(plan.orderdSis_, firstSi, lastSi); plan.shopMap_.Init(plan.orderdSis_); plan.FillGreedy(); IOResult result; s64 cost = 0; if (MakeMove(plan, result, cost, bestCost, true)) { if (cost < bestCost) { bestCost = cost; bestLastSi = lastSi; } } else { } } plan = initedPlan; CalcShopOrder(plan.orderdSis_, firstSi, bestLastSi); plan.shopMap_.Init(plan.orderdSis_); plan.FillGreedy(); cost = bestCost; } struct State { PlanState plan_; s64 rawScore_; void Init() { plan_.Init(); MakePlan(plan_, rawScore_); } s64 RawScore() const { return -rawScore_; } double EvalScore() const { return (double)-rawScore_; } }; static constexpr int StateSize = sizeof(State); struct Solver { State maxState_; void CheckMaxScore(const State& state) { if (state.RawScore() > maxState_.RawScore()) { maxState_ = state; } } void Run(ChronoTimer& timer) { vector states; InitState(states); maxState_ = states[0]; SimulatedAnnealing sa; sa.startTemp_ = HP.StartTemp; sa.endTemp_ = HP.EndTemp; sa.stepLoopCount = 10; auto transitions = make_tuple( MAKE_TRANS(Transition_Update1, 10) ); sa.Run2(timer, states, transitions); s64 cost = 0; IOResult result; MakeMove(maxState_.plan_, result, cost, INT64_MAX, false); server.Output(result); } void InitState(vector& states) { states.resize(InitialStateCount); { State& state = states[0]; state.Init(); } FOR(i, 1, InitialStateCount) { states[i] = states[0]; } } void Transition_Update1(SimulatedAnnealing& sa, SAChecker& checker, State& state) { static Backup backup; state.plan_.Save(backup); int removeCount = min(HP.RemoveCountMin + rand_((int)HP.RemoveCountRange), state.plan_.tids_.size()); REP(i, removeCount) { int ti = rand_(state.plan_.tids_.size()); int tid = state.plan_.tids_[ti]; state.plan_.Remove(tid); } state.plan_.FillGreedy(); double as = checker.AcceptScore(); s64 limitCost = (s64)ceil(-as); s64 cost = 0; IOResult result; if (MakeMove(state.plan_, result, cost, limitCost, true)) { VASSERT(cost <= limitCost); double newEvalScore = (double)-cost; checker(newEvalScore, true); state.rawScore_ = cost; CheckMaxScore(state); } else { checker.SetRevert(); state.plan_.Restore(backup); } } }; struct Main { void Run(int argc, const char* argv[]) { ChronoTimer timer; server.InitInput(timer); static Solver solver; timer.StartMs(TIME_LIMIT); solver.Run(timer); server.Finalize(); } };