結果
問題 | No.5015 Escape from Labyrinth |
ユーザー |
|
提出日時 | 2023-04-16 11:43:47 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,546 ms / 3,000 ms |
コード長 | 32,047 bytes |
コンパイル時間 | 5,617 ms |
コンパイル使用メモリ | 325,108 KB |
実行使用メモリ | 11,088 KB |
スコア | 209,210 |
最終ジャッジ日時 | 2023-04-16 11:48:14 |
合計ジャッジ時間 | 265,442 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge16 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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 <unordered_map>#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 LOCALreturn (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)return (double)(l | h << 32) * 4.3478260869565215e-10; // 1 / 2.3e9, for yukicoder judge#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// enums// structsstruct position {int x, y;position() = default;position(int x, int y): x(x), y(y) {}bool operator==(const position& that) const {return this->x == that.x && this->y == that.y;}inline bool operator!=(const position& that) const {return !(*this == that);}};struct laser_info {position pos;int shot_interval;laser_info() = default;laser_info(position pos, int shot_interval): pos(pos), shot_interval(shot_interval) {}laser_info(int x, int y, int shot_interval): pos(position(x, y)), shot_interval(shot_interval) {}};// constantsconstexpr int board_size = 60;constexpr int init_health = 1500;constexpr int laser_shot_cycle = 60;struct {const vector<int> x = { -1, 1, 0, 0};const vector<int> y = { 0, 0, -1, 1};const vector<char> d = {'U', 'D', 'L', 'R'};} delta;// inputsint laser_damage;vector<vector<char>> init_board(board_size, vector<char>(board_size));int laser_num;vector<laser_info> laser_infos;// outputsvector<vector<char>> movement;// internalsposition player_start_pos;position key_pos;position exit_pos;vector<position> jewel_positions;vector<vector<int>> jewel_id_on_board(board_size, vector<int>(board_size));vector<vector<vector<int>>> damage_at_end_of_turn(laser_shot_cycle, vector<vector<int>>(board_size, vector<int>(board_size)));vector<vector<vector<int>>> health_required_to_exit(laser_shot_cycle, vector<vector<int>>(board_size, vector<int>(board_size)));vector<vector<vector<int>>> movement_for_exit(laser_shot_cycle, vector<vector<int>>(board_size, vector<int>(board_size)));vector<vector<vector<int>>> health_required_to_key(laser_shot_cycle, vector<vector<int>>(board_size, vector<int>(board_size)));vector<vector<vector<int>>> movement_for_key(laser_shot_cycle, vector<vector<int>>(board_size, vector<int>(board_size)));vector<vector<double>> expected_damage_per_turn(board_size, vector<double>(board_size));vector<vector<double>> expected_cost_between_jewels;vector<double> expected_cost_to_jewel_from_start;vector<double> expected_cost_to_jewel_from_key;vector<int> collect_order_before_key;vector<int> collect_order_after_key;inline bool within_board(int x, int y) {return 0 <= x && x < board_size && 0 <= y && y < board_size;}void receive_input() {int _board_size, _init_health;cin >> _board_size >> laser_damage >> _init_health;for (int i = 0; i < board_size; i++) {for (int j = 0; j < board_size; j++) {cin >> init_board[i][j];}}cin >> laser_num;laser_infos.resize(laser_num);for (int i = 0; i < laser_num; i++) {cin >> laser_infos[i].pos.x >> laser_infos[i].pos.y >> laser_infos[i].shot_interval;}}void init() {for (int i = 0; i < board_size; i++) {for (int j = 0; j < board_size; j++) {if (init_board[i][j] == 'S') player_start_pos = position(i, j);else if (init_board[i][j] == 'K') key_pos = position(i, j);else if (init_board[i][j] == 'G') exit_pos = position(i, j);else if (init_board[i][j] == 'J') jewel_positions.emplace_back(i, j);}}for (int i = 0; i < board_size; i++) {for (int j = 0; j < board_size; j++) {jewel_id_on_board[i][j] = -1;}}for (int i = 0; i < (int) jewel_positions.size(); i++) {jewel_id_on_board[jewel_positions[i].x][jewel_positions[i].y] = i;}{for (int t = 0; t < laser_shot_cycle; t++) {for (int i = 0; i < board_size; i++) {for (int j = 0; j < board_size; j++) {if (init_board[i][j] == '#' || init_board[i][j] == 'E') damage_at_end_of_turn[t][i][j] = 1000000; // (基本的に)立ち入れないので、入ったら即死ということにしておくelse damage_at_end_of_turn[t][i][j] = 1;}}}for (int l = 0; l < laser_num; l++) {for (int d = 0; d < 4; d++) {int px = laser_infos[l].pos.x + delta.x[d];int py = laser_infos[l].pos.y + delta.y[d];while (within_board(px, py) && !(init_board[px][py] == '#' || init_board[px][py] == 'E')) {for (int t = 0; t < laser_shot_cycle; t += laser_infos[l].shot_interval) {damage_at_end_of_turn[t][px][py] += laser_damage;}px += delta.x[d];py += delta.y[d];}}}}{for (int t = 0; t < laser_shot_cycle; t++) {for (int i = 0; i < board_size; i++) {for (int j = 0; j < board_size; j++) {health_required_to_exit[t][i][j] = 1000000;}}}priority_queue<tuple<int, int, int, int, int>, vector<tuple<int, int, int, int, int>>, greater<tuple<int, int, int, int, int>>> que; // distance,turn, x, y, next_movementfor (int t = 0; t < laser_shot_cycle; t++) {que.emplace(0, t, exit_pos.x, exit_pos.y, -1);}while (!que.empty()) {auto [dist, turn, px, py, next_movement] = que.top();que.pop();if (dist >= health_required_to_exit[turn][px][py]) continue;health_required_to_exit[turn][px][py] = dist;movement_for_exit[turn][px][py] = next_movement;int turn_cost = (px == exit_pos.x && py == exit_pos.y) ? 1 : damage_at_end_of_turn[(turn + laser_shot_cycle - 1) % laser_shot_cycle][px][py];if (dist + turn_cost < health_required_to_exit[(turn + laser_shot_cycle - 1) % laser_shot_cycle][px][py]) {que.emplace(dist + turn_cost, (turn + laser_shot_cycle - 1) % laser_shot_cycle, px, py, -1);}for (int d = 0; d < 4; d++) {if (within_board(px - delta.x[d], py - delta.y[d]) && dist + turn_cost < health_required_to_exit[(turn + laser_shot_cycle - 1) %laser_shot_cycle][px - delta.x[d]][py - delta.y[d]]) {que.emplace(dist + turn_cost, (turn + laser_shot_cycle - 1) % laser_shot_cycle, px - delta.x[d], py - delta.y[d], d);}}}}{for (int t = 0; t < laser_shot_cycle; t++) {for (int i = 0; i < board_size; i++) {for (int j = 0; j < board_size; j++) {health_required_to_key[t][i][j] = 1000000;}}}priority_queue<tuple<int, int, int, int, int>, vector<tuple<int, int, int, int, int>>, greater<tuple<int, int, int, int, int>>> que; // distance,turn, x, y, next_movementfor (int t = 0; t < laser_shot_cycle; t++) {que.emplace(0, t, key_pos.x, key_pos.y, -1);}while (!que.empty()) {auto [dist, turn, px, py, next_movement] = que.top();que.pop();if (dist >= health_required_to_key[turn][px][py]) continue;health_required_to_key[turn][px][py] = dist;movement_for_key[turn][px][py] = next_movement;int turn_cost = damage_at_end_of_turn[(turn + laser_shot_cycle - 1) % laser_shot_cycle][px][py];if (dist + turn_cost < health_required_to_key[(turn + laser_shot_cycle - 1) % laser_shot_cycle][px][py]) {que.emplace(dist + turn_cost, (turn + laser_shot_cycle - 1) % laser_shot_cycle, px, py, -1);}for (int d = 0; d < 4; d++) {if (within_board(px - delta.x[d], py - delta.y[d]) && dist + turn_cost < health_required_to_key[(turn + laser_shot_cycle - 1) %laser_shot_cycle][px - delta.x[d]][py - delta.y[d]]) {que.emplace(dist + turn_cost, (turn + laser_shot_cycle - 1) % laser_shot_cycle, px - delta.x[d], py - delta.y[d], d);}}}}for (int i = 0; i < board_size; i++) {for (int j = 0; j < board_size; j++) {int damage_sum = 0;for (int t = 0; t < laser_shot_cycle; t++) {damage_sum += damage_at_end_of_turn[t][i][j];}expected_damage_per_turn[i][j] = (double) damage_sum / (double) laser_shot_cycle;}}expected_cost_between_jewels = vector<vector<double>>(jewel_positions.size(), vector<double>(jewel_positions.size(), 1e10));for (int k = 0; k < (int) jewel_positions.size(); k++) {vector<vector<double>> distance_from_source_jewel(board_size, vector<double>(board_size, 1e10));priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<tuple<double, int, int>>> que;que.emplace(0.0, jewel_positions[k].x, jewel_positions[k].y);while (!que.empty()) {auto [dist, px, py] = que.top();que.pop();if (dist >= distance_from_source_jewel[px][py]) continue;distance_from_source_jewel[px][py] = dist;if (jewel_id_on_board[px][py] != -1) {expected_cost_between_jewels[k][jewel_id_on_board[px][py]] = dist;}for (int d = 0; d < 4; d++) {if (within_board(px + delta.x[d], py + delta.y[d])&& !(init_board[px + delta.x[d]][py + delta.y[d]] == '#' || init_board[px + delta.x[d]][py + delta.y[d]] == 'E')&& dist + expected_damage_per_turn[px + delta.x[d]][py + delta.y[d]] < distance_from_source_jewel[px + delta.x[d]][py + delta.y[d]]) {que.emplace(dist + expected_damage_per_turn[px + delta.x[d]][py + delta.y[d]], px + delta.x[d], py + delta.y[d]);}}}}expected_cost_to_jewel_from_start = vector<double>(jewel_positions.size(), 1e10);{vector<vector<double>> distance_from_start(board_size, vector<double>(board_size, 1e10));priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<tuple<double, int, int>>> que;que.emplace(0.0, player_start_pos.x, player_start_pos.y);while (!que.empty()) {auto [dist, px, py] = que.top();que.pop();if (dist >= distance_from_start[px][py]) continue;distance_from_start[px][py] = dist;if (jewel_id_on_board[px][py] != -1) {expected_cost_to_jewel_from_start[jewel_id_on_board[px][py]] = dist;}for (int d = 0; d < 4; d++) {if (within_board(px + delta.x[d], py + delta.y[d])&& !(init_board[px + delta.x[d]][py + delta.y[d]] == '#' || init_board[px + delta.x[d]][py + delta.y[d]] == 'E')&& dist + expected_damage_per_turn[px + delta.x[d]][py + delta.y[d]] < distance_from_start[px + delta.x[d]][py + delta.y[d]]) {que.emplace(dist + expected_damage_per_turn[px + delta.x[d]][py + delta.y[d]], px + delta.x[d], py + delta.y[d]);}}}}expected_cost_to_jewel_from_key = vector<double>(jewel_positions.size(), 1e10);{vector<vector<double>> distance_from_key(board_size, vector<double>(board_size, 1e10));priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<tuple<double, int, int>>> que;que.emplace(0.0, key_pos.x, key_pos.y);while (!que.empty()) {auto [dist, px, py] = que.top();que.pop();if (dist >= distance_from_key[px][py]) continue;distance_from_key[px][py] = dist;if (jewel_id_on_board[px][py] != -1) {expected_cost_to_jewel_from_key[jewel_id_on_board[px][py]] = dist;}for (int d = 0; d < 4; d++) {if (within_board(px + delta.x[d], py + delta.y[d])&& !(init_board[px + delta.x[d]][py + delta.y[d]] == '#' || init_board[px + delta.x[d]][py + delta.y[d]] == 'E')&& dist + expected_damage_per_turn[px + delta.x[d]][py + delta.y[d]] < distance_from_key[px + delta.x[d]][py + delta.y[d]]) {que.emplace(dist + expected_damage_per_turn[px + delta.x[d]][py + delta.y[d]], px + delta.x[d], py + delta.y[d]);}}}}for (int k = 0; k < (int) jewel_positions.size(); k++) {if (expected_cost_to_jewel_from_start[k] > 1e9) continue; // 到達不能な宝石は無視するdouble roll = theRandom.nextDouble();if (roll < 0.5) collect_order_before_key.push_back(k);else collect_order_after_key.push_back(k);}shuffle(collect_order_before_key.begin(), collect_order_before_key.end(), theMersenne);shuffle(collect_order_after_key.begin(), collect_order_after_key.end(), theMersenne);}void solve() {auto calc_score = [&]() {double cost = 0.0;double score = 0.0;for (int i = 0; i < (int) collect_order_before_key.size(); i++) {if (i == 0) cost += expected_cost_to_jewel_from_start[collect_order_before_key[i]];else cost += expected_cost_between_jewels[collect_order_before_key[i-1]][collect_order_before_key[i]];score += 10.0;}bool position_score_deducted = false;cost += health_required_to_key[0][jewel_positions[collect_order_before_key[collect_order_before_key.size()-1]].x][jewel_positions[collect_order_before_key[collect_order_before_key.size()-1]].y];if (cost > 1000.0) score -= cost * 1000.0; // 鍵を取るまでの経路が長すぎるならペナルティfor (int i = 0; i < (int) collect_order_after_key.size(); i++) {if (i == 0) cost += expected_cost_to_jewel_from_key[collect_order_after_key[i]];else cost += expected_cost_between_jewels[collect_order_after_key[i-1]][collect_order_after_key[i]];if (!position_score_deducted && cost > 2000.0) {score -= health_required_to_exit[0][jewel_positions[collect_order_after_key[i]].x][jewel_positions[collect_order_after_key[i]].y] / 5.0;position_score_deducted = true;}if (cost < 1500.0) score += 10.0;else if (cost < 2500.0) score += (2500.0 - cost) / 100.0;else break;}return score;};double score = calc_score();double last_score = score;double best_score = score;const double base_temperature = 5e0;const double target_temperature = 5e-2;// const double decay_rate = 4e-5;double temperature = base_temperature;double time_start = theTimer.time();const double time_limit = 2.500;int iter_count = 0;while (theTimer.time() < time_limit) {double roll = theRandom.nextDouble();if (roll < 0.15) {int idx1 = theRandom.nextUIntMod(collect_order_before_key.size());int idx2 = theRandom.nextUIntMod(collect_order_before_key.size());if (idx1 == idx2) continue;swap(collect_order_before_key[idx1], collect_order_before_key[idx2]);score = calc_score();#ifdef DEBUGif (iter_count % 100000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " <<theTimer.time() << endl;#endifif (score >= last_score) {last_score = score;if (score > best_score) {best_score = score;}}else if (theRandom.nextDouble() < exp(double(score - last_score) / temperature)) { // acceptlast_score = score;}else { // rollbackswap(collect_order_before_key[idx1], collect_order_before_key[idx2]);score = last_score;}}else if (roll < 0.30) {int idx1 = theRandom.nextUIntMod(collect_order_after_key.size());int idx2 = theRandom.nextUIntMod(collect_order_after_key.size());if (idx1 == idx2) continue;swap(collect_order_after_key[idx1], collect_order_after_key[idx2]);score = calc_score();#ifdef DEBUGif (iter_count % 100000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " <<theTimer.time() << endl;#endifif (score >= last_score) {last_score = score;if (score > best_score) {best_score = score;}}else if (theRandom.nextDouble() < exp(double(score - last_score) / temperature)) { // acceptlast_score = score;}else { // rollbackswap(collect_order_after_key[idx1], collect_order_after_key[idx2]);score = last_score;}}else if (roll < 0.35) {int idx1 = theRandom.nextUIntMod(collect_order_before_key.size());int idx2 = theRandom.nextUIntMod(collect_order_after_key.size());swap(collect_order_before_key[idx1], collect_order_after_key[idx2]);score = calc_score();#ifdef DEBUGif (iter_count % 100000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " <<theTimer.time() << endl;#endifif (score >= last_score) {last_score = score;if (score > best_score) {best_score = score;}}else if (theRandom.nextDouble() < exp(double(score - last_score) / temperature)) { // acceptlast_score = score;}else { // rollbackswap(collect_order_before_key[idx1], collect_order_after_key[idx2]);score = last_score;}}else if (roll < 0.55) {int idx1 = theRandom.nextUIntMod(collect_order_before_key.size());int idx2 = theRandom.nextUIntMod(collect_order_before_key.size());if (idx1 == idx2) continue;auto content = collect_order_before_key[idx1];collect_order_before_key.erase(collect_order_before_key.begin() + idx1);collect_order_before_key.insert(collect_order_before_key.begin() + idx2, content);score = calc_score();#ifdef DEBUGif (iter_count % 100000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " <<theTimer.time() << endl;#endifif (score >= last_score) {last_score = score;if (score > best_score) {best_score = score;}}else if (theRandom.nextDouble() < exp(double(score - last_score) / temperature)) { // acceptlast_score = score;}else { // rollbackcollect_order_before_key.erase(collect_order_before_key.begin() + idx2);collect_order_before_key.insert(collect_order_before_key.begin() + idx1, content);score = last_score;}}else if (roll < 0.75) {int idx1 = theRandom.nextUIntMod(collect_order_after_key.size());int idx2 = theRandom.nextUIntMod(collect_order_after_key.size());if (idx1 == idx2) continue;auto content = collect_order_after_key[idx1];collect_order_after_key.erase(collect_order_after_key.begin() + idx1);collect_order_after_key.insert(collect_order_after_key.begin() + idx2, content);score = calc_score();#ifdef DEBUGif (iter_count % 100000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " <<theTimer.time() << endl;#endifif (score >= last_score) {last_score = score;if (score > best_score) {best_score = score;}}else if (theRandom.nextDouble() < exp(double(score - last_score) / temperature)) { // acceptlast_score = score;}else { // rollbackcollect_order_after_key.erase(collect_order_after_key.begin() + idx2);collect_order_after_key.insert(collect_order_after_key.begin() + idx1, content);score = last_score;}}else if (roll < 0.875) {if (collect_order_before_key.size() <= 1) continue;int idx1 = theRandom.nextUIntMod(collect_order_before_key.size());int idx2 = theRandom.nextUIntMod(collect_order_after_key.size()+1);auto content = collect_order_before_key[idx1];collect_order_before_key.erase(collect_order_before_key.begin() + idx1);collect_order_after_key.insert(collect_order_after_key.begin() + idx2, content);score = calc_score();#ifdef DEBUGif (iter_count % 100000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " <<theTimer.time() << endl;#endifif (score >= last_score) {last_score = score;if (score > best_score) {best_score = score;}}else if (theRandom.nextDouble() < exp(double(score - last_score) / temperature)) { // acceptlast_score = score;}else { // rollbackcollect_order_after_key.erase(collect_order_after_key.begin() + idx2);collect_order_before_key.insert(collect_order_before_key.begin() + idx1, content);score = last_score;}}else {if (collect_order_after_key.size() <= 1) continue;int idx1 = theRandom.nextUIntMod(collect_order_after_key.size());int idx2 = theRandom.nextUIntMod(collect_order_before_key.size()+1);auto content = collect_order_after_key[idx1];collect_order_after_key.erase(collect_order_after_key.begin() + idx1);collect_order_before_key.insert(collect_order_before_key.begin() + idx2, content);score = calc_score();#ifdef DEBUGif (iter_count % 100000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " <<theTimer.time() << endl;#endifif (score >= last_score) {last_score = score;if (score > best_score) {best_score = score;}}else if (theRandom.nextDouble() < exp(double(score - last_score) / temperature)) { // acceptlast_score = score;}else { // rollbackcollect_order_before_key.erase(collect_order_before_key.begin() + idx2);collect_order_after_key.insert(collect_order_after_key.begin() + idx1, content);score = last_score;}}// temperature *= 1.0 - decay_rate;temperature = exp(log(base_temperature) - ((log(base_temperature) - log(target_temperature)) * ((theTimer.time() - time_start) * (1.0 /(time_limit - time_start)))));iter_count++;}cerr << "iter_count = " << iter_count << endl;cerr << "score = " << score << endl;cerr << "best_score = " << best_score << endl;cerr << "temperature = " << temperature << endl;}void create_answer() {int current_turn = 1;int remaining_health = init_health;position p = player_start_pos;for (int k = 0; k < (int) collect_order_before_key.size(); k++) {unordered_map<int, Pii> movement_record;vector<int> best_movement;priority_queue<tuple<int, int, int, int, int>, vector<tuple<int, int, int, int, int>>, greater<tuple<int, int, int, int, int>>> que;que.emplace(0, current_turn, p.x, p.y, -1);while (!que.empty()) {auto [cost, turn, px, py, prev_movement] = que.top();que.pop();int hash_now = turn * board_size * board_size + px * board_size + py;if (movement_record.find(hash_now) != movement_record.end() && cost >= movement_record[hash_now].first) continue;movement_record[hash_now] = Pii(cost, prev_movement);if (px == jewel_positions[collect_order_before_key[k]].x && py == jewel_positions[collect_order_before_key[k]].y) {int backtrace_turn = turn;position backtrace_pos = jewel_positions[collect_order_before_key[k]];while (backtrace_turn > current_turn) {int hash_backtrace = backtrace_turn * board_size * board_size + backtrace_pos.x * board_size + backtrace_pos.y;best_movement.push_back(movement_record[hash_backtrace].second);if (movement_record[hash_backtrace].second != -1) {backtrace_pos.x -= delta.x[movement_record[hash_backtrace].second];backtrace_pos.y -= delta.y[movement_record[hash_backtrace].second];}backtrace_turn--;}reverse(best_movement.begin(), best_movement.end());break;}int hash_stay = (turn + 1) * board_size * board_size + px * board_size + py;if (movement_record.find(hash_stay) == movement_record.end() || cost + damage_at_end_of_turn[turn % laser_shot_cycle][px][py] <movement_record[hash_stay].first) {que.emplace(cost + damage_at_end_of_turn[turn % laser_shot_cycle][px][py], turn + 1, px, py, -1);}for (int d = 0; d < 4; d++) {if (!within_board(px + delta.x[d], py + delta.y[d]) || init_board[px + delta.x[d]][py + delta.y[d]] == '#' || init_board[px + delta.x[d]][py+ delta.y[d]] == 'E') continue;int hash_move = (turn + 1) * board_size * board_size + (px + delta.x[d]) * board_size + (py + delta.y[d]);if (movement_record.find(hash_move) == movement_record.end() || cost + damage_at_end_of_turn[turn % laser_shot_cycle][px + delta.x[d]][py +delta.y[d]] < movement_record[hash_move].first) {que.emplace(cost + damage_at_end_of_turn[turn % laser_shot_cycle][px + delta.x[d]][py + delta.y[d]], turn + 1, px + delta.x[d], py + delta.y[d], d);}}}for (auto &next_movement: best_movement) {if (next_movement == -1) movement.push_back({'S'});else {movement.push_back({'M', delta.d[next_movement]});p.x += delta.x[next_movement];p.y += delta.y[next_movement];}remaining_health -= damage_at_end_of_turn[current_turn % laser_shot_cycle][p.x][p.y];current_turn++;}}while (p != key_pos) {int next_movement = movement_for_key[current_turn % laser_shot_cycle][p.x][p.y];if (next_movement == -1) movement.push_back({'S'});else {movement.push_back({'M', delta.d[next_movement]});p.x += delta.x[next_movement];p.y += delta.y[next_movement];}remaining_health -= damage_at_end_of_turn[current_turn % laser_shot_cycle][p.x][p.y];current_turn++;}for (int k = 0; k < (int) collect_order_after_key.size(); k++) {int health_required_to_next_jewel = 0;int turn_at_next_jewel = 0;unordered_map<int, Pii> movement_record;vector<int> best_movement;priority_queue<tuple<int, int, int, int, int>, vector<tuple<int, int, int, int, int>>, greater<tuple<int, int, int, int, int>>> que;que.emplace(0, current_turn, p.x, p.y, -1);while (!que.empty()) {auto [cost, turn, px, py, prev_movement] = que.top();que.pop();int hash_now = turn * board_size * board_size + px * board_size + py;if (movement_record.find(hash_now) != movement_record.end() && cost >= movement_record[hash_now].first) continue;movement_record[hash_now] = Pii(cost, prev_movement);if (px == jewel_positions[collect_order_after_key[k]].x && py == jewel_positions[collect_order_after_key[k]].y) {int backtrace_turn = turn;position backtrace_pos = jewel_positions[collect_order_after_key[k]];while (backtrace_turn > current_turn) {int hash_backtrace = backtrace_turn * board_size * board_size + backtrace_pos.x * board_size + backtrace_pos.y;best_movement.push_back(movement_record[hash_backtrace].second);if (movement_record[hash_backtrace].second != -1) {backtrace_pos.x -= delta.x[movement_record[hash_backtrace].second];backtrace_pos.y -= delta.y[movement_record[hash_backtrace].second];}backtrace_turn--;}reverse(best_movement.begin(), best_movement.end());health_required_to_next_jewel = cost;turn_at_next_jewel = turn;break;}int hash_stay = (turn + 1) * board_size * board_size + px * board_size + py;if (movement_record.find(hash_stay) == movement_record.end() || cost + damage_at_end_of_turn[turn % laser_shot_cycle][px][py] <movement_record[hash_stay].first) {que.emplace(cost + damage_at_end_of_turn[turn % laser_shot_cycle][px][py], turn + 1, px, py, -1);}for (int d = 0; d < 4; d++) {if (!within_board(px + delta.x[d], py + delta.y[d]) || init_board[px + delta.x[d]][py + delta.y[d]] == '#' || init_board[px + delta.x[d]][py+ delta.y[d]] == 'E' || init_board[px + delta.x[d]][py + delta.y[d]] == 'G') continue;int hash_move = (turn + 1) * board_size * board_size + (px + delta.x[d]) * board_size + (py + delta.y[d]);if (movement_record.find(hash_move) == movement_record.end() || cost + damage_at_end_of_turn[turn % laser_shot_cycle][px + delta.x[d]][py +delta.y[d]] < movement_record[hash_move].first) {que.emplace(cost + damage_at_end_of_turn[turn % laser_shot_cycle][px + delta.x[d]][py + delta.y[d]], turn + 1, px + delta.x[d], py + delta.y[d], d);}}}if (remaining_health < health_required_to_next_jewel + health_required_to_exit[turn_at_next_jewel %laser_shot_cycle][jewel_positions[collect_order_after_key[k]].x][jewel_positions[collect_order_after_key[k]].y]) break;for (auto &next_movement: best_movement) {if (next_movement == -1) movement.push_back({'S'});else {movement.push_back({'M', delta.d[next_movement]});p.x += delta.x[next_movement];p.y += delta.y[next_movement];}remaining_health -= damage_at_end_of_turn[current_turn % laser_shot_cycle][p.x][p.y];current_turn++;}}while (p != exit_pos) {int next_movement = movement_for_exit[current_turn % laser_shot_cycle][p.x][p.y];if (next_movement == -1) movement.push_back({'S'});else {movement.push_back({'M', delta.d[next_movement]});p.x += delta.x[next_movement];p.y += delta.y[next_movement];}if (p != exit_pos) remaining_health -= damage_at_end_of_turn[current_turn % laser_shot_cycle][p.x][p.y];current_turn++;}}void output_ans() {for (auto &next_move: movement) {for (int i = 0; i < (int) next_move.size(); i++) {cout << next_move[i];if (i < (int) next_move.size() - 1) cout << " ";}cout << endl;}}int main(int argc, char *argv[]) {cin.tie(0);ios::sync_with_stdio(false);receive_input();init();solve();create_answer();output_ans();return 0;}