結果
| 問題 |
No.5017 Tool-assisted Shooting
|
| コンテスト | |
| ユーザー |
 bowwowforeach
|
| 提出日時 | 2023-07-16 18:53:54 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,615 ms / 2,000 ms |
| コード長 | 35,284 bytes |
| コンパイル時間 | 4,699 ms |
| コンパイル使用メモリ | 242,184 KB |
| 実行使用メモリ | 24,444 KB |
| スコア | 4,072,131 |
| 平均クエリ数 | 1000.00 |
| 最終ジャッジ日時 | 2023-07-16 18:58:34 |
| 合計ジャッジ時間 | 143,564 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge12 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
コンパイルメッセージ
main.cpp:409:22: 警告: 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 (1970)
#define NOT_SUBMIT 0
#define VALIDATION 0
#define IO_FILE 0
#define OUTPUT_INFO 0
#define OUTPUT_FINAL_INFO 1
#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) {
memset(data(), e, size);
}
else {
for (int i = 0; i < size; ++i) {
array_[i] = e;
}
}
}
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;
}
};
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 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 CapacitySet {
private:
CapArr<T, CAP> elemens;
CheckMapDataS<T, CAP> indexTable;
public:
CapacitySet() {
}
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 IsContain(T ai) const {
return indexTable.IsChecked(ai);
}
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 <class T, int CAP>
using CapSet = CapacitySet<T, CAP>;
inline int popcount(uint64_t bit) {
#if _MSC_VER
return (int)__popcnt64(bit);
#else
return __builtin_popcountll(bit);
#endif
}
int msb(uint64_t v) {
if (v == 0) return false;
v |= (v >> 1);
v |= (v >> 2);
v |= (v >> 4);
v |= (v >> 8);
v |= (v >> 16);
v |= (v >> 32);
return popcount(v) - 1;
}
inline uint64_t RotateLeft(uint64_t bit, uint64_t shift) {
return (bit << shift) | (bit >> (64ULL - shift));
}
inline uint64_t RotateRight(uint64_t bit, uint64_t shift) {
return (bit >> shift) | (bit << (64ULL - shift));
}
#if _MSC_VER
#include <intrin.h>
#endif
inline int FindBitRL(uint64_t bit) {
if (bit == 0) {
return -1;
}
#if _MSC_VER
unsigned long index = 0;
_BitScanForward64(&index, bit);
return (int)index;
#else
return __builtin_ctzll(bit);
#endif
}
inline int FindBitLR(uint64_t bit) {
if (bit == 0) {
return -1;
}
#if _MSC_VER
unsigned long index = 0;
_BitScanReverse64(&index, bit);
return 63 - (int)index;
#else
return __builtin_clzll(bit);
#endif
}
template <class K>
struct CapHashSet {
size_t m_capacity;
K* m_keys;
uint8_t* m_states;
size_t m_mask;
int m_count = 0;
void init(size_t capacity) {
m_capacity = 1ULL << (msb(capacity) + 1);
m_mask = m_capacity - 1;
m_keys = (K*)malloc(m_capacity * sizeof(K));
m_states = (uint8_t*)calloc(m_capacity, sizeof(uint8_t));
m_count = 0;
}
void clear() {
memset(m_states, 0, m_capacity * sizeof(uint8_t));
m_count = 0;
}
inline void set(K key) {
size_t i = key & m_mask;
for (;;) {
if (m_states[i]) {
if (key == m_keys[i]) {
break;
}
}
else {
m_states[i] = 1;
m_keys[i] = key;
++m_count;
break;
}
(++i) &= m_mask;
}
}
inline void insert(K key) {
set(key);
}
inline bool contains(K key) const {
size_t i = key & m_mask;
for (;;) {
if (m_states[i]) {
if (key == m_keys[i]) {
return true;
}
}
else {
break;
}
(++i) &= m_mask;
}
return false;
}
bool enter(K key) {
size_t i = key & m_mask;
for (;;) {
if (m_states[i]) {
if (key == m_keys[i]) {
return false;
}
}
else {
m_states[i] = 1;
m_keys[i] = key;
++m_count;
return true;
}
(++i) &= m_mask;
}
}
int GetCount() const {
return m_count;
}
};
#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;
}
inline uint64_t operator()(uint64_t r) {
return (*this)() % r;
}
inline double GetDouble() {
return (*this)() / (double)UINT64_MAX;
}
inline bool GetProb(double E) {
return GetDouble() <= E;
}
};
#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
constexpr
struct {
} HP;
constexpr int T_Max = 1000;
constexpr int W = 25;
constexpr int H = 60;
constexpr int level_up = 100;
template <class T> using WHArr = CapArr<T, W * H>;
template <class T> using WArr = CapArr<T, W>;
template <class T> using HArr = CapArr<T, H>;
enum class Action {
S,
L,
R,
};
char ActionToChar[3] = { 'S', 'L', 'R' };
int ActionToDir[3] = { 0, -1, 1 };
struct Enemy {
int initHp;
int hp;
int power;
void init() {
initHp = -1;
hp = -1;
power = -1;
}
bool exist() const {
return hp > 0;
}
void clear() {
initHp = -1;
hp = -1;
power = -1;
}
};
struct Player {
int x;
int score;
int power;
int level;
void init() {
x = 12;
score = 0;
power = 0;
level = 1;
}
void move(Action a) {
x += ActionToDir[(int)a];
if (x < 0) {
x = W - 1;
}
else if (x >= W) {
x = 0;
}
}
};
struct State {
WArr<HArr<Enemy>> enemies;
Player player;
int turn;
int destroyCount;
bool gameOver;
void init() {
enemies.resize(W);
REP(x, W) {
enemies[x].resize(H);
REP(y, H) {
enemies[x][y].init();
}
}
player.init();
turn = 0;
destroyCount = 0;
gameOver = false;
}
void moveEnemy() {
REP(x, W) {
REP(y, H) {
auto& e = enemies[x][y];
if (e.exist()) {
if (y - 1 >= 0) {
enemies[x][y - 1] = e;
if (y - 1 == 0 && x == player.x) {
gameOver = true;
}
}
e.clear();
}
}
}
}
void spawnEnemy(istream& is) {
int n = 0;
is >> n;
if (n < 0) {
quick_exit(0);
return;
}
int h, p, x;
REP(i, n) {
is >> h >> p >> x;
auto& e = enemies[x][H - 1];
e.initHp = h;
e.hp = h;
e.power = p;
}
}
void move(Action a) {
player.move(a);
}
void attack() {
REP(y, H) {
auto& e = enemies[player.x][y];
if (e.exist()) {
if (y == 0) {
gameOver = true;
}
else {
e.hp -= player.level;
if (e.hp <= 0) {
player.score += e.initHp;
player.power += e.power;
player.level = 1 + player.power / level_up;
e.clear();
++destroyCount;
}
}
break;
}
}
++turn;
}
void moveAndAttack(Action a) {
move(a);
attack();
}
int findFrontEnemy(int x) const {
REP(y, H) {
if (enemies[x][y].exist()) {
return y;
}
}
return -1;
}
};
struct IOServer {
State state_;
void InitInput(ChronoTimer& timer) {
istream& is = cin;
timer.Init();
state_.init();
}
void TurnInput() {
istream& is = cin;
state_.moveEnemy();
state_.spawnEnemy(is);
}
void Output(Action action) {
ostream& os = cout;
os << ActionToChar[(int)action] << endl;
state_.moveAndAttack(action);
}
void Finalize() {
}
};
IOServer server;
template <class OBJECT>
struct ObjectPool {
static_assert(is_trivially_copyable<OBJECT>::value, "not trivially copyable");
OBJECT* pool_ = nullptr;
OBJECT** reusable_ = nullptr;
int capacity_ = 0;
int usedTotalCount_ = 0;
int usedPoolCount_ = 0;
int reusableCount_ = 0;
int maxTotalCount_ = 0;
~ObjectPool() {
if (pool_) {
free(pool_);
}
if (reusable_) {
free(reusable_);
}
}
void Init(int capacity) {
if (capacity != capacity_) {
if (pool_) {
free(pool_);
}
if (reusable_) {
free(reusable_);
}
pool_ = (OBJECT*)malloc(capacity * sizeof(OBJECT));
reusable_ = (OBJECT**)malloc(capacity * sizeof(OBJECT*));
capacity_ = capacity;
}
usedTotalCount_ = 0;
usedPoolCount_ = 0;
reusableCount_ = 0;
}
void Clear() {
usedTotalCount_ = 0;
usedPoolCount_ = 0;
reusableCount_ = 0;
}
inline OBJECT* New() {
if (reusableCount_) {
++usedTotalCount_;
--reusableCount_;
chmax(maxTotalCount_, usedTotalCount_);
return reusable_[reusableCount_];
}
if (usedPoolCount_ >= capacity_) {
}
++usedTotalCount_;
chmax(maxTotalCount_, usedTotalCount_);
return &pool_[usedPoolCount_++];
}
inline void Delete(OBJECT* obj) {
reusable_[reusableCount_] = obj;
++reusableCount_;
--usedTotalCount_;
}
inline void Delete(OBJECT** start, int count) {
memcpy(&reusable_[reusableCount_], start, sizeof(OBJECT*) * count);
reusableCount_ += count;
usedTotalCount_ -= count;
}
inline int GetUsedCount() const {
return usedTotalCount_;
}
inline string Usage() const {
stringstream ss;
ss << usedTotalCount_ << " (" << (int)floor(usedTotalCount_ * 100 / (double)capacity_ + 0.5) << " %)";
return ss.str();
}
inline int UsedRate() const {
return (int)round(usedTotalCount_ * 100 / (double)capacity_);
}
inline int GetCapacity() const {
return capacity_;
}
inline int GetMaxUseCount() const {
return maxTotalCount_;
}
inline int GetMaxUsedRate() const {
return (int)round((double)GetMaxUseCount() * 100 / (double)capacity_);
}
inline string MaxUsage() const {
stringstream ss;
ss << maxTotalCount_ << " / " << capacity_ << " (" << (int)floor(maxTotalCount_ * 100 / (double)capacity_ + 0.5) << " %)";
return ss.str();
}
double GetMemoryRate() const {
return usedTotalCount_ / (double)capacity_;
}
};
template <class NODE, class SCORE_LESS_COMPARER>
struct BeamSearch {
public:
struct Nexts {
vector<NODE*>& nodes_;
Nexts(vector<NODE*>& nodes) : nodes_(nodes) {}
void Add(NODE* node) {
nodes_.emplace_back(node);
}
};
private:
using NodePool = ObjectPool<NODE>;
using HashTable = CapHashSet<u64>;
NodePool nodePool_;
HashTable hashTable_;
int widthLimit_;
double startTimeRate_;
vector<NODE*> nodes_;
vector<NODE*> nextNodes_;
public:
NODE* New() {
return nodePool_.New();
}
void Delete(NODE* node) {
nodePool_.Delete(node);
}
bool ContainHash(u64 hash) const {
return hashTable_.contains(hash);
}
void AddHash(u64 hash) {
hashTable_.set(hash);
}
const vector<NODE*> RefFinalNodes() {
return nodes_;
}
void Initialize(int widthLimit, int maxExpandCount, int hashTableSize = 0, int poolSize = -1, double startTimeRate = 0.5) {
int widthCapacity = widthLimit * maxExpandCount;
if (poolSize < 0) {
poolSize = widthLimit + widthLimit * maxExpandCount;
}
nodePool_.Init(poolSize);
hashTable_.init(hashTableSize);
widthLimit_ = widthLimit;
startTimeRate_ = startTimeRate;
nodes_.reserve(widthCapacity);
nextNodes_.reserve(widthCapacity);
}
template <class CREATE_ROOT_NODES, class CREATE_NEXT_NODES>
void Run(ChronoTimer& timer, int beamDepth, int timeLimitMs, CREATE_ROOT_NODES&& createRootNodes, CREATE_NEXT_NODES&& createNextNodes) {
SCORE_LESS_COMPARER less;
auto greater = [&](const NODE* a, const NODE* b) {
return less(b, a);
};
nodePool_.Clear();
hashTable_.clear();
nodes_.clear();
nextNodes_.clear();
Nexts nexts(nextNodes_);
auto startTime = timer.ElapseTimeUs();
auto limitTimePoint = timer.GetLimitTimePointUs(timeLimitMs * 1000);
int finishedNodeCount = 0;
{
createRootNodes(nexts);
REP(depth, beamDepth) {
swap(nodes_, nextNodes_);
if (nodes_.empty()) {
break;
}
auto nowTime = timer.ElapseTimeUs();
int timeLeft = timer.LeftToUS(limitTimePoint);
int turnLeft = beamDepth - depth;
double turnRate = depth / (double)(depth + turnLeft);
double timeRate = startTimeRate_ + (1.0 - startTimeRate_) * turnRate;
int turnTime = int(timeLeft * timeRate / turnLeft);
timer.StartUs(nowTime + turnTime);
int width = widthLimit_;
auto elapsedTime = nowTime - startTime;
if (elapsedTime && finishedNodeCount) {
double timeNode = finishedNodeCount / (double)elapsedTime;
chmin(width, (int)ceil(timeNode * turnTime));
chmax(width, 1);
}
if (nodes_.size() > width) {
nth_element(nodes_.begin(), nodes_.begin() + width, nodes_.end(), greater);
nodePool_.Delete(nodes_.data() + width, (int)nodes_.size() - width);
nodes_.resize(width);
}
sort(nodes_.begin(), nodes_.end(), greater);
nodePool_.Delete(nextNodes_.data(), (int)nextNodes_.size());
nextNodes_.clear();
hashTable_.clear();
for (auto& node : nodes_) {
createNextNodes(depth, node, nexts);
if (timer.IsOver()) {
break;
}
++finishedNodeCount;
}
}
}
if (nextNodes_.empty()) {
swap(nodes_, nextNodes_);
}
cerr << "total node " << finishedNodeCount << endl;
}
template <class CREATE_ROOT_NODES, class CREATE_NEXT_NODES>
void Run(ChronoTimer& timer, CREATE_ROOT_NODES&& createRootNodes, CREATE_NEXT_NODES&& createNextNodes) {
nodePool_.Clear();
nodes_.clear();
nextNodes_.clear();
hashTable_.clear();
SCORE_LESS_COMPARER less;
auto greater = [&](const NODE* a, const NODE* b) {
return less(b, a);
};
Nexts nexts(nextNodes_);
int finishedNodeCount = 0;
int depth = 0;
{
createRootNodes(nexts);
while (!timer.IsOver()) {
swap(nodes_, nextNodes_);
int width = widthLimit_;
if (nodes_.size() > width) {
nth_element(nodes_.begin(), nodes_.begin() + width, nodes_.end(), greater);
nodePool_.Delete(nodes_.data() + width, (int)nodes_.size() - width);
nodes_.resize(width);
}
nodePool_.Delete(nextNodes_.data(), (int)nextNodes_.size());
nextNodes_.clear();
for (auto& node : nodes_) {
createNextNodes(depth, node, nexts);
if (timer.IsOver()) {
break;
}
}
finishedNodeCount += (int)nodes_.size();
++depth;
if (nextNodes_.empty()) {
break;
}
}
}
}
template <class CREATE_ROOT_NODES, class CREATE_NEXT_NODES>
void Run(int beamWidth, int beamDepth, CREATE_ROOT_NODES&& createRootNodes, CREATE_NEXT_NODES&& createNextNodes) {
nodePool_.Clear();
nodes_.clear();
nextNodes_.clear();
hashTable_.clear();
SCORE_LESS_COMPARER less;
auto greater = [&](const NODE* a, const NODE* b) {
return less(b, a);
};
Nexts nexts(nextNodes_);
int finishedNodeCount = 0;
{
createRootNodes(nexts);
REP(depth, beamDepth) {
swap(nodes_, nextNodes_);
if (nodes_.size() > beamWidth) {
nth_element(nodes_.begin(), nodes_.begin() + beamWidth, nodes_.end(), greater);
nodePool_.Delete(nodes_.data() + beamWidth, (int)nodes_.size() - beamWidth);
nodes_.resize(beamWidth);
}
nodePool_.Delete(nextNodes_.data(), (int)nextNodes_.size());
nextNodes_.clear();
for (auto& node : nodes_) {
createNextNodes(depth, node, nexts);
}
finishedNodeCount += (int)nodes_.size();
if (nextNodes_.empty()) {
break;
}
}
}
}
};
struct Node {
Action firstAction;
State state;
double evalScore;
};
static constexpr int StateSize = sizeof(Node);
struct RawComparer {
bool operator()(const Node* a, const Node* b) const {
return a->evalScore < b->evalScore;
}
};
struct Solver {
Xor64 rand_;
using Search = BeamSearch<Node, RawComparer>;
using Nexts = Search::Nexts;
Search search;
void Run(ChronoTimer& timer) {
search.Initialize(1000, 16, 0, -1, 0.5);
REP(t, T_Max) {
server.TurnInput();
double bestEvalScore = -1e100;
Action bestAction = Action::S;
auto Eval = [&](const State& state) {
double eval = 0;
double turnRate = state.turn / (double)T_Max;
double baseHP = 7.5 + 0.15 * state.turn;
double destroyTurn = baseHP / (double)(state.player.level + state.player.power / 100.0);
eval -= pow(destroyTurn, 20) * 1000;
eval += state.player.power;
eval -= sqrt(state.turn) * 20000000;
eval += state.player.score * 10 * pow(turnRate, 2.0);
if (state.gameOver) {
eval -= 1e10;
}
return eval;
};
auto FindEnemy = [&](const State& state) {
cauto& player = state.player;
return state.findFrontEnemy(player.x);
};
auto DestroyTurn = [&](const State& state, int enemyY) {
cauto& player = state.player;
cauto& enemy = state.enemies[player.x][enemyY];
int attackCount = enemyY;
int damage = attackCount * player.level;
if (damage >= enemy.hp) {
int destroyTurn = (enemy.hp + player.level - 1) / player.level;
return destroyTurn;
}
return -1;
};
auto createRootNodes = [&](Nexts& nextNodes) {
Node* node = search.New();
node->state = server.state_;
node->evalScore = 0;
nextNodes.Add(node);
};
auto createNextNodes = [&](int depth, const Node* node, Nexts& nextNodes) {
if (node->state.turn >= T_Max) {
return;
}
{
int enemyY = FindEnemy(node->state);
if (enemyY >= 0) {
int destroyTurn = DestroyTurn(node->state, enemyY);
if (destroyTurn >= 0) {
Node* nextNode = search.New();
nextNode->state = node->state;
REP(dt, destroyTurn) {
nextNode->state.move(Action::S);
nextNode->state.attack();
nextNode->state.moveEnemy();
}
nextNode->evalScore = Eval(nextNode->state);
if (depth == 0) {
nextNode->firstAction = Action::S;
}
else {
nextNode->firstAction = node->firstAction;
}
nextNodes.Add(nextNode);
if (nextNode->evalScore > bestEvalScore) {
bestEvalScore = nextNode->evalScore;
bestAction = nextNode->firstAction;
}
}
}
}
for (Action action : {Action::L, Action::R}) {
State state = node->state;
REP(appendTurn, 4) {
State tmpState = state;
tmpState.move(action);
tmpState.attack();
tmpState.moveEnemy();
if (tmpState.gameOver) {
state.move(Action::S);
state.attack();
state.moveEnemy();
if (tmpState.gameOver) {
break;
}
}
else {
state.move(action);
state.attack();
state.moveEnemy();
int enemyY = FindEnemy(state);
if (enemyY >= 0) {
int destroyTurn = DestroyTurn(state, enemyY);
if (destroyTurn >= 0) {
Node* nextNode = search.New();
nextNode->state = state;
REP(dt, destroyTurn) {
nextNode->state.move(Action::S);
nextNode->state.attack();
nextNode->state.moveEnemy();
}
nextNode->evalScore = Eval(nextNode->state);
if (depth == 0) {
nextNode->firstAction = action;
}
else {
nextNode->firstAction = node->firstAction;
}
nextNodes.Add(nextNode);
if (nextNode->evalScore > bestEvalScore) {
bestEvalScore = nextNode->evalScore;
bestAction = nextNode->firstAction;
}
}
}
}
}
}
};
search.Run(16, 3, createRootNodes, createNextNodes);
server.Output(bestAction);
}
}
};
struct Main {
void Run(int argc, const char* argv[]) {
ChronoTimer timer;
server.InitInput(timer);
static Solver solver;
timer.StartMs(TIME_LIMIT);
solver.Run(timer);
cerr << "time " << timer.ElapseTimeMs() << endl;
server.Finalize();
}
};