結果
| 問題 | No.5006 Hidden Maze |
| ユーザー |
 highjump
|
| 提出日時 | 2022-06-12 15:42:09 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 126 ms / 2,000 ms |
| コード長 | 5,124 bytes |
| コンパイル時間 | 1,786 ms |
| 実行使用メモリ | 22,620 KB |
| スコア | 40,198 |
| 平均クエリ数 | 599.02 |
| 最終ジャッジ日時 | 2022-06-12 15:42:47 |
| 合計ジャッジ時間 | 13,987 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge14 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
コンパイルメッセージ
main.cpp: 関数 ‘int move(int, char)’ 内:
main.cpp:134:1: 警告: 制御が非 void 関数の終りに到達しました [-Wreturn-type]
134 | }
| ^
main.cpp: 関数 ‘std::string findPath()’ 内:
main.cpp:172:1: 警告: 制御が非 void 関数の終りに到達しました [-Wreturn-type]
172 | }
| ^
ソースコード
#pragma GCC optimize("Ofast")#include <iostream>#include <algorithm>#include <string>#include <cstdlib>#include <cmath>#include <iomanip>#include <cctype>#include <sstream>#include <vector>#include <stack>#include <deque>#include <queue>#include <list>#include <set>#include <map>#include <unordered_map>#include <chrono>#include <random>using namespace std;using ll = long long;using P = pair<int, int>;template <class T>using V = vector<T>;template <class T>using VV = V<V<T>>;template <class T, class U>bool chmin(T& t, const U& u) { if (t > u) { t = u; return 1; } else return 0; }template <class T, class U>bool chmax(T& t, const U& u) { if (t < u) { t = u; return 1; } else return 0; }#define REP(i,n) for(int i=0;i<int(n);i++)#define FOR(i,a,b) for(int i=int(a);i<=int(b);i++)#define FORD(i,a,b) for(int i=int(a);i>=int(b);i--)#define MP make_pair#define SZ(x) int(x.size())#define ALL(x) x.begin(),x.end()#define INF 10001000#define endl "\n"chrono::system_clock::time_point t_start;const double TIME_LIMIT1 = 500, TIME_LIMIT = 2930;double last_update = 0, t_diff;double start_temp, end_temp;mt19937 rng;using uni_int = uniform_int_distribution<>;using uni_real = uniform_real_distribution<>;using u64 = uint64_t;using u32 = uint32_t;V<int> y_vec = { 0, 1,0, -1 };V<int> x_vec = { -1, 0,1, 0 };class XorInt {public:uint32_t x = 2463534242;XorInt() {};XorInt(uint32_t seed) {x = 2463534242 + seed;};uint32_t next() {x ^= x << 13; x ^= x >> 17; x ^= x << 5;return x;}uint32_t operator()(uint32_t l, uint32_t r) {return (this->next() % (r - l)) + l;}uint32_t operator()(uint32_t d) {return this->next() % d;}};XorInt xs;class Xor64 {public:uint64_t x = 88172645463325252ULL;Xor64() {};Xor64(uint64_t seed) {x = 88172645463325252ULL + seed;}uint64_t next() {x ^= x << 13; x ^= x >> 7; x ^= x << 17;return x;}uint64_t operator()(uint64_t l, uint64_t r) {return (this->next() % (r - l)) + l;}uint64_t operator()(uint64_t d) {return this->next() % d;}};Xor64 xx;void get_time() {auto t_now = chrono::system_clock::now();t_diff = chrono::duration_cast<chrono::milliseconds>(t_now - t_start).count();}int H, W, p;int Pos(int x, int y) {return x * W + y;}char Dir(int pos, int npos) {if (pos / H == npos / H) {if (pos < npos)return'R';else return 'L';}else {if (pos < npos)return'D';else return 'U';}}int move(int pos, char dir) {if (dir == 'U')return pos - W;if (dir == 'R')return pos + 1;if (dir == 'D')return pos + W;if (dir == 'L')return pos - 1;}string Direction = "URDL";VV<int> pass;class Cell {public:int state = 0;V<int> around4;Cell() {};};V<Cell> grid;string findPath() {int start = 0;int goal = H * W - 1;V<int> d(H * W, INF);V<string> path(H * W, "");d[0] = 0;priority_queue<P, V<P>, greater<P>> pq;pq.push(MP(0, 0));while (!pq.empty()) {int dis = pq.top().first;int pos = pq.top().second;pq.pop();if (dis > d[pos])continue;if (pos == goal)return path[goal];for (auto npos : grid[pos].around4) {int cost = max(0, pass[pos][npos]);if (chmin(d[npos], d[pos] + cost)) {path[npos] = path[pos] + Dir(pos,npos);pq.push(MP(d[npos], npos));}}}}void update(string ans, int res) {int pos = 0;REP(i, res) {int npos = move(pos, ans[i]);pass[pos][npos] = -1;pass[npos][pos] = -1;pos = npos;}int npos = move(pos, ans[res]);if (pass[pos][npos] == -1)return;pass[pos][npos] += 100 - p;pass[npos][pos] = pass[pos][npos];}signed main() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);cerr << fixed << setprecision(15);t_start = chrono::system_clock::now();get_time();cin >> H >> W >> p;grid = V<Cell>(H * W);pass = VV<int>(H * W, V<int>(H * W));REP(x, H) {REP(y, W) {V<int> a;REP(k, 4) {int nx = x + x_vec[k];int ny = y + y_vec[k];if (nx < 0 || nx >= H || ny < 0 || ny >= W)continue;a.push_back(Pos(nx, ny));}shuffle(ALL(a),rng);grid[Pos(x, y)].around4 = a;}}while (true) {string ans = findPath();cerr << ans << endl;cout << ans << endl;cout.flush();int res;cin >> res;if (res == -1)break;update(ans, res);}cerr << "time: " << int(t_diff) << " ms" << endl;//cerr << "score: " << score << endl;//cerr << "last: " << last_update << endl;//cerr << "cnt: " << cnt << endl;//cerr << "update:" << update_cnt << endl;return 0;}