結果
問題 | No.5006 Hidden Maze |
ユーザー |
|
提出日時 | 2022-06-12 14:54:21 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 123 ms / 2,000 ms |
コード長 | 8,057 bytes |
コンパイル時間 | 2,738 ms |
実行使用メモリ | 22,876 KB |
スコア | 65,747 |
平均クエリ数 | 343.53 |
最終ジャッジ日時 | 2022-06-12 14:54:46 |
合計ジャッジ時間 | 11,791 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #pragma GCC target ("avx2") #include <iostream> #include <iomanip> #include <vector> #include <algorithm> #include <utility> #include <string> #include <queue> #include <stack> #include <unordered_set> #include <random> #include <cmath> #include <cassert> #include <x86intrin.h> struct xorshift64 { unsigned long long int x = 88172645463325252ULL; inline unsigned short nextUShort() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline unsigned int nextUShortMod(unsigned long long int mod) { x = x ^ (x << 7); x = x ^ (x >> 9); return ((x & 0x0000ffffffffffff) * mod) >> 48; } inline unsigned int nextUInt() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline unsigned int nextUIntMod(unsigned long long int mod) { x = x ^ (x << 7); x = x ^ (x >> 9); return ((x & 0x00000000ffffffff) * mod) >> 32; } inline unsigned long long int nextULL() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline double nextDouble() { x = x ^ (x << 7); x = x ^ (x >> 9); return (double)x * 5.42101086242752217e-20; } }; struct timer { double t = 0.0; double lastStop = 0.0; bool stopped = false; timer() { restart(); } inline void restart() { t = now(); stopped = false; } inline void start() { if (stopped) { t += now() - lastStop; stopped = false; } } inline void stop() { if (!stopped) { lastStop = now(); stopped = true; } } inline double time() { if (stopped) return lastStop - t; else return now() - t; } inline double now() { unsigned long long l, h; __asm__ ("rdtsc" : "=a"(l), "=d"(h)); #ifdef LOCAL return (double)(l | h << 32) * 2.857142857142857e-10; // 1 / 3.5e9, for local (Ryzen 9 3950X) #else //return (double)(l | h << 32) * 3.5714285714285715e-10; // 1 / 2.8e9, for AWS EC2 C3 (Xeon E5-2680 v2) //return (double)(l | h << 32) * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C4 (Xeon E5-2666 v3) return (double)(l | h << 32) * 3.333333333333333e-10; // 1 / 3.0e9, for AWS EC2 C5 (Xeon Platinum 8124M / Xeon Platinum 8275CL) #endif } }; using namespace std; typedef long long int ll; typedef unsigned long long int ull; typedef pair<int, int> Pii; const ll mod = 1000000007; timer theTimer; xorshift64 theRandom; mt19937 theMersenne(1); // hyper parameters // structs struct { const vector<int> x = { -1, 1, 0, 0}; const vector<int> y = { 0, 0, -1, 1}; const vector<char> c = {'U', 'D', 'L', 'R'}; } delta; // constants constexpr int h = 20; constexpr int w = 20; constexpr int turn_limit = 1001; constexpr int start_x = 0; constexpr int start_y = 0; constexpr int finish_x = h-1; constexpr int finish_y = w-1; vector<double> edge_cost; // inputs double p; // outputs string ans; // internals vector<vector<bool> > edge_passable_vertical(h-1, vector<bool>(w)); vector<vector<bool> > edge_passable_horizontal(h, vector<bool>(w-1)); vector<vector<int> > edge_wall_hit_count_vertical(h-1, vector<int>(w)); vector<vector<int> > edge_wall_hit_count_horizontal(h, vector<int>(w-1)); bool within_board(int x, int y) { return 0 <= x && x < h && 0 <= y && y < w; } void receive_first_input() { int _h, _w, _p; cin >> _h >> _w >> _p; p = (double) _p * 0.01; } int answer(string ans) { cout << ans << endl; int res; cin >> res; return res; } void init() { edge_cost = vector<double>(turn_limit); edge_cost[0] = 1.0; for (int i = 1; i < turn_limit; i++) { edge_cost[i] = edge_cost[i-1] * (1.0 / p); } } void solve() { for (int turn_count = 0; turn_count < turn_limit; turn_count++) { // find next path string next_path = ""; { vector<vector<char> > prev_dir(h, vector<char>(w)); // direction to start vector<vector<bool> > visited(h, vector<bool>(w)); priority_queue<tuple<double, int, int, char>, vector<tuple<double, int, int, char> >, greater<tuple<double, int, int, char> > > que; que.emplace(0, start_x, start_y, '.'); while (!que.empty()) { auto [current_cost, px, py, dir] = que.top(); que.pop(); if (visited[px][py]) continue; visited[px][py] = true; prev_dir[px][py] = dir; if (px == finish_x && py == finish_y) break; for (int d = 0; d < 4; d++) { if (within_board(px + delta.x[d], py + delta.y[d]) && !visited[px + delta.x[d]][py + delta.y[d]]) { if (d & 2) { // horizontal movement assert(delta.x[d] == 0); assert(abs(delta.y[d]) == 1); int wall_y = min(py, py + delta.y[d]); if (edge_passable_horizontal[px + delta.x[d]][wall_y]) { que.emplace(current_cost, px + delta.x[d], py + delta.y[d], delta.c[d ^ 1]); // ^ 1: 180 deg flip } else { que.emplace(current_cost + edge_cost[edge_wall_hit_count_horizontal[px + delta.x[d]][wall_y]], px + delta.x[d], py + delta.y[d], delta.c[d ^ 1]); // ^ 1: 180 deg flip } } else { // vertical movement assert(abs(delta.x[d]) == 1); assert(delta.y[d] == 0); int wall_x = min(px, px + delta.x[d]); if (edge_passable_vertical[wall_x][py + delta.y[d]]) { que.emplace(current_cost, px + delta.x[d], py + delta.y[d], delta.c[d ^ 1]); // ^ 1: 180 deg flip } else { que.emplace(current_cost + edge_cost[edge_wall_hit_count_vertical[wall_x][py + delta.y[d]]], px + delta.x[d], py + delta.y[d], delta.c[d ^ 1]); // ^ 1: 180 deg flip } } } } } { int px = finish_x; int py = finish_y; while (!(px == start_x && py == start_y)) { assert(within_board(px, py)); assert(visited[px][py]); visited[px][py] = false; auto dir = prev_dir[px][py]; for (int d = 0; d < 4; d++) { if (delta.c[d] == dir) { next_path.push_back(delta.c[d ^ 1]); px += delta.x[d]; py += delta.y[d]; break; } } } reverse(next_path.begin(), next_path.end()); } } auto res = answer(next_path); if (res == -1) break; // valid path found else { int px = 0; int py = 0; for (int i = 0; i < res; i++) { for (int d = 0; d < 4; d++) { if (delta.c[d] == next_path[i]) { if (d & 2) { // horizontal movement assert(delta.x[d] == 0); assert(abs(delta.y[d]) == 1); int wall_y = min(py, py + delta.y[d]); edge_passable_horizontal[px + delta.x[d]][wall_y] = true; } else { // vertical movement assert(abs(delta.x[d]) == 1); assert(delta.y[d] == 0); int wall_x = min(px, px + delta.x[d]); edge_passable_vertical[wall_x][py + delta.y[d]] = true; } px += delta.x[d]; py += delta.y[d]; } } } for (int d = 0; d < 4; d++) { if (delta.c[d] == next_path[res]) { if (d & 2) { // horizontal movement assert(delta.x[d] == 0); assert(abs(delta.y[d]) == 1); int wall_y = min(py, py + delta.y[d]); edge_wall_hit_count_horizontal[px + delta.x[d]][wall_y]++; } else { // vertical movement assert(abs(delta.x[d]) == 1); assert(delta.y[d] == 0); int wall_x = min(px, px + delta.x[d]); edge_wall_hit_count_vertical[wall_x][py + delta.y[d]]++; } } } } } } int main(int argc, char *argv[]) { cin.tie(0); ios::sync_with_stdio(false); receive_first_input(); init(); solve(); return 0; }