結果

問題 No.5015 Escape from Labyrinth
ユーザー takumi152takumi152
提出日時 2023-04-16 10:54:28
言語 C++17
(gcc 12.3.0 + boost 1.83.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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,528 ms
10,092 KB
testcase_01 AC 2,536 ms
10,532 KB
testcase_02 AC 2,533 ms
10,632 KB
testcase_03 AC 2,539 ms
10,536 KB
testcase_04 AC 2,528 ms
10,200 KB
testcase_05 AC 2,540 ms
10,604 KB
testcase_06 AC 2,548 ms
10,764 KB
testcase_07 AC 2,530 ms
10,256 KB
testcase_08 AC 2,539 ms
10,648 KB
testcase_09 AC 2,532 ms
10,216 KB
testcase_10 AC 2,528 ms
10,420 KB
testcase_11 AC 2,527 ms
10,148 KB
testcase_12 AC 2,538 ms
10,528 KB
testcase_13 AC 2,530 ms
10,768 KB
testcase_14 AC 2,528 ms
10,524 KB
testcase_15 AC 2,533 ms
10,488 KB
testcase_16 AC 2,526 ms
10,284 KB
testcase_17 AC 2,530 ms
10,584 KB
testcase_18 AC 2,535 ms
10,376 KB
testcase_19 AC 2,532 ms
10,584 KB
testcase_20 AC 2,534 ms
10,452 KB
testcase_21 AC 2,526 ms
10,524 KB
testcase_22 AC 2,537 ms
10,588 KB
testcase_23 AC 2,527 ms
10,404 KB
testcase_24 AC 2,539 ms
10,416 KB
testcase_25 AC 2,531 ms
10,400 KB
testcase_26 AC 2,532 ms
10,352 KB
testcase_27 AC 2,528 ms
10,392 KB
testcase_28 AC 2,543 ms
10,692 KB
testcase_29 AC 2,541 ms
10,752 KB
testcase_30 AC 2,529 ms
10,244 KB
testcase_31 AC 2,546 ms
10,812 KB
testcase_32 AC 2,535 ms
10,448 KB
testcase_33 AC 2,540 ms
10,636 KB
testcase_34 AC 2,528 ms
10,568 KB
testcase_35 AC 2,536 ms
10,516 KB
testcase_36 AC 2,528 ms
10,456 KB
testcase_37 AC 2,536 ms
10,704 KB
testcase_38 AC 2,535 ms
10,612 KB
testcase_39 AC 2,526 ms
10,500 KB
testcase_40 AC 2,538 ms
10,676 KB
testcase_41 AC 2,539 ms
10,400 KB
testcase_42 AC 2,535 ms
10,236 KB
testcase_43 AC 2,534 ms
10,380 KB
testcase_44 AC 2,523 ms
10,404 KB
testcase_45 AC 2,529 ms
10,364 KB
testcase_46 AC 2,539 ms
10,672 KB
testcase_47 AC 2,531 ms
10,432 KB
testcase_48 AC 2,521 ms
10,292 KB
testcase_49 AC 2,535 ms
10,640 KB
testcase_50 AC 2,535 ms
10,136 KB
testcase_51 AC 2,542 ms
10,820 KB
testcase_52 AC 2,534 ms
10,456 KB
testcase_53 AC 2,529 ms
10,216 KB
testcase_54 AC 2,519 ms
10,480 KB
testcase_55 AC 2,529 ms
10,512 KB
testcase_56 AC 2,521 ms
10,528 KB
testcase_57 AC 2,542 ms
10,644 KB
testcase_58 AC 2,532 ms
10,440 KB
testcase_59 AC 2,532 ms
10,400 KB
testcase_60 AC 2,530 ms
10,296 KB
testcase_61 AC 2,529 ms
10,180 KB
testcase_62 AC 2,535 ms
10,580 KB
testcase_63 AC 2,529 ms
10,388 KB
testcase_64 AC 2,550 ms
10,864 KB
testcase_65 AC 2,530 ms
10,424 KB
testcase_66 AC 2,531 ms
10,400 KB
testcase_67 AC 2,526 ms
10,412 KB
testcase_68 AC 2,544 ms
10,460 KB
testcase_69 AC 2,526 ms
10,264 KB
testcase_70 AC 2,532 ms
10,556 KB
testcase_71 AC 2,536 ms
10,508 KB
testcase_72 AC 2,542 ms
10,656 KB
testcase_73 AC 2,537 ms
10,592 KB
testcase_74 AC 2,542 ms
10,460 KB
testcase_75 AC 2,531 ms
10,472 KB
testcase_76 AC 2,535 ms
10,724 KB
testcase_77 AC 2,534 ms
10,376 KB
testcase_78 AC 2,532 ms
10,556 KB
testcase_79 AC 2,551 ms
11,008 KB
testcase_80 AC 2,526 ms
10,284 KB
testcase_81 AC 2,523 ms
10,160 KB
testcase_82 AC 2,534 ms
10,304 KB
testcase_83 AC 2,532 ms
10,264 KB
testcase_84 AC 2,530 ms
10,760 KB
testcase_85 AC 2,535 ms
10,168 KB
testcase_86 AC 2,535 ms
10,648 KB
testcase_87 AC 2,540 ms
10,456 KB
testcase_88 AC 2,536 ms
10,496 KB
testcase_89 AC 2,546 ms
11,032 KB
testcase_90 AC 2,525 ms
10,304 KB
testcase_91 AC 2,541 ms
10,388 KB
testcase_92 AC 2,533 ms
10,796 KB
testcase_93 AC 2,543 ms
10,792 KB
testcase_94 AC 2,530 ms
10,788 KB
testcase_95 AC 2,526 ms
10,156 KB
testcase_96 AC 2,521 ms
10,340 KB
testcase_97 AC 2,537 ms
10,644 KB
testcase_98 AC 2,536 ms
10,368 KB
testcase_99 AC 2,526 ms
10,824 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
0