結果

問題 No.5006 Hidden Maze
ユーザー maimai
提出日時 2022-06-12 17:31:26
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 12,849 bytes
コンパイル時間 2,990 ms
実行使用メモリ 22,876 KB
スコア 64,817
平均クエリ数 337.44
最終ジャッジ日時 2022-06-12 17:31:39
合計ジャッジ時間 12,815 ms
ジャッジサーバーID
(参考情報)
judge10 / judge11
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 97 RE * 3
権限があれば一括ダウンロードができます

ソースコード

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

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
// clang-format off
using namespace std;
using ll = long long int;
#define all(v) (v).begin(),(v).end()
#define repeat(cnt,l) for(typename remove_const<typename remove_reference<decltype(l)>::type>::type cnt={};(cnt)<(l);++(cnt))
#define rrepeat(cnt,l) for(auto cnt=(l)-1;0<=(cnt);--(cnt))
#define iterate(cnt,b,e) for(auto cnt=(b);(cnt)!=(e);++(cnt))
#define upto(cnt,b,e,step) for(auto cnt=(b);(cnt)<=(e);(cnt)+=(step))
#define downto(cnt,b,e,step) for(auto cnt=(b);(e)<=(cnt);(cnt)-=(step))
const long long MD = 998244353; const long double PI = 3.1415926535897932384626433832795L;
template<typename T1, typename T2> inline ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << '(' << p.first << ':' << p.second << ')';
    return o; }
template<typename T> inline T& chmax(T& to, const T& val) { return to = max(to, val); }
template<typename T> inline T& chmin(T& to, const T& val) { return to = min(to, val); }
void bye(string s, int code = 0) { cout << s << endl; exit(code); }
mt19937_64 randdev(8901016);
template<typename T, typename Random = decltype(randdev), typename enable_if<is_integral<T>::value>::type* = nullptr>
inline T rand(T l, T h, Random& rand = randdev) { return uniform_int_distribution<T>(l, h)(rand); }
template<typename T, typename Random = decltype(randdev), typename enable_if<is_floating_point<T>::value>::type* = nullptr>
inline T rand(T l, T h, Random& rand = randdev) { return uniform_real_distribution<T>(l, h)(rand); }template<typename T>
static ostream& operator<<(ostream& o, const std::vector<T>& v) {
o << "[ "; for(const auto& e : v) o<<e<<' '; return o << ']';
}
template <typename I> struct MyRangeFormat{ I b,e; MyRangeFormat(I _b, I _e):b(_b),e(_e){} };
template<typename I> static ostream& operator<<(ostream& o, const MyRangeFormat<I>& f) {
o << "[ "; iterate(i,f.b,f.e) o<<*i<<' '; return o << ']';
}
template <typename I> struct MyMatrixFormat{
const I& p; long long n, m;
MyMatrixFormat(const I& _p, long long _n, long long _m):p(_p),n(_n),m(_m){}
};
template<typename I> static ostream& operator<<(ostream& o, const MyMatrixFormat<I>& f) {
o<<'\n'; repeat(i,(f.n)) { repeat(j,f.m) o<<f.p[i][j]<<' '; o<<'\n'; }
return o;
}
struct LOG_t { ~LOG_t() { cout << endl; } };
#define LOG (LOG_t(),cout<<'L'<<__LINE__<<": ")
#define FMTA(m,w) (MyRangeFormat<decltype(m+0)>(m,m+w))
#define FMTR(b,e) (MyRangeFormat<decltype(e)>(b,e))
#define FMTV(v) FMTR(v.begin(),v.end())
#define FMTM(m,h,w) (MyMatrixFormat<decltype(m+0)>(m,h,w))
#if defined(_WIN32) || defined(_WIN64)
#define getc_x _getc_nolock
#define putc_x _putc_nolock
#elif defined(__GNUC__)
#define getc_x getc_unlocked
#define putc_x putc_unlocked
#else
#define getc_x getc
#define putc_x putc
#endif
class MaiScanner {
FILE* fp_;
constexpr bool isvisiblechar(char c) noexcept { return (0x21<=(c)&&(c)<=0x7E); }
public:
inline MaiScanner(FILE* fp):fp_(fp){}
template<typename T> void input_integer(T& var) noexcept {
var = 0; T sign = 1;
int cc = getc_x(fp_);
for (; cc < '0' || '9' < cc; cc = getc_x(fp_))
if (cc == '-') sign = -1;
for (; '0' <= cc && cc <= '9'; cc = getc_x(fp_))
var = (var << 3) + (var << 1) + cc - '0';
var = var * sign;
}
inline int c() noexcept { return getc_x(fp_); }
template<typename T, typename enable_if<is_integral<T>::value, nullptr_t>::type = nullptr>
inline MaiScanner& operator>>(T& var) noexcept { input_integer<T>(var); return *this; }
inline MaiScanner& operator>>(string& var) {
int cc = getc_x(fp_);
for (; !isvisiblechar(cc); cc = getc_x(fp_));
for (; isvisiblechar(cc); cc = getc_x(fp_))
var.push_back(cc);
return *this;
}
template<typename IT> inline void in(IT begin, IT end) { for (auto it = begin; it != end; ++it) *this >> *it; }
};
class MaiPrinter {
FILE* fp_;
public:
inline MaiPrinter(FILE* fp):fp_(fp){}
template<typename T>
void output_integer(T var) noexcept {
if (var == 0) { putc_x('0', fp_); return; }
if (var < 0)
putc_x('-', fp_),
var = -var;
char stack[32]; int stack_p = 0;
while (var)
stack[stack_p++] = '0' + (var % 10),
var /= 10;
while (stack_p)
putc_x(stack[--stack_p], fp_);
}
inline MaiPrinter& operator<<(char c) noexcept { putc_x(c, fp_); return *this; }
template<typename T, typename enable_if<is_integral<T>::value, nullptr_t>::type = nullptr>
inline MaiPrinter& operator<<(T var) noexcept { output_integer<T>(var); return *this; }
inline MaiPrinter& operator<<(const char* str_p) noexcept { while (*str_p) putc_x(*(str_p++), fp_); return *this; }
inline MaiPrinter& operator<<(const string& str) {
const char* p = str.c_str();
const char* l = p + str.size();
while (p < l) putc_x(*p++, fp_);
return *this;
}
template<typename IT> void join(IT begin, IT end, char sep = ' ') { for (bool b = 0; begin != end; ++begin, b = 1) b ? *this << sep << *begin :
      *this << *begin; }
};
MaiScanner scanner(stdin);
MaiPrinter printer(stdout);
// clang-format on
struct P {
using T = int;
T y, x;
inline explicit P(T _y, T _x) : y(_y), x(_x) {}
inline P() : y(0), x(0) {}
inline bool operator==(P p) const { return y == p.y && x == p.x; }
inline bool operator<(P p) const { return y == p.y ? x < p.x : y < p.y; }
inline P operator+(P p) const { return P(y + p.y, x + p.x); }
inline P operator-(P p) const { return P(y - p.y, x - p.x); }
inline P& operator+=(P p) {
y += p.y;
x += p.x;
return *this;
}
inline P& operator-=(P p) {
y -= p.y;
x -= p.x;
return *this;
}
inline P& operator*=(T m) {
y *= m;
x *= m;
return *this;
}
inline T distM(P p) const { return abs(y - p.y) + abs(x - p.x); }
inline T distC(P p) const { return max(abs(y - p.y), abs(x - p.x)); }
template <typename ITR>
ITR nearestM(ITR begin, ITR end) const {
if (begin == end)
return end;
T best = distM(*begin);
ITR besti = begin;
for (ITR it = begin; ++it, it != end;) {
T m = distM(*it);
if (best < m) {
best = m;
besti = it;
}
}
return besti;
}
};
inline ostream& operator<<(ostream& os, P p) {
os << '(' << p.y << ',' << p.x << ')';
return os;
}
// URDL
const P FourMoving[] = {P(-1, 0), P(0, 1), P(1, 0), P(0, -1)};
const P FiveMoving[] = {P(-1, 0), P(0, 1), P(1, 0), P(0, -1), P(0, 0)};
const P EightMoving[] = {P(-1, 0), P(0, 1), P(1, 0), P(0, -1),
P(-1, -1), P(-1, 1), P(1, -1), P(1, 1)};
inline P operator*(P::T m, P p) noexcept {
return P(m * p.y, m * p.x);
}
template <typename T>
// using T = int;
struct F {
int height, width;
vector<T> data;
explicit F(int h, int w) : height(h), width(w), data(h * w) {}
F() : F(1, 1) {}
inline T& operator()(int y, int x) { return data[x + y * width]; }
inline T& operator()(P p) { return data[p.x + p.y * width]; }
inline T operator()(int y, int x) const { return data[x + y * width]; }
inline T operator()(P p) const { return data[p.x + p.y * width]; }
inline bool safe(int y, int x) const { return 0 <= y && y < height && 0 <= x && x < width; }
inline bool safe(P p) const { return 0 <= p.y && p.y < height && 0 <= p.x && p.x < width; }
inline void fill(T e) { std::fill(data.begin(), data.end(), e); }
inline void resize(int h, int w) {
height = h;
width = w;
data.resize(h * w);
}
void print(ostream& os, int setw_arg = 4) {
for (int y = 0; y < height; ++y) {
for (int x = 0; x < width; ++x)
os << setw(setw_arg) << operator()(y, x) << ' ';
os << '\n';
}
}
};
//
#define USE_EMULATOR 0
constexpr int H = 20;
constexpr int W = 20;
int PH; // *1000 TODO: 1e9?
bool phTrue(int p) {
return rand(0, 1000) < p;
}
//
// <s>perecentage</s>
//
F<int> field_wall_r(H, W);
F<int> field_wall_d(H, W);
//
//
F<int> field_nowall_r(H, W);
F<int> field_nowall_d(H, W);
int& getW(P p, int d, F<int>& fd, F<int>& fr){
// assume: p + V[d] is not out of screen.
// URDL
if (d == 0) {
return fd(p - P{-1, 0});
} else if (d == 1) {
return fr(p);
} else if (d == 2) {
return fd(p);
} else { // if (d == 3) {
return fr(p - P{0, -1});
}
}
int& getWall(P p, int d){
return getW(p, d, field_wall_d, field_wall_r);
}
int& getNoWall(P p, int d){
return getW(p, d, field_nowall_d, field_nowall_r);
}
// bool existsWall(P p, int d) {
// return phTrue(getWall(p, d));
// }
//
F<int> emulator_wall_r(H, W);
F<int> emulator_wall_d(H, W);
void initEmulator(){
mt19937_64 mt(8901016);
repeat(i, 150) {
int y = uniform_int_distribution<int>(0, H-1)(mt);
int x = uniform_int_distribution<int>(0, W-1)(mt);
int d = uniform_int_distribution<int>(0, 1)(mt);
if (d) emulator_wall_d(y, x) = 1;
else emulator_wall_r(y, x) = 1;
}
//
emulator_wall_d(0,0) = 0;
string out[H*2];
repeat(i, H*2) out[i] = string(W*2, '.');
repeat(y, H) {
repeat(x, W) {
out[y*2+1][x*2+1] = '#';
if (emulator_wall_r(y, x))
out[y*2][x*2+1] = '#';
if (emulator_wall_d(y, x))
out[y*2+1][x*2] = '#';
}
}
repeat(i, H*2) LOG<<out[i];
}
int emulateAnswer(const vector<int>& commands) {
assert(!commands.empty());
for (auto c : commands) {
printer << "URDL"[c];
}
cout << endl;
P current = P{0, 0};
repeat(i, int(commands.size())) {
if (getW(current, commands[i], emulator_wall_d, emulator_wall_r)) {
LOG << "cmd=" << i << " is wall";
return i;
}
if (rand(0, 1000) < PH) {
LOG << "cmd=" << i << " unfortune";
return i;
}
current += FourMoving[commands[i]];
}
if (current == P{H-1, W-1}) {
LOG << "complete!";
return -1;
}
return commands.size();
}
//
vector<int> calcNewPath() {
const int inf = MD;
F<int> prev_dirs(H, W);
F<int /*bool*/> visited(H, W);
priority_queue<pair<int, P>> que;
que.emplace(0, P{0, 0});
visited.fill(inf);
visited(0, 0) = 0;
P goal = P{H-1, W-1};
while (!que.empty()) {
P p = que.top().second;
int w = -que.top().first;
que.pop();
if (visited(p) < w) continue;
repeat(vi, 4) {
auto v = FourMoving[vi];
auto p2 = p + v;
if (!visited.safe(p2))
continue;
int w2 = w + getWall(p, vi);
if (visited(p2) <= w2)
continue;
prev_dirs(p2) = vi;
visited(p2) = w2;
que.emplace(-w2, p2);
}
}
#if 1
// REDO:
if (visited(goal) == inf) return calcNewPath();
#else
while (!visited(goal)) {
goal.x -= 1;
if (goal.x < 0) {
goal.x = W-1;
goal.y -= 1;
}
}
#endif
vector<int> commands;
P current = goal;
while (!(current == P{0, 0})) {
auto vi = prev_dirs(current);
auto v = FourMoving[vi];
current -= v;
commands.push_back(vi);
}
reverse(all(commands));
return commands;
}
void feedbackWall(int& wall) {
// increment(pow) HIGH
// wall = (((wall >> 20) | 1) << 21) | (wall & ((1 << 20) - 1));
// chmin(wall, 1 << 26);
chmax(wall, 0);
wall += 100000;
}
void feedbackNoWall(int& wall) {
// wall &= (1 << 20) -1; // RESET HIGH because it's never wall
// wall += 1;
wall = 1;
}
void feedback(const vector<int>& commands, int length) {
P current = P{0, 0};
repeat(i, length) {
getNoWall(current, commands[i]) = true;
feedbackNoWall(getWall(current, commands[i]));
current += FourMoving[commands[i]];
}
if (getNoWall(current, commands[length])) {
#if USE_EMULATOR
LOG << current << "URDL"[commands[length]] << " stopeed but it never wall!";
#endif
} else {
int& w = getWall(current, commands[length]);
feedbackWall(w);
#if USE_EMULATOR
LOG << current << "URDL"[commands[length]] << " may be wall: potential=" << w;
#endif
}
}
//
int answerCommands(const vector<int>& commands) {
for (auto c : commands) {
printer << "URDL"[c];
}
cout << endl;
int available_length;
scanner >> available_length;
return available_length;
}
void init() {
// field_wall_d.fill(10);
// field_wall_r.fill(10);
field_wall_d.fill(2);
field_wall_r.fill(2);
}
bool solve() {
auto commands = calcNewPath();
#if USE_EMULATOR
int available_length = emulateAnswer(commands);
#else
int available_length = answerCommands(commands);
#endif
if (available_length < 0) return true;
feedback(commands, available_length);
return false;
}
int main() {
int h, w;
scanner >> h >> w >> PH;
PH *= 10;
#if USE_EMULATOR
initEmulator();
#endif
init();
repeat(turn, 1212) {
if (solve()) {
cerr << "turn=" << turn << endl;
break;
}
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0