結果
| 問題 |
No.5019 Hakai Project
|
| コンテスト | |
| ユーザー |
 bowwowforeach
|
| 提出日時 | 2023-11-19 19:18:41 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2,927 ms / 3,000 ms |
| コード長 | 61,255 bytes |
| コンパイル時間 | 6,420 ms |
| コンパイル使用メモリ | 335,960 KB |
| 実行使用メモリ | 258,036 KB |
| スコア | 2,920,310,720 |
| 最終ジャッジ日時 | 2023-11-19 19:21:33 |
| 合計ジャッジ時間 | 159,943 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge12 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
コンパイルメッセージ
main.cpp:409:22: warning: class 'CapArr<T, CAP>' is implicitly friends with itself
409 | friend class CapArr;
| ^~~~~~
ソースコード
#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 <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cfenv>
#include <cinttypes>
#include <cstdint>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#else
#include <bits/stdc++.h>
#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 <class T, class U> inline void chmin(T& a, U&& b) { if (b < a) { a = b; } }
template <class T, class U> inline void chmax(T& a, U&& b) { if (a < b) { a = b; } }
template <class T, class U, class V> inline void clip(T& v, U&& lower, V&& upper) {
if (v < lower) { v = lower; }
else if (v > upper) { v = upper; }
}
template <class T> inline constexpr T square(T v) { return v * v; }
template <class T, int SIZE>
constexpr int len(const T(&)[SIZE]) { return SIZE; }
#define cauto const auto
#include <cstdint>
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::milliseconds>(chrono::high_resolution_clock::now() - startTime_).count();
}
inline int ElapseTimeUs() const {
return (int)chrono::duration_cast<chrono::microseconds>(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<chrono::microseconds>(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 <class T>
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<Main>(argc, argv);
}
struct MemoryException {};
#define VALIDATE_ABORT()
#define VALIDATE_ASSERT(exp)
#define VABORT() VALIDATE_ABORT()
#define VASSERT(exp) VALIDATE_ASSERT(exp)
template <class A, class B>
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 <class C, class D>
auto operator + (pr<C, D> const& v) const {
return pr<decltype(a + v.a), decltype(b + v.b)>{ a + v.a, b + v.b };
}
template <class C, class D>
auto operator - (pr<C, D> const& v) const {
return pr<decltype(a - v.a), decltype(b - v.b)>{ a - v.a, b - v.b };
}
template <class C, class D>
explicit operator pr<C, D>() const {
return { C(a), D(b) };
}
template <class T>
auto operator * (T const& v) const -> pr<decltype(x * v), decltype(y * v)> {
return { x * v, y * v };
}
template <class T>
auto operator / (T const& v) const -> pr<decltype(x / v), decltype(y / v)> {
return { x / v, y / v };
}
template <class T>
pr& operator *= (T const& v) {
x *= v;
y *= v;
return *this;
}
template <class T>
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 <size_t I>
auto get() const {
if constexpr (I == 0) {
return x;
}
else if constexpr (I == 1) {
return y;
}
}
};
using pint = pr<int, int>;
using pdouble = pr<double, double>;
static_assert(is_trivially_copyable<pint>::value, "not trivially_copyable");
template <class A, class B>
struct tuple_size<pr<A, B>> : integral_constant<size_t, 2> {};
template <class A, class B>
struct tuple_element<0, pr<A, B>> { using type = A; };
template <class A, class B>
struct tuple_element<1, pr<A, B>> { 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 T, int CAP>
class CapArr {
private:
friend class CapArr;
static_assert(is_trivially_copyable<T>::value);
T array_[CAP];
int size_ = 0;
public:
bool operator == (const CapArr<T, CAP>& r) const {
if (size_ != r.size_) {
return false;
}
REP(i, size_) {
if (!(array_[i] == r.array_[i])) {
return false;
}
}
return true;
}
template <class U, int U_CAP>
bool operator != (const CapArr<U, U_CAP>& r) const {
return !(*this == r);
}
bool MemEqual(const CapArr<T, CAP>& 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<T>::value) {
memset(data(), underlying_type<T>::type(e), size);
}
else {
memset(data(), *reinterpret_cast<const unsigned char*>(&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<T, CAP>& 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 <int RCAP>
void append(const CapArr<T, RCAP>& 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 <class LESS>
void stable_sort(LESS&& less) {
::stable_sort(begin(), end(), less);
}
void reverse() {
::reverse(begin(), end());
}
};
template <class T, int CAPACITY>
struct CapacityQueue {
private:
array<T, CAPACITY> 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 <class T, int CAPACITY>
using CapQue = CapacityQueue<T, CAPACITY>;
template <int CAP>
struct CapacitySet {
private:
CapArr<int, CAP> elemens;
array<int, CAP> indexTable;
public:
CapacitySet() {
fill(indexTable.begin(), indexTable.end(), -1);
}
void Clear() {
elemens.clear();
fill(indexTable.begin(), indexTable.end(), -1);
}
void Add(int ai) {
indexTable[ai] = elemens.size();
elemens.push(ai);
}
void ForceAdd(int ai) {
if (indexTable[ai] >= 0) {
return;
}
indexTable[ai] = elemens.GetCount();
elemens.PushBack(ai);
}
void Remove(int ai) {
int removeIndex = indexTable[ai];
int lastIndex = elemens.size() - 1;
if (removeIndex != lastIndex) {
elemens[removeIndex] = elemens[lastIndex];
indexTable[elemens[lastIndex]] = removeIndex;
}
elemens.pop();
indexTable[ai] = -1;
}
void ForceRemove(int ai) {
if (indexTable[ai] < 0) {
return;
}
int removeIndex = indexTable[ai];
int lastIndex = elemens.GetCount() - 1;
if (removeIndex != lastIndex) {
elemens[removeIndex] = elemens[lastIndex];
indexTable[elemens[lastIndex]] = removeIndex;
}
elemens.PopBack();
indexTable[ai] = -1;
}
bool IsContain(int ai) const {
return indexTable[ai] >= 0;
}
bool contains(int ai) const {
return indexTable[ai] >= 0;
}
int GetCount() const {
return elemens.GetCount();
}
int size() const {
return elemens.size();
}
bool empty() const {
return elemens.empty();
}
int At(int index) const {
return elemens[index];
}
int 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 <class T, int CAP>
using CapSet = CapacitySet<CAP>;
template <int S>
struct CheckMapS {
private:
array<u32, S> 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<S>& r) const {
REP(i, S) {
if (this->IsChecked(i) != r.IsChecked(i)) {
return false;
}
}
return true;
}
};
template <class T, int S>
struct CheckMapDataS {
private:
array<T, S> data_;
array<u32, S> 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 <class T, int CAP>
struct CapacityMap {
private:
CapArr<pr<int, T>, CAP> elemens;
CheckMapDataS<int, CAP> 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 <class T, int CAPACITY>
using CapMap = struct CapacityMap<T, CAPACITY>;
template <class T, int CAP>
struct CapPriorityQueue {
CapArr<T, CAP> buf_;
void clear() {
buf_.clear();
}
bool empty() const {
return buf_.empty();
}
bool exist() const {
return !buf_.empty();
}
const T& top() {
return buf_.front();
}
template <class CMP>
void push(const T& v, CMP&& cmp) {
buf_.push(v);
push_heap(ALL(buf_), cmp);
}
template <class CMP>
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 <class IT, class RAND>
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 <cstdint>
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 <class T>
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<Dir, 4> Dir4 = {
Dir::L,
Dir::U,
Dir::R,
Dir::D,
};
constexpr array<pint, 4> Around4 = { pint{-1, 0}, pint{0, -1}, pint{1, 0}, pint{0, 1} };
constexpr array<pint, 5> 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 <int W, int H>
struct GridSystemS {
pint toPos_[W*H];
constexpr GridSystemS() : toPos_{} {
REP(y, H) {
REP(x, W) {
int id = x + W * y;
toPos_[id] = pint{ x, y };
}
}
}
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 const pint& ToPos(int id) const {
return toPos_[id];
}
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 <class T, int CAP>
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 <int W, int H, int AROUND_COUNT>
struct AroundMapS {
using CA = CCA<int, AROUND_COUNT>;
CA table[W * H];
constexpr AroundMapS(const array<pint, AROUND_COUNT>& 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 <int W, int H, int AROUND_COUNT>
struct DirMapS {
using CA = CCA<int, AROUND_COUNT>;
CA table[W * H];
constexpr DirMapS(const array<pint, AROUND_COUNT>& 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 <int W, int H>
struct JointAroundMapS {
using CA = CCA<int, 8>;
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 <class T> using NArr = CapArr<T, N>;
template <class T> using NNArr = CapArr<T, NN>;
template <class T> using MArr = CapArr<T, M>;
template <class T> using NNMArr = CapArr<T, NNM>;
template <class T> using NQue = CapQue<T, N>;
template <class T> using NNQue = CapQue<T, NN>;
template <class T> using MQue = CapQue<T, M>;
template <class T> using NNMQue = CapQue<T, NNM>;
template <class T> using NSet = CapSet<T, N>;
template <class T> using NNSet = CapSet<T, NN>;
template <class T> using MSet = CapSet<T, M>;
template <class T> using NNMSet = CapSet<T, NNM>;
struct Bomb {
int cost_;
double invCost_;
NNArr<int> ps_;
NNArr<bool> flags_;
CapArr<NNArr<bool>, 300> bombShop_;
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 {
return CanBomb(gs.ToPos(targetPos) - gs.ToPos(putPos));
}
bool CanBombShop(int putPos, int si) const {
return bombShop_[si][putPos];
}
};
struct Input {
NNArr<char> grid_;
MArr<Bomb> bombs_;
NNArr<int> 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 <class T>
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<double> 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<double> 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, 25.025193540547974, 25.0, 35.0);PARAM_LOWER(0.0);
PARAM_DOUBLE(EndTemp, 9.896526645816342, 5.0, 10.0);PARAM_LOWER(0.0);
PARAM_INT(RemoveCountMin, 9, 5, 11);PARAM_LOWER(1);
PARAM_INT(RemoveCountRange, 5, 7, 13);PARAM_LOWER(1);
PARAM_DOUBLE(ShopDistRate, 0.14330911299300678, 0.05, 0.15);
PARAM_DOUBLE(LastShopDistRate, 0.12649641320064645, 0.1, 0.2);
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<IOCommand, TurnMax> 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<u16, 31 * 31>;
array<CA, NNM> 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<u16, 31 * 31 * M>;
array<CA, NN> 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_;
bomb.invCost_ = 1.0 / (double)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;
}
bomb.bombShop_.resize(input_.shops_.size());
for (auto& b : bomb.bombShop_) {
b.assign(NN, false);
}
}
fireMap.Init();
fromFireMap.Init();
REP(si, input_.shops_.size()) {
for (int tid : fromFireMap[input_.shops_[si]]) {
cauto& pp = ts.ToPP(tid);
input_.bombs_[pp.bi_].bombShop_[si][pp.p_] = true;
}
}
}
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<int> table_;
void push(int value, int count) {
table_.reserve(table_.size() + count);
REP(i, count) {
table_.emplace_back(value);
}
}
template <class ENGINE>
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<double>::is_iec559);
return currentScore + temp * log(rand_->GetDouble());
}
void SetRevert() {
++noMaxUpdateCount;
}
};
template <class F>
struct SATransition {
const char* name;
F func;
int weight;
};
template <class F>
auto MakeTransition(const char* name, F&& func, int weight) {
return SATransition<F>{ name, func, weight };
}
#define MAKE_TRANS(func, weight) MakeTransition(#func, [&](SAChecker& sac, State& state) { func(sa, sac, state); }, weight)
struct SimulatedAnnealing {
vector<SAChecker> 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 <class STATE, class... TRANSITION>
void Run2(ChronoTimer& timer, vector<STATE>& states, tuple<SATransition<TRANSITION>...>& 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<int> 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 <class Tuple, class Func>
void TupleLoop(Tuple & t, Func && f) {
TupleLoop2(t, forward<Func>(f), make_index_sequence<tuple_size<Tuple>::value>{});
}
template <class Tuple, class Func, size_t... Indics>
void TupleLoop2(Tuple & t, Func && f, index_sequence<Indics...>) {
using swallow = int[];
(void)swallow {
(TupleLoop3<Tuple, Func, Indics>(t, f), 0)...
};
}
template <class Tuple, class Func, size_t Index>
void TupleLoop3(Tuple & t, Func & f) {
f(get<Index>(t), Index);
}
template <class Tuple, class Func>
void TupleAccess(Tuple & t, int i, Func && f) {
TupleAccess2(t, i, forward<Func>(f), make_index_sequence<tuple_size<Tuple>::value>{});
}
template <class Tuple, class Func, size_t... Indics>
void TupleAccess2(Tuple & t, int i, Func && f, index_sequence<Indics...>) {
using swallow = int[];
(void)swallow {
(TupleAccess3<Tuple, Func, Indics>(t, i, f), 0)...
};
}
template <class Tuple, class Func, size_t Index>
void TupleAccess3(Tuple & t, int i, Func & f) {
if (i == Index) {
f(get<Index>(t), Index);
}
}
};
Xor64 rand_;
struct ShopMap {
NNArr<int> dist_;
NNArr<int> nearSi_;
void Init(const NNArr<int>& 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<int> breakableCount_;
NNMSet<int> breakableTids_;
NNMSet<int> tids_;
NNArr<int> firedCount_;
};
static constexpr int BackupSize = sizeof(Backup);
struct PlanState {
NNArr<int> orderdSis_;
ShopMap shopMap_;
NNMArr<int> breakableCount_;
NNMSet<int> breakableTids_;
NNMSet<int> tids_;
NNArr<int> 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<int> 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 lastSi = orderdSis_.back();
const int lastShop = input_.shops_[lastSi];
bool brokenLastShop = firedCount_[lastShop] > 0;
static NNMArr<bool> tidBreakLastShop;
tidBreakLastShop.resize(NNM);
for (int tid : breakableTids_) {
cauto& pp = ts.ToPP(tid);
tidBreakLastShop[tid] = input_.bombs_[pp.bi_].CanBombShop(pp.p_, lastSi);
}
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_].invCost_;
if (eval > bestEval) {
bestEval = eval;
bestTid = tid;
bestBreakLastShop = breakLastShop;
}
}
VASSERT(bestTid >= 0);
Put(bestTid);
if (bestBreakLastShop) {
brokenLastShop = true;
}
}
RemoveUnnecessary();
}
};
int LocalSearch2opt(const NNArr<NNArr<int>>& sortedTbl, NNArr<int>& route, NNArr<int>& 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<int>& orderdSis, int firstSi, int lastSi) {
orderdSis.clear();
cauto& shops = input_.shops_;
NNArr<bool> 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<NNArr<int>> 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<int> order;
order.resize(orderdSis.size());
REP(i, orderdSis.size()) {
order[orderdSis[i]] = i;
}
return LocalSearch2opt(aroundSortedSis, orderdSis, order);
}
struct MoveState {
int p_;
NNArr<char> grid_;
int shopCount_;
int buildingCount_;
int bombCount_;
MArr<int> 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 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<char>& grid, int start, int end, NNArr<int>& 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<int> costs;
NNArr<int> froms;
costs.assign(NN, INT_MAX);
froms.resize(NN);
CapPriorityQueue<Node, NN> 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<int> planTids;
planTids = plan.tids_;
static NNArr<NNArr<int>> shopTids;
NNArr<int> 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<Command, TurnMax> commands;
static CapArr<CapArr<s8, 100>, 300> buys;
commands.clear();
buys.clear();
int lastShop = -1;
int lastBuyCi = -1;
NNArr<MoveRecord> moveFromLastShop;
auto Move = [&](MoveState& state, int p) {
state.EasyMove(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<int> 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<int> enableTids;
NNArr<int> 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);
}
}
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<int> 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<State> states;
InitState(states);
maxState_ = states[0];
SimulatedAnnealing sa;
sa.startTemp_ = HP.StartTemp;
sa.endTemp_ = HP.EndTemp;
sa.stepLoopCount = 1;
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<State>& 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();
}
};