Submission #65212780

---

Source Code Expand

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct AHC046 {
    int N, M;
    vector<pair<int, int>> pos;
    vector<vector<int>> board_target;
    vector<vector<int>> board_block;
    vector<pair<char, char>> ans;

    AHC046() { input(); }

    void input() {
        cin >> N >> M;
        pos.resize(M);
        for (int k = 0; k < M; ++k) {
            cin >> pos[k].first >> pos[k].second;
        }
        board_target.assign(N, vector<int>(N, -1));
        board_block.assign(N, vector<int>(N, false));
        for (int k = 1; k < M; ++k) {
            int r = pos[k].first, c = pos[k].second;
            board_target[r][c] = k;
        }
        ans.clear();
    }

    void output() const {
        for (auto &pr : ans)
            cout << pr.first << ' ' << pr.second << '\n';
    }

    int calc_score(const vector<pair<char, char>> &seq) const {
        int cur_r = pos[0].first, cur_c = pos[0].second;
        int next_target = 1, visited = 0;
        int maxT = 2 * N * M;
        vector<vector<int>> local_block = board_block;
        for (int t = 0; t < (int)seq.size() && t < maxT; ++t) {
            char act = seq[t].first, dir = seq[t].second;
            int dr = (dir == 'U' ? -1 : dir == 'D' ? 1 : 0);
            int dc = (dir == 'L' ? -1 : dir == 'R' ? 1 : 0);
            if (act == 'M') {
                int nr = cur_r + dr, nc = cur_c + dc;
                if (nr < 0 || nr >= N || nc < 0 || nc >= N ||
                    local_block[nr][nc])
                    break;
                cur_r = nr;
                cur_c = nc;
            } else if (act == 'S') {
                int nr = cur_r, nc = cur_c;
                while (true) {
                    int tr = nr + dr, tc = nc + dc;
                    if (tr < 0 || tr >= N || tc < 0 || tc >= N ||
                        local_block[tr][tc])
                        break;
                    nr = tr;
                    nc = tc;
                }
                cur_r = nr;
                cur_c = nc;
            } else if (act == 'A') {
                int br = cur_r + dr, bc = cur_c + dc;
                if (br >= 0 && br < N && bc >= 0 && bc < N)
                    local_block[br][bc] = !local_block[br][bc];
            }
            if (next_target < M && board_target[cur_r][cur_c] == next_target) {
                visited++;
                next_target++;
            }
        }
        if (visited < M - 1)
            return visited + 1;
        return M + max(0, maxT - (int)seq.size());
    }

    int greedy() {
        ans.clear();
        int cur_r = pos[0].first, cur_c = pos[0].second;
        for (int k = 1; k < M; ++k) {
            int tr = pos[k].first, tc = pos[k].second;
            int dr = tr - cur_r;
            int dc = tc - cur_c;
            char vdir = dr > 0 ? 'D' : 'U';
            char hdir = dc > 0 ? 'R' : 'L';

            vector<vector<pair<char, char>>> cands(4);
            // 0: no slide
            for (int i = 0; i < abs(dr); ++i)
                cands[0].emplace_back('M', vdir);
            for (int i = 0; i < abs(dc); ++i)
                cands[0].emplace_back('M', hdir);
            // 1: one horizontal slide
            for (int i = 0; i < abs(dr); ++i)
                cands[1].emplace_back('M', vdir);
            cands[1].emplace_back('S', hdir);
            int slide_h_c = (hdir == 'R' ? N - 1 : 0);
            int back_h = abs(slide_h_c - tc);
            char back_hdir = (slide_h_c > tc ? 'L' : 'R');
            for (int i = 0; i < back_h; ++i)
                cands[1].emplace_back('M', back_hdir);
            // 2: one vertical slide
            cands[2].emplace_back('S', vdir);
            int slide_v_r = (vdir == 'D' ? N - 1 : 0);
            int back_v = abs(slide_v_r - tr);
            char back_vdir = (slide_v_r > tr ? 'U' : 'D');
            for (int i = 0; i < back_v; ++i)
                cands[2].emplace_back('M', back_vdir);
            for (int i = 0; i < abs(dc); ++i)
                cands[2].emplace_back('M', hdir);
            // 3: two slides
            cands[3].emplace_back('S', vdir);
            cands[3].emplace_back('S', hdir);
            int slide2_v_r = (vdir == 'D' ? N - 1 : 0);
            int slide2_h_c = (hdir == 'R' ? N - 1 : 0);
            int back_v2 = abs(slide2_v_r - tr);
            char back_v2dir = (slide2_v_r > tr ? 'U' : 'D');
            for (int i = 0; i < back_v2; ++i)
                cands[3].emplace_back('M', back_v2dir);
            int back_h2 = abs(slide2_h_c - tc);
            char back_h2dir = (slide2_h_c > tc ? 'L' : 'R');
            for (int i = 0; i < back_h2; ++i)
                cands[3].emplace_back('M', back_h2dir);

            // pick shortest
            int best = 0, best_len = cands[0].size();
            for (int i = 1; i < 4; ++i) {
                if ((int)cands[i].size() < best_len) {
                    best = i;
                    best_len = cands[i].size();
                }
            }
            // append and update current pos
            for (auto &p : cands[best])
                ans.push_back(p);
            cur_r = tr;
            cur_c = tc;
        }
        return calc_score(ans);
    }

    vector<pair<char, char>> new_make_process(const vector<vector<int>> &bblock,
                                              int next_tar, int si,
                                              int sj) const {

        vector<int> DR = {1, 0, -1, 0};
        vector<int> DC = {0, 1, 0, -1};
        vector<char> DIRC = {'D', 'R', 'U', 'L'};

        auto make_path = [&](int sr, int sc, int tr, int tc) {
            vector<vector<int>> dist(N, vector<int>(N, INT_MAX));
            struct State {
                int pr, pc;
                char act, dir;
            };
            vector<vector<State>> prevv(N, vector<State>(N));
            queue<pair<int, int>> q;

            dist[sr][sc] = 0;
            q.push({sr, sc});

            while (!q.empty()) {
                auto [r, c] = q.front();
                q.pop();
                if (r == tr && c == tc)
                    break;
                int d = dist[r][c];

                // Move
                for (int k = 0; k < 4; ++k) {
                    int nr = r + DR[k], nc = c + DC[k];
                    if (nr < 0 || nr >= N || nc < 0 || nc >= N)
                        continue;
                    if (bblock[nr][nc])
                        continue;
                    if (dist[nr][nc] > d + 1) {
                        dist[nr][nc] = d + 1;
                        prevv[nr][nc] = {r, c, 'M', DIRC[k]};
                        q.push({nr, nc});
                    }
                }
                // Slide
                for (int k = 0; k < 4; ++k) {
                    int dr = DR[k], dc = DC[k];
                    int cr = r, cc = c;
                    while (true) {
                        int nr = cr + dr, nc = cc + dc;
                        if (nr < 0 || nr >= N || nc < 0 || nc >= N)
                            break;
                        if (bblock[nr][nc])
                            break;
                        cr = nr;
                        cc = nc;
                    }
                    if (dist[cr][cc] > d + 1) {
                        dist[cr][cc] = d + 1;
                        prevv[cr][cc] = {r, c, 'S', DIRC[k]};
                        q.push({cr, cc});
                    }
                }
            }

            // 経路再構築
            if (dist[tr][tc] == INT_MAX) {
                // 到達不能
                return vector<pair<char, char>>();
            }
            vector<pair<char, char>> path;
            int cr = tr, cc = tc;
            while (!(cr == sr && cc == sc)) {
                auto &st = prevv[cr][cc];
                path.emplace_back(st.act, st.dir);
                cr = st.pr;
                cc = st.pc;
            }
            reverse(path.begin(), path.end());
            return path;
        };

        vector<pair<char, char>> ret;
        while (next_tar < M) {
            int tr = pos[next_tar].first;
            int tc = pos[next_tar].second;
            auto path = make_path(si, sj, tr, tc);

            // 経路なしなら WA
            if (path.empty() && (si != tr || sj != tc)) {
                return vector<pair<char, char>>{{'W', 'A'}};
            }

            // 経路を追加
            for (auto &p : path) {
                ret.push_back(p);
            }
            si = tr;
            sj = tc;
            ++next_tar;
        }

        return ret;
    }

    void new_make_block(int id, char dir) {
        vector<pair<int, int>> path;
        vector<pair<char, char>> new_ans;
        vector<vector<int>> board_block(N, vector<int>(N, 0));
        int cur_r = pos[0].first, cur_c = pos[0].second;
        int next_tar = 1;
        for (int i = 0; i < id; ++i)
            new_ans.push_back(ans[i]);
        new_ans.push_back({'A', dir});
        for (auto [act, dir] : new_ans) {
            int dr = (dir == 'U' ? -1 : dir == 'D' ? 1 : 0);
            int dc = (dir == 'L' ? -1 : dir == 'R' ? 1 : 0);
            if (act == 'M') {
                int nr = cur_r + dr, nc = cur_c + dc;
                if (nr < 0 || nr >= N || nc < 0 || nc >= N ||
                    board_block[nr][nc])
                    break;
                cur_r = nr;
                cur_c = nc;
            } else if (act == 'S') {
                int nr = cur_r, nc = cur_c;
                while (true) {
                    int tr = nr + dr, tc = nc + dc;
                    if (tr < 0 || tr >= N || tc < 0 || tc >= N ||
                        board_block[tr][tc])
                        break;
                    nr = tr;
                    nc = tc;
                }
                cur_r = nr;
                cur_c = nc;
            } else if (act == 'A') {
                int br = cur_r + dr, bc = cur_c + dc;
                if (br >= 0 && br < N && bc >= 0 && bc < N)
                    board_block[br][bc] ^= 1;
                else {
                    return;
                }
                if (board_block[br][bc] && board_target[br][bc] >= next_tar) {
                    return;
                }
            }
            if (next_tar < M && board_target[cur_r][cur_c] == next_tar) {
                next_tar++;
            }
        }

        auto add_path = new_make_process(board_block, next_tar, cur_r, cur_c);
        if (add_path[0].first == 'W') {
            return;
        }
        for (auto p : add_path) {
            new_ans.push_back(p);
        }
        if (ans.size() > new_ans.size()) {
            ans = new_ans;
        }
    }

    int climbing() {
        greedy();
        // for (int i = 0; i < 1000; ++i) {
        //     int id = rand() % ans.size();
        //     char dir = "UDLR"[rand() % 4];
        //     new_make_block(id, dir);
        // }
        for (int i = 0; i < 1000; ++i) {
            if (ans.size() <= i)
                break;
            for (auto d = 0; d < 4; ++d) {
                char dir = "UDLR"[d];
                new_make_block(i, dir);
            }
        }
        return calc_score(ans);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    AHC046 solver;
    solver.climbing();
    solver.output();
    return 0;
}

Submission Info

Compile Error

Main.cpp: In member function ‘int AHC046::climbing()’:
Main.cpp:314:28: warning: comparison of integer expressions of different signedness: ‘std::vector<std::pair<char, char> >::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  314 |             if (ans.size() <= i)
      |                 ~~~~~~~~~~~^~~~

Judge Result