結果
| 問題 | No.5006 Hidden Maze |
| ユーザー |
 bowwowforeach
|
| 提出日時 | 2022-06-12 17:53:28 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 304 ms / 2,000 ms |
| コード長 | 35,231 bytes |
| コンパイル時間 | 3,344 ms |
| 実行使用メモリ | 22,868 KB |
| スコア | 74,970 |
| 平均クエリ数 | 251.30 |
| 最終ジャッジ日時 | 2022-06-12 17:53:46 |
| 合計ジャッジ時間 | 16,218 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 36 ms
21,992 KB |
| testcase_01 | AC | 53 ms
21,952 KB |
| testcase_02 | AC | 24 ms
21,880 KB |
| testcase_03 | AC | 52 ms
22,548 KB |
| testcase_04 | AC | 56 ms
21,880 KB |
| testcase_05 | AC | 123 ms
22,228 KB |
| testcase_06 | AC | 46 ms
22,240 KB |
| testcase_07 | AC | 25 ms
22,264 KB |
| testcase_08 | AC | 271 ms
21,916 KB |
| testcase_09 | AC | 304 ms
21,808 KB |
| testcase_10 | AC | 30 ms
22,692 KB |
| testcase_11 | AC | 39 ms
21,940 KB |
| testcase_12 | AC | 55 ms
21,792 KB |
| testcase_13 | AC | 51 ms
22,600 KB |
| testcase_14 | AC | 32 ms
21,892 KB |
| testcase_15 | AC | 38 ms
21,892 KB |
| testcase_16 | AC | 35 ms
21,928 KB |
| testcase_17 | AC | 151 ms
21,928 KB |
| testcase_18 | AC | 81 ms
21,992 KB |
| testcase_19 | AC | 24 ms
22,396 KB |
| testcase_20 | AC | 27 ms
22,444 KB |
| testcase_21 | AC | 28 ms
22,252 KB |
| testcase_22 | AC | 33 ms
21,940 KB |
| testcase_23 | AC | 45 ms
21,964 KB |
| testcase_24 | AC | 122 ms
21,904 KB |
| testcase_25 | AC | 186 ms
22,004 KB |
| testcase_26 | AC | 281 ms
22,600 KB |
| testcase_27 | AC | 101 ms
22,600 KB |
| testcase_28 | AC | 98 ms
21,940 KB |
| testcase_29 | AC | 272 ms
22,600 KB |
| testcase_30 | AC | 29 ms
21,892 KB |
| testcase_31 | AC | 31 ms
21,916 KB |
| testcase_32 | AC | 85 ms
22,004 KB |
| testcase_33 | AC | 38 ms
21,992 KB |
| testcase_34 | AC | 45 ms
21,780 KB |
| testcase_35 | AC | 54 ms
22,564 KB |
| testcase_36 | AC | 174 ms
21,780 KB |
| testcase_37 | AC | 183 ms
21,952 KB |
| testcase_38 | AC | 209 ms
21,928 KB |
| testcase_39 | AC | 24 ms
21,892 KB |
| testcase_40 | AC | 32 ms
22,276 KB |
| testcase_41 | AC | 42 ms
21,904 KB |
| testcase_42 | AC | 30 ms
22,612 KB |
| testcase_43 | AC | 42 ms
21,940 KB |
| testcase_44 | AC | 30 ms
22,288 KB |
| testcase_45 | AC | 57 ms
21,952 KB |
| testcase_46 | AC | 272 ms
21,940 KB |
| testcase_47 | AC | 51 ms
22,620 KB |
| testcase_48 | AC | 294 ms
22,600 KB |
| testcase_49 | AC | 277 ms
22,588 KB |
| testcase_50 | AC | 31 ms
21,940 KB |
| testcase_51 | AC | 33 ms
22,600 KB |
| testcase_52 | AC | 42 ms
21,904 KB |
| testcase_53 | AC | 55 ms
21,940 KB |
| testcase_54 | AC | 46 ms
21,916 KB |
| testcase_55 | AC | 48 ms
21,992 KB |
| testcase_56 | AC | 89 ms
21,880 KB |
| testcase_57 | AC | 32 ms
21,916 KB |
| testcase_58 | AC | 24 ms
21,904 KB |
| testcase_59 | AC | 20 ms
21,780 KB |
| testcase_60 | AC | 24 ms
22,408 KB |
| testcase_61 | AC | 43 ms
21,792 KB |
| testcase_62 | AC | 32 ms
22,004 KB |
| testcase_63 | AC | 45 ms
21,928 KB |
| testcase_64 | AC | 95 ms
21,904 KB |
| testcase_65 | AC | 23 ms
21,928 KB |
| testcase_66 | AC | 39 ms
21,768 KB |
| testcase_67 | AC | 28 ms
22,444 KB |
| testcase_68 | AC | 210 ms
21,940 KB |
| testcase_69 | AC | 26 ms
22,588 KB |
| testcase_70 | AC | 21 ms
22,612 KB |
| testcase_71 | AC | 29 ms
22,156 KB |
| testcase_72 | AC | 21 ms
22,868 KB |
| testcase_73 | AC | 30 ms
22,276 KB |
| testcase_74 | AC | 26 ms
22,228 KB |
| testcase_75 | AC | 33 ms
22,228 KB |
| testcase_76 | AC | 22 ms
21,768 KB |
| testcase_77 | AC | 265 ms
21,892 KB |
| testcase_78 | AC | 45 ms
21,964 KB |
| testcase_79 | AC | 284 ms
21,780 KB |
| testcase_80 | AC | 31 ms
21,904 KB |
| testcase_81 | AC | 40 ms
22,456 KB |
| testcase_82 | AC | 54 ms
21,928 KB |
| testcase_83 | AC | 28 ms
21,892 KB |
| testcase_84 | AC | 142 ms
21,768 KB |
| testcase_85 | AC | 110 ms
21,768 KB |
| testcase_86 | AC | 20 ms
21,992 KB |
| testcase_87 | AC | 158 ms
22,704 KB |
| testcase_88 | AC | 122 ms
21,928 KB |
| testcase_89 | AC | 270 ms
21,892 KB |
| testcase_90 | AC | 21 ms
21,892 KB |
| testcase_91 | AC | 45 ms
22,456 KB |
| testcase_92 | AC | 36 ms
21,892 KB |
| testcase_93 | AC | 54 ms
22,264 KB |
| testcase_94 | AC | 91 ms
22,004 KB |
| testcase_95 | AC | 26 ms
21,964 KB |
| testcase_96 | AC | 24 ms
22,608 KB |
| testcase_97 | AC | 271 ms
22,004 KB |
| testcase_98 | AC | 243 ms
21,964 KB |
| testcase_99 | AC | 149 ms
22,004 KB |
ソースコード
#define CODETEST 0
#define OPTUNE 0
#define PERFORMANCE 0
#define EVAL 0
#define TIME_LIMIT (1950)
#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
#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"
#endif
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
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()
#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> inline void chmin(T& a, T b) { if (b < a) { a = b; } }
template <class T> inline void chmax(T& a, T b) { if (a < b) { a = b; } }
template <class T> inline constexpr T square(T v) { return v * v; }
using TimePoint = chrono::steady_clock::time_point;
struct Timer {
private:
TimePoint startTime_;
TimePoint endTime_;
public:
inline void Init() {
startTime_ = chrono::steady_clock::now();
}
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::steady_clock::now() >= endTime_;
}
inline int ElapseTimeMs() const {
return (int)chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - startTime_).count();
}
inline int ElapseTimeUs() const {
return (int)chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now() - startTime_).count();
}
inline int LeftToUS(const TimePoint& limit) const {
return (int)chrono::duration_cast<chrono::microseconds>(limit - chrono::steady_clock::now()).count();
}
inline double NowRate() const {
return (chrono::steady_clock::now() - startTime_).count() / (double)(endTime_ - startTime_).count();
}
inline TimePoint Now() const {
return chrono::steady_clock::now();
}
inline TimePoint EndTime() const {
return endTime_;
}
TimePoint GetLimitTimePointUs(int limit) const {
return startTime_ + chrono::microseconds(limit);
}
};
Timer timer;
template <class T>
void InstanceRun(int argc, const char* argv[]) {
timer.Init();
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 ValidateException {
stringstream ss;
ValidateException(const char* function, int line, const char* msg) {
ss << "**** ABORT **** : " << function << " " << line << " " << msg;
}
};
struct MemoryException {};
#define VALIDATE_ABORT()
#define VALIDATE_ASSERT(exp)
#define VABORT() VALIDATE_ABORT()
#define VASSERT(exp) VALIDATE_ASSERT(exp)
#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;
template <class A, class B>
struct pr {
union {
A a;
A key;
A first;
A x;
};
union {
B b;
B value;
B second;
B y;
};
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;
}
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_pod<pint>::value, "not pod");
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; };
template <class A, class B, class C>
struct tr {
union {
A a;
A first;
A x;
};
union {
B b;
B second;
B y;
};
union {
C c;
C third;
C z;
};
bool operator == (tr const& r) const { return a == r.a && b == r.b && c == r.c; }
bool operator != (tr const& r) const { return !((*this) == r); }
bool operator < (tr const& r) const {
if (a == r.a) {
if (b == r.b) {
return c < r.c;
}
return b < r.b;
}
return a < r.a;
}
tr operator + (tr v) const { return tr(x, y, z) += v; }
tr operator - (tr v) const { return tr(x, y, z) -= v; }
tr operator - () const { return tr{ -x, -y, -z }; }
tr& operator += (tr v) {
x += v.x;
y += v.y;
z += v.z;
return *this;
}
tr& operator -= (tr v) {
x -= v.x;
y -= v.y;
z -= v.z;
return *this;
}
friend istream& operator>>(istream& is, tr& p) {
is >> p.a >> p.b >> p.c;
return is;
}
friend ostream& operator<<(ostream& os, tr const& p) {
os << p.a << " " << p.b << " " << p.c;
return os;
}
};
using tint = tr<int, int, int>;
static_assert(is_pod<tint>::value, "not pod");
template <class T>
struct arr : public vector<T> {
static arr<arr<T>> D2(int y, int x, T value) {
return arr<arr<T>>(y, arr<T>(x, value));
}
static arr<arr<arr<T>>> D3(int z, int y, int x, T value) {
return arr<arr<arr<T>>>(z, arr<arr<T>>(y, arr<T>(x, value)));
}
static arr<arr<arr<arr<T>>>> D4(int w, int z, int y, int x, T value) {
return arr<arr<arr<arr<T>>>>(w, arr<arr<arr<T>>>(z, arr<arr<T>>(y, arr<T>(x, value))));
}
static arr<T> Iota(int N, int value = 0) {
auto r = arr<T>(N);
r.iota(value);
return r;
}
arr() {}
arr(initializer_list<T> il) : vector<T>(il) {}
explicit arr(int n) : vector<T>(n) {}
arr(int n, T v) : vector<T>(n, v) {}
arr(const arr& r) : vector<T>(r) {}
arr(arr&& r) : vector<T>(move(r)) {}
arr& operator = (const arr& r) {
vector<T>::operator = (r);
return *this;
}
arr& operator = (arr&& r) {
vector<T>::operator = (move(r));
return *this;
}
T& operator()(int i) { return (*this)[i]; }
T const& operator()(int i) const { return (*this)[i]; }
void init(int n, T v = T()) {
this->assign(n, v);
}
int sz() const { return (int)this->size(); }
void pb(T v) { this->push_back(v); }
void sort() { std::sort(this->begin(), this->end()); }
template <class F> void sort(F&& f) { std::sort(this->begin(), this->end(), f); }
void rsort() { std::sort(this->begin(), this->end(), greater<T>()); }
void reverse() { std::reverse(this->begin(), this->end()); }
void unique_erase() { this->erase(std::unique(this->begin(), this->end()), this->end()); }
bool next_permutation() { return std::next_permutation(this->begin(), this->end()); }
int lower_bound(T const& v, function<bool(T, T)> p) { return std::lower_bound(this->begin(), this->end(), v, p) - this->begin(); }
int lower_bound(T const& v) { return std::lower_bound(this->begin(), this->end(), v) - this->begin(); }
int upper_bound(T const& v, function<bool(T, T)> p) { return std::upper_bound(this->begin(), this->end(), v, p) - this->begin(); }
int upper_bound(T const& v) { return std::upper_bound(this->begin(), this->end(), v) - this->begin(); }
void iota(T startValue = 0) { ::iota(this->begin(), this->end(), startValue); }
void fill(T v) { ::fill(this->begin(), this->end(), v); }
int find_sorted_nearest(T const& v) {
int i = this->lower_bound(v);
if (i >= sz()) {
--i;
}
else if ((*this)[i] != v) {
int p = i - 1;
if (p >= 0) {
int id = abs((*this)[i] - v);
int pd = abs((*this)[p] - v);
if (pd < id) {
i = p;
}
}
}
return i;
}
int find_sorted(T const& v) {
int i = this->lower_bound(v);
if (i >= sz()) {
return -1;
}
if ((*this)[i] != v) {
return -1;
}
return i;
}
int find(T const& v) const {
auto it = std::find(this->begin(), this->end(), v);
if (it == this->end()) {
return -1;
}
return (int)(it - this->begin());
}
bool is_contains(T const& v) const {
auto it = std::find(this->begin(), this->end(), v);
if (it == this->end()) {
return false;
}
return true;
}
template <class P>
void remove_if_erase(P&& predicate) { this->erase(std::remove_if(this->begin(), this->end(), predicate), this->end()); }
void slide_remove(int i) {
(*this)[i] = (*this)[sz() - 1];
this->pop_back();
}
void remove_idx(int i) {
this->erase(this->begin() + i);
}
void insert_idx(int i, const T& v) {
this->insert(this->begin() + i, v);
}
int findGE(const T& v) {
return lower_bound(v);
}
int findG(const T& v) {
return upper_bound(v);
}
int findLE(const T& v) {
return upper_bound(v) - 1;
}
int findL(const T& v) {
return lower_bound(v) - 1;
}
friend ostream& operator<<(ostream& os, const arr<T>& p) {
if (p.empty()) {
return os;
}
os << p[0];
FOR(i, 1, p.size()) {
os << " " << p[i];
}
return os;
}
};
using ints = arr<int>;
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;
}
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;
}
};
template <class T, int CAPACITY>
using CapQue = CapacityQueue<T, CAPACITY>;
template <class T, int CAPACITY>
class CapacityArray {
static_assert(is_trivially_copyable<T>::value);
private:
array<T, CAPACITY> array_ = {};
int count_ = 0;
public:
CapacityArray() {
}
explicit CapacityArray(int count) {
resize(count);
}
inline void clear() {
count_ = 0;
}
inline void Clear() {
clear();
}
inline void resize(int count) {
count_ = count;
}
inline void Resize(int count) {
resize(count);
}
inline void assign(int count, const T& e) {
count_ = count;
for (int i = 0; i < count; ++i) {
array_[i] = e;
}
}
inline T* PushBack() {
return &array_[count_++];
}
inline void push_back(const T& e) {
array_[count_++] = e;
}
inline void PushBack(const T& e) {
push_back(e);
}
inline void pop_back() {
--count_;
}
inline void PopBack() {
pop_back();
}
inline void RemoveSlide(int i) {
array_[i] = array_[count_ - 1];
--count_;
}
inline int GetCount() const {
return count_;
}
inline int size() const {
return count_;
}
inline int sz() const {
return count_;
}
inline bool empty() const {
return count_ == 0;
}
inline T& operator[](int index) {
return array_[index];
}
inline const T& operator[](int index) const {
return array_[index];
}
inline auto begin() -> decltype(array_.begin()) {
return array_.begin();
}
inline auto end() -> decltype(array_.begin()) {
return array_.begin() + count_;
}
inline auto begin() const -> decltype(array_.begin()) {
return array_.begin();
}
inline auto end() const -> decltype(array_.begin()) {
return array_.begin() + count_;
}
inline bool IsContain(const T& value) const {
for (const auto& v : *this) {
if (v == value) {
return true;
}
}
return false;
}
inline void MemInsert(int index, const T* mem, int count) {
if (index == count_) {
memcpy(array_.data() + index, mem, sizeof(T) * count);
count_ += count;
}
else {
memmove(array_.data() + index + count, array_.data() + index, sizeof(T) * (count_ - index));
memcpy(array_.data() + index, mem, sizeof(T) * count);
count_ += count;
}
}
void insert(int index, const T& value) {
MemInsert(index, &value, 1);
}
};
template <class T, int CAPACITY>
using CapArr = CapacityArray<T, CAPACITY>;
template <int CAPACITY>
struct CapacitySet {
private:
CapacityArray<int, CAPACITY> elemens;
array<int, CAPACITY> indexTable;
public:
CapacitySet() {
fill(indexTable.begin(), indexTable.end(), -1);
}
void Clear() {
elemens.Clear();
fill(indexTable.begin(), indexTable.end(), -1);
}
inline void Add(int ai) {
indexTable[ai] = elemens.GetCount();
elemens.PushBack(ai);
}
inline void ForceAdd(int ai) {
if (indexTable[ai] >= 0) {
return;
}
indexTable[ai] = elemens.GetCount();
elemens.PushBack(ai);
}
inline void Remove(int ai) {
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;
}
inline 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;
}
inline bool IsContain(int ai) const {
return indexTable[ai] >= 0;
}
inline int GetCount() const {
return elemens.GetCount();
}
inline int size() const {
return elemens.GetCount();
}
inline int At(int index) const {
return elemens[index];
}
inline int operator[](int index) const {
return elemens[index];
}
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();
}
};
struct SizeSet {
private:
vector<int> elemens;
vector<int> indexTable;
public:
void InitSize(int size) {
elemens.clear();
elemens.reserve(size);
indexTable.assign(size, -1);
}
void Clear() {
elemens.clear();
indexTable.assign(indexTable.size(), -1);
}
inline void Add(int ai) {
indexTable[ai] = (int)elemens.size();
elemens.emplace_back(ai);
}
inline void ForceAdd(int ai) {
if (indexTable[ai] >= 0) {
return;
}
indexTable[ai] = (int)elemens.size();
elemens.emplace_back(ai);
}
inline void Remove(int ai) {
int removeIndex = indexTable[ai];
int lastIndex = (int)elemens.size() - 1;
if (removeIndex != lastIndex) {
elemens[removeIndex] = elemens[lastIndex];
indexTable[elemens[lastIndex]] = removeIndex;
}
elemens.pop_back();
indexTable[ai] = -1;
}
inline void ForceRemove(int ai) {
if (indexTable[ai] < 0) {
return;
}
int removeIndex = indexTable[ai];
int lastIndex = (int)elemens.size() - 1;
if (removeIndex != lastIndex) {
elemens[removeIndex] = elemens[lastIndex];
indexTable[elemens[lastIndex]] = removeIndex;
}
elemens.pop_back();
indexTable[ai] = -1;
}
inline bool IsContain(int ai) const {
return indexTable[ai] >= 0;
}
inline int GetCount() const {
return (int)elemens.size();
}
inline int At(int index) const {
return elemens[index];
}
inline int operator[](int index) const {
return elemens[index];
}
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, class COMPARERE>
struct PriorityQueue : public priority_queue<T, vector<T>, COMPARERE> {
template <class D>
void Cut(int size, D&& deleter) {
if ((int)this->c.size() > size) {
int orgSize = (int)this->c.size();
for (int i = size; i < orgSize; ++i) {
deleter(this->c[i]);
}
this->c.resize(size);
}
}
vector<T>& Container() {
return this->c;
}
void Cut(int size) {
if ((int)this->c.size() > size) {
this->c.resize(size);
}
}
void Clear() {
this->c.clear();
}
};
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];
}
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;
}
};
struct CheckMapD {
private:
vector<u32> checked_;
u32 mark_ = 1;
public:
void SetSize(int size) {
checked_.resize(size, mark_);
}
void Clear() {
++mark_;
if (mark_ == 0) {
checked_.assign(checked_.size(), 0);
++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;
}
};
template <class T>
struct CheckMapDataD {
private:
vector<T> data_;
vector<u32> checked_;
u32 mark_ = 1;
public:
void SetSize(int size) {
checked_.resize(size, mark_);
data_.resize(size);
}
void Clear() {
++mark_;
if (mark_ == 0) {
checked_.assign(checked_.size(), 0);
++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];
}
};
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} };
inline Dir RotateRight(Dir d) {
return Dir(((int)d + 1) % 4);
}
inline Dir RotateLeft(Dir d) {
return Dir(((int)d + 3) % 4);
}
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 const 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 <class T, int CAP>
struct CCA {
T ar[CAP];
int s;
inline constexpr void push(const T& v) {
ar[s++] = v;
}
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 {
return ar[i];
}
inline constexpr const T& operator [](int i) const {
return ar[i];
}
};
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 AROUND_COUNT>
struct AroundMapD {
using CA = CCA<int, AROUND_COUNT>;
vector<CA> table_;
int width_ = 1;
void Init(int width, int height, const pint (&aroundDirs)[AROUND_COUNT]) {
width_ = width;
int count = width * height;
table_.resize(count);
REP(i, count) {
pint p = { i % width, i / width };
for (const pint& a : aroundDirs) {
pint n = p + a;
if (n.a >= 0 && n.a < width &&
n.b >= 0 && n.b < height) {
table_[i].push(n.a + n.b * width);
}
}
}
}
inline const CA& operator[](int i) const {
return table_[i];
}
inline const CA& operator[](const pint& p) const {
return table_[p.x + p.y * width_];
}
};
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];
}
};
#include <cstdint>
struct XorShift {
uint32_t x;
uint32_t y;
uint32_t z;
uint32_t w;
inline XorShift(uint32_t seed = 0) {
x = 123456789;
y = 362436069;
z = 521288629;
w = 88675123 + seed;
}
inline uint32_t operator()() {
uint32_t t = x ^ (x << 11);
x = y;
y = z;
z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
inline uint32_t operator()(uint32_t l, uint32_t r) {
return ((*this)() % (r - l)) + l;
}
inline uint32_t operator()(uint32_t r) {
return (*this)() % r;
}
};
struct Xor64 {
using result_type = uint64_t;
static constexpr result_type min() { return 0; }
static constexpr result_type max() { return UINT64_MAX; }
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;
}
};
struct Xor32 {
using result_type = uint32_t;
static constexpr result_type min() { return 0; }
static constexpr result_type max() { return UINT32_MAX; }
uint32_t x;
inline Xor32(uint32_t seed = 0) {
x = 2463534242 + seed;
}
inline uint32_t operator ()(void) {
x = x ^ (x << 13);
x = x ^ (x >> 17);
return x = x ^ (x << 5);
}
inline uint32_t operator()(uint32_t l, uint32_t r) {
return ((*this)() % (r - l)) + l;
}
inline uint32_t operator()(uint32_t r) {
return (*this)() % r;
}
};
struct Random {
static inline Xor32& Instnce() {
static Xor32 x;
return x;
}
static inline uint32_t Get() {
return Instnce()();
}
static inline uint32_t Get(uint32_t l, uint32_t r) {
return Instnce()(l, r);
}
static inline uint32_t Get(uint32_t r) {
return Instnce()(r);
}
static inline void Get2(uint32_t N, uint32_t& a, uint32_t& b) {
VASSERT(N >= 2);
a = Get(N);
b = Get(N - 1);
if (b >= a) {
++b;
}
}
static inline double GetDouble() {
return Get() / (double)UINT32_MAX;
}
static inline double GetDouble(double l, double r) {
return l + GetDouble() * (r - l);
}
};
#define REGIST_PARAM(name, type, defaultValue) type name = defaultValue;
constexpr
struct {
} HYPER_PARAM;
auto& HP = HYPER_PARAM;
double ParamValue(double x, double a, double e) {
return a * pow(x, e);
}
constexpr int W = 20;
constexpr int H = 20;
constexpr int WH = W * H;
constexpr int L_MAX = 400;
constexpr int T_MAX = 1000;
AroundMapS<W, H, 4> AroundMap(Around4);
DirMapS<W, H, 4> DirMap(Around4);
template <int W, int H>
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);
}
};
template <class T>
using Grid = array<T, WH>;
GridSystemS<W, H> gs;
struct Action {
CapArr<Dir, T_MAX> dirs;
};
struct Wall {
int moveCount = 0;
int wallCount = 0;
double noWallRate = 1.0;
void CanMoved() {
moveCount++;
}
void NotMoved(double failProb) {
moveCount++;
wallCount++;
noWallRate *= failProb;
}
double CanMoveRate(double failProb) const {
if (moveCount > wallCount) {
return 1;
}
return noWallRate;
}
double WallRate(double failProb) const {
if (moveCount > wallCount) {
return 0;
}
return 1.0 - noWallRate;
}
};
struct IOServer {
array<array<Wall, W - 1>, H> wallsH = {};
array<array<Wall, H - 1>, W> wallsV = {};
double failProb = 0;
Wall& GetWall(const pint& p, Dir dir) {
pint nextP = p + Around4[(int)dir];
if (nextP.x < 0 || nextP.x >= W || nextP.y < 0 || nextP.y >= H) {
VABORT();
}
if (dir == Dir::L || dir == Dir::R) {
int left = min(p.x, nextP.x);
return wallsH[p.y][left];
}
else {
int top = min(p.y, nextP.y);
return wallsV[p.x][top];
}
}
const Wall& GetWall(const pint& p, Dir dir) const {
return ((IOServer&)(*this)).GetWall(p, dir);
}
bool CanMove(const pint& p, Dir dir, double& canMoveRate) const {
pint nextP = p + Around4[(int)dir];
if (nextP.x < 0 || nextP.x >= W || nextP.y < 0 || nextP.y >= H) {
return false;
}
auto& wall = GetWall(p, dir);
canMoveRate = wall.CanMoveRate(failProb);
return true;
}
void SetResult(const pint& p, Dir dir, bool successMove) {
pint nextP = p + Around4[(int)dir];
if (nextP.x < 0 || nextP.x >= W || nextP.y < 0 || nextP.y >= H) {
VABORT();
}
auto& wall = GetWall(p, dir);
if (successMove) {
wall.CanMoved();
}
else {
wall.NotMoved(failProb);
}
}
void Input(int argc, const char* argv[]) {
auto& is = cin;
int dummy = 0;
is >> dummy >> dummy;
int ip = 0;
is >> ip;
failProb = ip / 100.0;
}
void Output(const CapArr<Dir, T_MAX>& dirs) {
{
static string str;
str.clear();
REP(i, dirs.size()) {
auto dir = dirs[i];
str += DirToChar(dir);
}
auto& os = cout;
auto& is = cin;
os << str << endl;
int ret = 0;
is >> ret;
if (ret < 0) {
exit(0);
return;
}
pint p = {};
REP(i, ret) {
Dir dir = dirs[i];
SetResult(p, dir, true);
p += Around4[(int)dir];
}
if (ret < dirs.size()) {
Dir dir = dirs[ret];
SetResult(p, dir, false);
}
}
}
};
IOServer server;
const double D_MAX = sqrt(square(W - 1) + square(H - 1));
struct Solver {
struct Node {
pint p = {};
CapArr<Dir, T_MAX> dirs = {};
double cost = 0;
Node() {};
Node(const pint& p_, const CapArr<Dir, T_MAX>& dirs_, double cost_) {
p = p_;
dirs = dirs_;
cost = cost_;
}
};
struct Comparer {
bool operator()(const Node& a, const Node& b) {
return a.cost > b.cost;
}
};
void Run() {
PriorityQueue<Node, Comparer> que;
array<array<double, W>, H> costMap;
CapArr<Dir, T_MAX> bestDirs;
double bestCost = 999999999;
REP(t, T_MAX + 2) {
que.Clear();
REP(y, H) {
REP(x, W) {
costMap[y][x] = 999999999;
}
}
bestDirs.clear();
{
Node node = Node(pint{}, {}, 0);
que.push(node);
costMap[0][0] = 0;
}
while (!que.empty()) {
Node node = que.top();
que.pop();
const pint p = node.p;
if (node.cost > costMap[p.y][p.x]) {
continue;
}
REP(di, 4) {
pint np = node.p + Around4[di];
Dir dir = Dir4[di];
double canMoveRate = 0;
if (server.CanMove(node.p, dir, canMoveRate))
{
CapArr<Dir, T_MAX> newDirs = node.dirs;
newDirs.push_back(dir);
double newCost = node.cost + 1;
const auto& wall = server.GetWall(p, dir);
if (wall.moveCount == 0) {
newCost -= 0.05;
}
else if (wall.moveCount > wall.wallCount) {
newCost -= 0.1;
}
else {
if (wall.wallCount) {
newCost += square((double)wall.wallCount) / 20.0;
}
}
double dist = sqrt(square(np.x - (W - 1)) + square(np.y - (H - 1)));
newCost += dist * 0.000001;
Node newNode = Node(np, newDirs, newCost);
if (newNode.cost < costMap[np.y][np.x]) {
if (np.y == H - 1 && np.x == W - 1) {
if (bestDirs.empty() || newNode.cost < bestCost) {
bestCost = newNode.cost;
bestDirs = newNode.dirs;
}
}
else {
if (newNode.dirs.size() < L_MAX) {
que.push(newNode);
costMap[np.y][np.x] = newNode.cost;
}
}
}
}
}
}
server.Output(bestDirs);
}
}
};
struct Main {
void Run(int argc, const char* argv[]) {
try {
timer.StartMs(TIME_LIMIT);
server.Input(argc, argv);
Solver* solver = new Solver;
solver->Run();
}
catch (ValidateException& e) {
(void)e;
}
cerr << "time " << timer.ElapseTimeMs() << endl;
}
};