結果

問題 No.5006 Hidden Maze
ユーザー bowwowforeach
提出日時 2022-06-12 17:59:14
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 345 ms / 2,000 ms
コード長 35,458 bytes
コンパイル時間 3,282 ms
実行使用メモリ 22,876 KB
スコア 76,326
平均クエリ数 237.74
最終ジャッジ日時 2022-06-12 18:00:45
合計ジャッジ時間 17,354 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge10
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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.001;
                        }
                        else if (wall.moveCount > wall.wallCount) {
                            if (p.x == 0 && p.y == 0) {
                            }
                            else {
                                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;
                        newCost += Random::GetDouble() * 0.00000001;
                        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;
    }
};
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0