結果

問題 No.5015 Escape from Labyrinth
ユーザー takumi152takumi152
提出日時 2023-04-16 10:54:28
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,551 ms / 3,000 ms
コード長 31,585 bytes
コンパイル時間 8,941 ms
コンパイル使用メモリ 323,388 KB
実行使用メモリ 11,032 KB
スコア 148,800
最終ジャッジ日時 2023-04-16 10:59:00
合計ジャッジ時間 268,538 ms
ジャッジサーバーID
(参考情報)
judge12 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

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

#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 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)
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
// structs
struct 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) {}
};
// constants
constexpr 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;
// inputs
int laser_damage;
vector<vector<char>> init_board(board_size, vector<char>(board_size));
int laser_num;
vector<laser_info> laser_infos;
// outputs
vector<vector<char>> movement;
// internals
position 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_movement
for (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_movement
for (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 score = 0.0;
for (int i = 0; i < (int) collect_order_before_key.size(); i++) {
if (i == 0) score += expected_cost_to_jewel_from_start[collect_order_before_key[i]];
else score += expected_cost_between_jewels[collect_order_before_key[i-1]][collect_order_before_key[i]];
}
score += 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 (score > 1000.0) score *= score; //
for (int i = 0; i < (int) collect_order_after_key.size(); i++) {
if (i == 0) score += expected_cost_to_jewel_from_key[collect_order_after_key[i]] * 2.0;
else score += expected_cost_between_jewels[collect_order_after_key[i-1]][collect_order_after_key[i]] * 2.0;
}
return score;
};
int score = calc_score();
int last_score = score;
int best_score = score;
const double base_temperature = 1e2;
const double target_temperature = 1e-1;
// 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 DEBUG
if (iter_count % 10000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " <<
          theTimer.time() << endl;
#endif
if (score <= last_score) {
last_score = score;
if (score < best_score) {
best_score = score;
}
}
else if (theRandom.nextDouble() < exp(double(last_score - score) / temperature)) { // accept
last_score = score;
}
else { // rollback
swap(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 DEBUG
if (iter_count % 10000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " <<
          theTimer.time() << endl;
#endif
if (score <= last_score) {
last_score = score;
if (score < best_score) {
best_score = score;
}
}
else if (theRandom.nextDouble() < exp(double(last_score - score) / temperature)) { // accept
last_score = score;
}
else { // rollback
swap(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 DEBUG
if (iter_count % 10000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " <<
          theTimer.time() << endl;
#endif
if (score <= last_score) {
last_score = score;
if (score < best_score) {
best_score = score;
}
}
else if (theRandom.nextDouble() < exp(double(last_score - score) / temperature)) { // accept
last_score = score;
}
else { // rollback
swap(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 DEBUG
if (iter_count % 10000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " <<
          theTimer.time() << endl;
#endif
if (score <= last_score) {
last_score = score;
if (score < best_score) {
best_score = score;
}
}
else if (theRandom.nextDouble() < exp(double(last_score - score) / temperature)) { // accept
last_score = score;
}
else { // rollback
collect_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 DEBUG
if (iter_count % 10000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " <<
          theTimer.time() << endl;
#endif
if (score <= last_score) {
last_score = score;
if (score < best_score) {
best_score = score;
}
}
else if (theRandom.nextDouble() < exp(double(last_score - score) / temperature)) { // accept
last_score = score;
}
else { // rollback
collect_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 DEBUG
if (iter_count % 10000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " <<
          theTimer.time() << endl;
#endif
if (score <= last_score) {
last_score = score;
if (score < best_score) {
best_score = score;
}
}
else if (theRandom.nextDouble() < exp(double(last_score - score) / temperature)) { // accept
last_score = score;
}
else { // rollback
collect_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 DEBUG
if (iter_count % 10000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " <<
          theTimer.time() << endl;
#endif
if (score <= last_score) {
last_score = score;
if (score < best_score) {
best_score = score;
}
}
else if (theRandom.nextDouble() < exp(double(last_score - score) / temperature)) { // accept
last_score = score;
}
else { // rollback
collect_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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0