結果
| 問題 | No.5006 Hidden Maze |
| ユーザー |
 plcherrim
|
| 提出日時 | 2022-06-12 17:49:34 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,432 bytes |
| コンパイル時間 | 2,708 ms |
| 実行使用メモリ | 37,648 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2022-06-12 17:49:51 |
| 合計ジャッジ時間 | 9,294 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
| testcase_84 | -- | - |
| testcase_85 | -- | - |
| testcase_86 | -- | - |
| testcase_87 | -- | - |
| testcase_88 | -- | - |
| testcase_89 | -- | - |
| testcase_90 | -- | - |
| testcase_91 | -- | - |
| testcase_92 | -- | - |
| testcase_93 | -- | - |
| testcase_94 | -- | - |
| testcase_95 | -- | - |
| testcase_96 | -- | - |
| testcase_97 | -- | - |
| testcase_98 | -- | - |
| testcase_99 | -- | - |
ソースコード
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
#pragma GCC diagnostic ignored "-Wunused-value"
#include<bits/stdc++.h>
using namespace std;
/*
* Additional Type Definition
*/
using ll=long long;
using ld=long double;
using ull=unsigned long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<ld>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vp=vector<pll>;
using tl2=tuple<ll,ll>;
using tl3=tuple<ll,ll,ll>;
using vs=vector<string>;
#define all(a) begin(a),end(a)
#define rall(a) rbegin(a),rend(a)
#define __LOOPSWITCH(_1, _2, _3, __LOOPSWITCH, ...) __LOOPSWITCH
#define rep(...) __LOOPSWITCH(__VA_ARGS__, __RANGE, __REP, __LOOP) (__VA_ARGS__)
#define rrep(...) __LOOPSWITCH(__VA_ARGS__, __RRANGE, __RREP, __LOOP) (__VA_ARGS__)
#define __LOOP(q) __LOOP2(q, __LINE__)
#define __LOOP2(q,l) __LOOP3(q,l)
#define __LOOP3(q,l) __REP(_lp ## l,q)
#define __REP(i,n) __RANGE(i,0,n)
#define __RANGE(i,a,n) for(ll i=((ll)a);i<((ll)n);++i)
#define __RREP(i,n) __RRANGE(i,0,n)
#define __RRANGE(i,a,n) for(ll i=((ll)(n)-1);i>=((ll)a);--i)
#define sz(a) ((ll)(a).size())
/*
* Constants
*/
constexpr ll LINF=1ll<<60;
constexpr int INF=1<<30;
constexpr double EPS=(1e-14);
constexpr ll MOD=998244353ll;
constexpr long double PI=3.14159265358979323846;
/*
* Utilities
*/
template<class T>constexpr bool chmax(T&a,T b){return a<b?a=b,1:0;}
template<class T>constexpr bool chmin(T&a,T b){return a>b?a=b,1:0;}
template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
namespace IO {
// container detection
template<typename T, typename _=void> struct is_container : false_type {};
template<> struct is_container<string> : false_type {};
template<typename...Ts> struct is_container_helper {};
template<typename T> struct is_container<T, conditional_t<
true, void, is_container_helper<
typename T::value_type, typename T::size_type, typename T::iterator,
decltype(declval<T>().size()),
decltype(declval<T>().begin()),
decltype(declval<T>().end()) >>> : public true_type {};
template<typename T,
typename enable_if<is_container<T>{}, nullptr_t>::type = nullptr,
char Separator = is_container<typename T::value_type>{} ? '\n' : ' ' >
constexpr ostream&operator<<(ostream&os, T t){
if(auto b=begin(t), e=end(t) ; !t.empty()) for(os<<(*b++);b!=e;os<<Separator<<(*b++)) ;
return os;
}
// output
template<class T, class...Ts> constexpr ostream& pargs(ostream&os, T&&t, Ts&&...args); // support clang
template<class S,class T>constexpr ostream&operator<<(ostream&os,pair<S,T>p){ return os<<'['<<p.first<<", "<<p.second<<']'; };
template<class...Ts>constexpr ostream&operator<<(ostream&os,tuple<Ts...>t){
return apply([&os](auto&&t,auto&&...args)->ostream&{return pargs(os, t, args...);}, t);
};
template<class T, class...Ts> constexpr ostream& pargs(ostream&os, T&&t, Ts&&...args) {
return ((os<<t)<<...<<(os<<' ', args));
}
template<class...Ts> constexpr ostream& out(Ts...args) { return pargs(cout, args...)<<'\n'; }
template<class...Ts> constexpr ostream& debug_f(Ts...args) { return pargs(cerr, args...)<<'\n'; }
#ifdef _DEBUG
template<class...Ts> constexpr ostream& debug(Ts...args) { return pargs(cerr, args...)<<'\n'; }
#else
#define debug(...) if(false)debug_f(__VA_ARGS__)
#endif
void Yn(bool f) { out(f?"Yes":"No"); }
// input
template<class T, class...Ts> constexpr istream& gargs(istream&is, T&&t, Ts&&...args) {
return ((is>>t)>>...>>args);
}
template<class S,class T>auto&operator>>(istream&is,pair<S,T>&p){return is>>p.first>>p.second;}
template<class...Ts>constexpr istream&operator>>(istream&is,tuple<Ts...>&t){
return apply([&is](auto&&t,auto&&...args)->istream&{return gargs(is, t, args...);}, t);
};
template<typename...S>auto&in(S&...s){return gargs(cin, s...);}
#define def(t,...) t __VA_ARGS__; in(__VA_ARGS__)
template<typename T, typename enable_if<is_container<T>{}, nullptr_t>::type = nullptr>
auto&operator>>(istream&is,T&t){for(auto&a:t)is>>a; return is;}
}
using namespace IO;
class Random {
public:
typedef uint_fast32_t result_type;
constexpr result_type operator()(){return operator()((ll)min(),(ll)max());}
static constexpr result_type max(){return numeric_limits<result_type>::max();}
static constexpr result_type min(){return 0;}
constexpr Random(const bool&isDeterministic):y(isDeterministic?2463534242:chrono::system_clock::now().time_since_epoch().count()){}
constexpr int operator()(int a,int b){return next()%(b-a)+a;}
constexpr ll operator()(ll a,ll b){return (((ull)next())<<32|next())%(b-a)+a;}
constexpr double operator()(double a,double b){return (b-a)*next()/4294967296.0+a;}
private:
result_type y;
constexpr result_type next(){return y^=(y^=(y^=y<<13)>>17)<<5;}
} Random(0);
class Timer {
#ifdef _DEBUG
static constexpr uint64_t ClocksPerMsec = 3587000;
#else
static constexpr uint64_t ClocksPerMsec = 2987000;
#endif
const uint64_t start,limit;
uint64_t getClocks() const{
unsigned int lo,hi;
__asm__ volatile ("rdtsc" : "=a" (lo), "=d" (hi));
return((uint64_t)hi<<32)|lo;
}
public:
Timer(uint64_t _limit=1970): start(getClocks()),limit(start+_limit*ClocksPerMsec) {}
uint64_t get() const{return (getClocks()-start)/ClocksPerMsec;}
operator bool()const{return getClocks()<limit;}
};
void wait(const int&msec){Timer tm(msec); while(tm);}
struct Mgr {
static const int TLE = 2000;
static inline Timer timer = Timer(TLE-20);
Mgr() {
ios_base::sync_with_stdio(0); cin.tie(0);
cout<<fixed<<setprecision(11);
cerr<<fixed<<setprecision(3);
}
~Mgr(){
debug_f(timer.get(), "ms")<<flush;
}
} _manager;
int main() {
map<char,int> enc;
enc['L']=0;
enc['U']=1;
enc['R']=2;
enc['D']=3;
string dec="LURD";
/**/
def(int,h,w,p);
deque<tuple<string,int,int>> q;
q.emplace_back("D",0,0);
q.emplace_back("R",0,0);
while(!q.empty()){
auto [s,fail,ret]=q.front();q.pop_front();
out(s);
def(int,t);
if(t==-1)break;
if(sz(s)==t){
rep(i,4)if(s.back()!=dec[i^2]){
q.emplace_back(s+dec[i], 0, t);
}
}else{
if(fail<3){
q.emplace_front(s,fail+1, max(ret, t));
}else{
q.emplace_back(s.substr(0,max(ret, t)), 0, max(ret, t));
}
}
}
}