Submission #65208020

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define TOSTRING(x) std::string(#x)
template <typename T, typename U> std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p) { return os; }
template <typename T> std::istream &operator>>(std::istream &is, std::vector<T> &vec) { for(T &x : vec) is >> x; return is; }
template <typename T> std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) { os << "["; for(auto _ : v) os << _ << ", "; os << "]"; return os; };
template <typename T> std::ostream &operator<<(std::ostream &os, std::set<T> &st) {os << "("; for(auto _ : st) { os << _ << ", "; } os << ")"; return os; }
template <typename T> std::ostream &operator<<(std::ostream &os, std::multiset<T> &st) { os << "("; for(auto _ : st) { os << _ << ", "; } os << ")"; return os; }
template <typename T, typename U> std::ostream &operator<<(std::ostream &os, const std::map<T, U> &mp) { os << "["; for(auto _ : mp) { os << _ << ", "; } os << "]"; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, std::deque<T> dq) { os << "["; while (!dq.empty()) { os << dq.front(); dq.pop_front(); if (!dq.empty()) { os << ", "; } } os << "]"; return os; }
#define DUMPOUT std::cerr
void dump_func() { DUMPOUT << std::endl; }
template <class Head, class... Tail>
void dump_func(Head &&head, Tail &&...tail) { DUMPOUT << head; if(sizeof...(Tail) > 0) { DUMPOUT << ", "; } dump_func(std::move(tail)...); }
#ifdef DEBUG
#define dbg(...) { dump_func(__VA_ARGS__) }
#define dump(...) DUMPOUT << std::string(#__VA_ARGS__) << ": "; dump_func(__VA_ARGS__)
#else
#define dbg(...)
#define dump(...)
#endif

constexpr double TL = 1.95;
struct MyTimer {
    std::chrono::high_resolution_clock::time_point start;
    MyTimer() { reset(); }
    void reset() {
        start = std::chrono::high_resolution_clock::now();
    }
    inline double get() {
        auto now = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double> diff = now - start;
        return diff.count();
    }
} timer;

int rnd() {
    static int x = 123456789;
    static int y = 362436069;
    static int z = 521288629;
    static int w = 88675123;
    int t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

double drnd() {
    return (double)rnd() / (double)(UINT32_MAX);
}

string dstr = "UDLR";
constexpr int dx[4] = {-1, 1, 0, 0};
constexpr int dy[4] = {0, 0, -1, 1};

constexpr int N = 20;
constexpr int M = 40;

vector<int> i, j;
vector<pair<char, char>> ans;

void input() {
    int _;
    cin >> _ >> _;
    i.resize(M);
    j.resize(M);
    for(int t = 0; t < M; t++) {
        cin >> i[t] >> j[t];
    }
    dump(i);
    dump(j);
}

void solve_only_move() {
    int x = i[0], y = j[0];
    for (int t = 1; t < M; ++t) {
        const int tx = i[t];
        const int ty = j[t];

        while (x < tx) { ans.emplace_back('M', 'D'); ++x; }
        while (x > tx) { ans.emplace_back('M', 'U'); --x; }

        while (y < ty) { ans.emplace_back('M', 'R'); ++y; }
        while (y > ty) { ans.emplace_back('M', 'L'); --y; }
    }
}

void solve_move_and_skating() {
    int x = i[0], y = j[0];

    for (int idx = 1; idx < M; ++idx) {
        const int tx = i[idx], ty = j[idx];

        /* ---------- 縦方向（行） ---------- */
        {
            // 0: 直接 M, 1: 上端へ S→M, 2: 下端へ S→M
            int best = 0;
            int bestCost = abs(tx - x);
            int costTop    = (x ? 1 : 0) + tx;          // x!=0 なら S U + tx 回 M D
            int costBottom = (x != N - 1 ? 1 : 0) + (N - 1 - tx); // x!=19 なら S D + (19-tx) 回 M U

            if (costTop    < bestCost) { best = 1; bestCost = costTop; }
            if (costBottom < bestCost) { best = 2; bestCost = costBottom; }

            if (best == 1 && x) {                // S U
                ans.emplace_back('S', 'U');
                x = 0;
            } else if (best == 2 && x != N - 1) { // S D
                ans.emplace_back('S', 'D');
                x = N - 1;
            }
            // 残りは M で目標へ
            while (x < tx) { ans.emplace_back('M', 'D'); ++x; }
            while (x > tx) { ans.emplace_back('M', 'U'); --x; }
        }

        /* ---------- 横方向（列） ---------- */
        {
            // 0: 直接 M, 1: 左端へ S→M, 2: 右端へ S→M
            int best = 0;
            int bestCost = abs(ty - y);
            int costLeft  = (y ? 1 : 0) + ty;            // y!=0 なら S L + ty 回 M R
            int costRight = (y != N - 1 ? 1 : 0) + (N - 1 - ty); // y!=19 なら S R + (19-ty) 回 M L

            if (costLeft  < bestCost) { best = 1; bestCost = costLeft; }
            if (costRight < bestCost) { best = 2; bestCost = costRight; }

            if (best == 1 && y) {                // S L
                ans.emplace_back('S', 'L');
                y = 0;
            } else if (best == 2 && y != N - 1) { // S R
                ans.emplace_back('S', 'R');
                y = N - 1;
            }
            // 残りは M で目標へ
            while (y < ty) { ans.emplace_back('M', 'R'); ++y; }
            while (y > ty) { ans.emplace_back('M', 'L'); --y; }
        }
    }
}


void output() {
    for (auto [act, dir] : ans) {
        cout << act << ' ' << dir << '\n';
    }
}

int main() {
    timer.reset();
    input();
    // solve_only_move();
    solve_move_and_skating();
    output();
}

Submission Info

Judge Result