#770807 (C++17) No.5006 Hidden Maze

提出ソース

結果

問題	No.5006 Hidden Maze
ユーザー	plcherrim
提出日時	2022-06-12 18:20:52
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	52 ms / 2,000 ms
コード長	6,229 bytes
コンパイル時間	2,426 ms
実行使用メモリ	22,868 KB
スコア	42,927
平均クエリ数	571.73
最終ジャッジ日時	2022-06-12 18:21:04
合計ジャッジ時間	10,255 ms
ジャッジサーバーID （参考情報）	judge10 / judge11
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	23 ms 21,928 KB
testcase_01	AC	49 ms 21,916 KB
testcase_02	AC	21 ms 21,880 KB
testcase_03	AC	24 ms 21,756 KB
testcase_04	AC	24 ms 22,612 KB
testcase_05	AC	41 ms 22,564 KB
testcase_06	AC	29 ms 22,868 KB
testcase_07	AC	27 ms 22,620 KB
testcase_08	AC	50 ms 21,856 KB
testcase_09	AC	28 ms 21,780 KB
testcase_10	AC	47 ms 21,928 KB
testcase_11	AC	48 ms 22,624 KB
testcase_12	AC	51 ms 22,588 KB
testcase_13	AC	22 ms 22,564 KB
testcase_14	AC	52 ms 21,756 KB
testcase_15	AC	21 ms 22,216 KB
testcase_16	AC	21 ms 22,216 KB
testcase_17	AC	21 ms 21,952 KB
testcase_18	AC	27 ms 21,940 KB
testcase_19	AC	20 ms 21,940 KB
testcase_20	AC	21 ms 22,004 KB
testcase_21	AC	41 ms 21,768 KB
testcase_22	AC	20 ms 21,756 KB
testcase_23	AC	21 ms 22,276 KB
testcase_24	AC	27 ms 22,216 KB
testcase_25	AC	51 ms 21,928 KB
testcase_26	AC	48 ms 21,892 KB
testcase_27	AC	48 ms 21,856 KB
testcase_28	AC	22 ms 21,940 KB
testcase_29	AC	29 ms 22,612 KB
testcase_30	AC	23 ms 22,216 KB
testcase_31	AC	47 ms 22,432 KB
testcase_32	AC	22 ms 22,264 KB
testcase_33	AC	35 ms 21,756 KB
testcase_34	AC	25 ms 21,940 KB
testcase_35	AC	35 ms 21,892 KB
testcase_36	AC	23 ms 21,940 KB
testcase_37	AC	36 ms 21,940 KB
testcase_38	AC	52 ms 21,992 KB
testcase_39	AC	25 ms 21,952 KB
testcase_40	AC	46 ms 21,892 KB
testcase_41	AC	47 ms 21,892 KB
testcase_42	AC	20 ms 22,588 KB
testcase_43	AC	45 ms 21,904 KB
testcase_44	AC	21 ms 21,892 KB
testcase_45	AC	50 ms 22,216 KB
testcase_46	AC	48 ms 21,892 KB
testcase_47	AC	19 ms 22,264 KB
testcase_48	AC	19 ms 22,620 KB
testcase_49	AC	48 ms 22,456 KB
testcase_50	AC	20 ms 21,768 KB
testcase_51	AC	21 ms 21,916 KB
testcase_52	AC	47 ms 21,940 KB
testcase_53	AC	46 ms 22,432 KB
testcase_54	AC	22 ms 22,564 KB
testcase_55	AC	45 ms 22,576 KB
testcase_56	AC	27 ms 21,916 KB
testcase_57	AC	52 ms 22,240 KB
testcase_58	AC	25 ms 21,892 KB
testcase_59	AC	21 ms 21,892 KB
testcase_60	AC	22 ms 21,892 KB
testcase_61	AC	45 ms 21,768 KB
testcase_62	AC	45 ms 21,904 KB
testcase_63	AC	30 ms 22,004 KB
testcase_64	AC	45 ms 21,904 KB
testcase_65	AC	19 ms 22,216 KB
testcase_66	AC	26 ms 21,916 KB
testcase_67	AC	18 ms 22,588 KB
testcase_68	AC	46 ms 22,564 KB
testcase_69	AC	19 ms 22,608 KB
testcase_70	AC	46 ms 21,880 KB
testcase_71	AC	45 ms 21,928 KB
testcase_72	AC	19 ms 21,992 KB
testcase_73	AC	45 ms 21,940 KB
testcase_74	AC	18 ms 21,768 KB
testcase_75	AC	45 ms 21,768 KB
testcase_76	AC	19 ms 21,892 KB
testcase_77	AC	45 ms 22,680 KB
testcase_78	AC	21 ms 21,940 KB
testcase_79	AC	50 ms 22,004 KB
testcase_80	AC	22 ms 21,892 KB
testcase_81	AC	21 ms 22,216 KB
testcase_82	AC	21 ms 21,880 KB
testcase_83	AC	18 ms 21,892 KB
testcase_84	AC	20 ms 22,600 KB
testcase_85	AC	45 ms 21,940 KB
testcase_86	AC	17 ms 21,928 KB
testcase_87	AC	25 ms 22,264 KB
testcase_88	AC	27 ms 22,216 KB
testcase_89	AC	46 ms 22,576 KB
testcase_90	AC	24 ms 22,600 KB
testcase_91	AC	33 ms 21,928 KB
testcase_92	AC	52 ms 21,904 KB
testcase_93	AC	22 ms 22,540 KB
testcase_94	AC	52 ms 22,252 KB
testcase_95	AC	22 ms 21,756 KB
testcase_96	AC	21 ms 21,600 KB
testcase_97	AC	48 ms 22,576 KB
testcase_98	AC	34 ms 22,004 KB
testcase_99	AC	22 ms 22,632 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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() {
	def(int,h,w,p);
	while(true){
		string init="DRDRDRDRDRDRDRDRDRDRDRDRDRDRDRDRDRDRDRUUDDLLRR";
		queue<pair<string, int>> q;
		q.emplace(init,0);
		while(!q.empty()){
			auto [s,mScore]=q.front(); q.pop();
			out(s)<<flush;
			def(int,t);
			if(t==-1) return 0;
			chmax(t,mScore);
			shuffle(s.begin()+t, s.end(), Random);
			q.emplace(s,t);
		}
	}
}

yukicoder

結果

テストケース

ソースコード