結果
問題 | No.5006 Hidden Maze |
ユーザー | takumi152 |
提出日時 | 2022-06-12 14:54:21 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.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 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 24 ms
22,588 KB |
testcase_01 | AC | 31 ms
21,928 KB |
testcase_02 | AC | 19 ms
22,588 KB |
testcase_03 | AC | 34 ms
22,228 KB |
testcase_04 | AC | 32 ms
21,940 KB |
testcase_05 | AC | 105 ms
21,980 KB |
testcase_06 | AC | 27 ms
21,980 KB |
testcase_07 | AC | 64 ms
22,692 KB |
testcase_08 | AC | 118 ms
21,992 KB |
testcase_09 | AC | 118 ms
21,892 KB |
testcase_10 | AC | 22 ms
22,276 KB |
testcase_11 | AC | 29 ms
22,876 KB |
testcase_12 | AC | 31 ms
22,204 KB |
testcase_13 | AC | 31 ms
21,660 KB |
testcase_14 | AC | 45 ms
21,756 KB |
testcase_15 | AC | 31 ms
21,940 KB |
testcase_16 | AC | 54 ms
21,880 KB |
testcase_17 | AC | 18 ms
22,576 KB |
testcase_18 | AC | 59 ms
21,916 KB |
testcase_19 | AC | 79 ms
21,892 KB |
testcase_20 | AC | 26 ms
21,780 KB |
testcase_21 | AC | 27 ms
21,992 KB |
testcase_22 | AC | 18 ms
21,916 KB |
testcase_23 | AC | 22 ms
21,940 KB |
testcase_24 | AC | 29 ms
22,612 KB |
testcase_25 | AC | 51 ms
21,892 KB |
testcase_26 | AC | 108 ms
22,704 KB |
testcase_27 | AC | 68 ms
22,216 KB |
testcase_28 | AC | 104 ms
22,552 KB |
testcase_29 | AC | 69 ms
21,892 KB |
testcase_30 | AC | 24 ms
21,768 KB |
testcase_31 | AC | 26 ms
21,980 KB |
testcase_32 | AC | 54 ms
21,928 KB |
testcase_33 | AC | 25 ms
22,264 KB |
testcase_34 | AC | 20 ms
21,940 KB |
testcase_35 | AC | 32 ms
21,880 KB |
testcase_36 | AC | 29 ms
21,880 KB |
testcase_37 | AC | 39 ms
21,768 KB |
testcase_38 | AC | 66 ms
21,928 KB |
testcase_39 | AC | 24 ms
22,600 KB |
testcase_40 | AC | 21 ms
21,768 KB |
testcase_41 | AC | 25 ms
22,264 KB |
testcase_42 | AC | 26 ms
21,904 KB |
testcase_43 | AC | 46 ms
21,892 KB |
testcase_44 | AC | 28 ms
21,928 KB |
testcase_45 | AC | 37 ms
22,004 KB |
testcase_46 | AC | 32 ms
21,892 KB |
testcase_47 | AC | 28 ms
21,880 KB |
testcase_48 | AC | 96 ms
21,768 KB |
testcase_49 | AC | 123 ms
21,780 KB |
testcase_50 | AC | 34 ms
21,928 KB |
testcase_51 | AC | 24 ms
22,444 KB |
testcase_52 | AC | 22 ms
21,940 KB |
testcase_53 | AC | 33 ms
21,892 KB |
testcase_54 | AC | 41 ms
21,992 KB |
testcase_55 | AC | 23 ms
21,928 KB |
testcase_56 | AC | 27 ms
22,704 KB |
testcase_57 | AC | 89 ms
22,264 KB |
testcase_58 | AC | 93 ms
21,892 KB |
testcase_59 | AC | 29 ms
21,940 KB |
testcase_60 | AC | 19 ms
22,264 KB |
testcase_61 | AC | 25 ms
22,096 KB |
testcase_62 | AC | 39 ms
21,992 KB |
testcase_63 | AC | 19 ms
21,768 KB |
testcase_64 | AC | 37 ms
22,620 KB |
testcase_65 | AC | 21 ms
22,444 KB |
testcase_66 | AC | 19 ms
22,576 KB |
testcase_67 | AC | 33 ms
21,928 KB |
testcase_68 | AC | 114 ms
22,216 KB |
testcase_69 | AC | 81 ms
22,612 KB |
testcase_70 | AC | 22 ms
21,928 KB |
testcase_71 | AC | 22 ms
21,880 KB |
testcase_72 | AC | 39 ms
21,768 KB |
testcase_73 | AC | 91 ms
22,264 KB |
testcase_74 | AC | 33 ms
21,892 KB |
testcase_75 | AC | 98 ms
22,548 KB |
testcase_76 | AC | 90 ms
21,940 KB |
testcase_77 | AC | 111 ms
21,940 KB |
testcase_78 | AC | 57 ms
21,768 KB |
testcase_79 | AC | 119 ms
21,904 KB |
testcase_80 | AC | 21 ms
21,892 KB |
testcase_81 | AC | 26 ms
21,940 KB |
testcase_82 | AC | 26 ms
22,868 KB |
testcase_83 | AC | 20 ms
22,576 KB |
testcase_84 | AC | 24 ms
22,216 KB |
testcase_85 | AC | 77 ms
21,904 KB |
testcase_86 | AC | 35 ms
22,864 KB |
testcase_87 | AC | 33 ms
21,992 KB |
testcase_88 | AC | 44 ms
21,940 KB |
testcase_89 | AC | 70 ms
22,612 KB |
testcase_90 | AC | 23 ms
21,892 KB |
testcase_91 | AC | 20 ms
22,276 KB |
testcase_92 | AC | 36 ms
21,904 KB |
testcase_93 | AC | 31 ms
22,600 KB |
testcase_94 | AC | 50 ms
22,444 KB |
testcase_95 | AC | 76 ms
22,552 KB |
testcase_96 | AC | 19 ms
21,992 KB |
testcase_97 | AC | 89 ms
21,992 KB |
testcase_98 | AC | 105 ms
21,768 KB |
testcase_99 | AC | 51 ms
21,768 KB |
ソースコード
#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; }