Submission #72331146

---

Source Code Expand

#include <algorithm>
#include <array>
#include <bitset>
#include <chrono>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>

using namespace std;

class Timer {
  public:
    Timer() : start_(chrono::high_resolution_clock::now()) {}
    void reset() { start_ = chrono::high_resolution_clock::now(); }
    long long elapsed_ms() const {
        auto now = chrono::high_resolution_clock::now();
        return chrono::duration_cast<chrono::milliseconds>(now - start_)
            .count();
    }

  private:
    chrono::high_resolution_clock::time_point start_;
};

constexpr int N = 20;
constexpr int BOARD_SIZE = N * N;
constexpr int CARD_TYPES = BOARD_SIZE / 2;
constexpr int OPEN_CANDS = 20;
constexpr int BEAM_LIMIT = 250;
constexpr long long TIME_LIMIT_MS = 1950;
constexpr int INF_INT = 1'000'000'000;

array<int, BOARD_SIZE> board_flat;
array<array<int, 2>, CARD_TYPES> card_cells;
array<int, BOARD_SIZE> row_of;
array<int, BOARD_SIZE> col_of;
array<array<uint16_t, BOARD_SIZE>, BOARD_SIZE> dist_matrix;

void build_dist_matrix();

inline int idx(int r, int c) { return r * N + c; }

inline int manhattan_idx(int a, int b) { return dist_matrix[a][b]; }

void build_dist_matrix() {
    for (int a = 0; a < BOARD_SIZE; ++a) {
        int ra = row_of[a];
        int ca = col_of[a];
        for (int b = 0; b < BOARD_SIZE; ++b) {
            int d = std::abs(ra - row_of[b]) + std::abs(ca - col_of[b]);
            dist_matrix[a][b] = static_cast<uint16_t>(d);
        }
    }
}

struct State {
    int id = -1;
    int depth = 0;  // visited cells
    int pos = 0;
    int move_cost = 0;
    int heuristic = 0;
    int parent = -1;
    int picked = -1;  // cell picked at this state
    bitset<BOARD_SIZE> taken;
    bitset<CARD_TYPES> on_stack;
    vector<int> stack;
    int score() const { return move_cost + heuristic; }
};

vector<State> states;

struct CompareState {
    bool operator()(int lhs, int rhs) const {
        const State& a = states[lhs];
        const State& b = states[rhs];
        if (a.score() != b.score()) return a.score() > b.score();  // min-heap
        return a.depth < b.depth;
    }
};

vector<priority_queue<int, vector<int>, CompareState>> beams(BOARD_SIZE + 1);
int best_state_id = -1;
Timer timer;

int calc_heuristic(const State& st) {
    // 1) resolve stack in LIFO order
    bitset<BOARD_SIZE> tmp_taken = st.taken;
    int pos = st.pos;
    int cost = 0;
    for (int i = static_cast<int>(st.stack.size()) - 1; i >= 0; --i) {
        int card = st.stack[i];
        int c0 = card_cells[card][0];
        int c1 = card_cells[card][1];
        int target = tmp_taken.test(c0) ? c1 : c0;
        cost += manhattan_idx(pos, target);
        pos = target;
        tmp_taken.set(target);
    }

    // 2) collect remaining complete pairs (both cells not taken)
    struct PairInfo {
        int c0, c1;
        int dist;
    };
    vector<PairInfo> pairs;
    pairs.reserve(CARD_TYPES);
    for (int card = 0; card < CARD_TYPES; ++card) {
        int c0 = card_cells[card][0];
        int c1 = card_cells[card][1];
        if (tmp_taken.test(c0) || tmp_taken.test(c1)) continue;
        int d01 = manhattan_idx(c0, c1);
        pairs.push_back({c0, c1, d01});
    }

    // 3) greedy visit for a limited number of pairs
    const int GREEDY_LIMIT = 20;
    int processed = 0;
    while (!pairs.empty() && processed < GREEDY_LIMIT) {
        int best_idx = -1;
        int best_to_first = INF_INT;
        bool go_to_c0 = true;
        for (int i = 0; i < static_cast<int>(pairs.size()); ++i) {
            int d0 = manhattan_idx(pos, pairs[i].c0);
            int d1 = manhattan_idx(pos, pairs[i].c1);
            if (d0 < best_to_first) {
                best_to_first = d0;
                best_idx = i;
                go_to_c0 = true;
            }
            if (d1 < best_to_first) {
                best_to_first = d1;
                best_idx = i;
                go_to_c0 = false;
            }
        }
        if (best_idx == -1) break;
        const PairInfo p = pairs[best_idx];
        cost += best_to_first + p.dist;
        pos = go_to_c0 ? p.c1 : p.c0;
        pairs[best_idx] = pairs.back();
        pairs.pop_back();
        processed++;
    }

    // 4) rough upper bound for remaining pairs
    int leftover_sum = 0;
    int nearest_leftover = INF_INT;
    for (const auto& p : pairs) {
        leftover_sum += p.dist;
        nearest_leftover = min(nearest_leftover, min(manhattan_idx(pos, p.c0),
                                                     manhattan_idx(pos, p.c1)));
    }
    if (nearest_leftover == INF_INT) nearest_leftover = 0;
    cost += leftover_sum + nearest_leftover;

    return cost;
}

bool better_state(int a, int b) {
    const State& x = states[a];
    const State& y = states[b];
    if (x.depth != y.depth) return x.depth > y.depth;
    if (x.stack.size() != y.stack.size())
        return x.stack.size() < y.stack.size();
    return x.move_cost < y.move_cost;
}

int other_cell(const State& st, int card) {
    int c0 = card_cells[card][0];
    int c1 = card_cells[card][1];
    if (!st.taken.test(c0)) return c0;
    if (!st.taken.test(c1)) return c1;
    return -1;
}

void prune(int depth) {
    auto& pq = beams[depth];
    if (static_cast<int>(pq.size()) <= BEAM_LIMIT) return;
    vector<int> keep;
    keep.reserve(BEAM_LIMIT);
    for (int i = 0; i < BEAM_LIMIT && !pq.empty(); i++) {
        keep.push_back(pq.top());
        pq.pop();
    }
    priority_queue<int, vector<int>, CompareState> npq(CompareState(),
                                                       std::move(keep));
    beams[depth].swap(npq);
}

void push_state(State st) {
    st.id = static_cast<int>(states.size());
    st.heuristic = calc_heuristic(st);
    int depth = st.depth;
    states.push_back(std::move(st));
    int sid = states.back().id;
    beams[depth].push(sid);
    prune(depth);
    if (best_state_id == -1 || better_state(sid, best_state_id))
        best_state_id = sid;
}

void expand(int sid) {
    // Snapshot because push_state can reallocate the states vector.
    const State cur = states[sid];
    if (cur.depth >= BOARD_SIZE) return;
    int next_depth = cur.depth + 1;

    // 1) Retrieve the pair for the top of the stack.
    if (!cur.stack.empty()) {
        int card = cur.stack.back();
        int target = other_cell(cur, card);
        if (target != -1) {
            State nxt = cur;
            nxt.parent = sid;
            nxt.picked = target;
            nxt.depth = next_depth;
            nxt.move_cost += manhattan_idx(cur.pos, target);
            nxt.pos = target;
            nxt.taken.set(target);
            nxt.stack.pop_back();
            nxt.on_stack.reset(card);
            push_state(std::move(nxt));
        }
    }

    // 2) Pick a new card that is not on the stack.
    vector<pair<int, int>> cand;
    cand.reserve(BOARD_SIZE - cur.depth);
    for (int i = 0; i < BOARD_SIZE; i++) {
        if (cur.taken.test(i)) continue;
        int card = board_flat[i];
        if (cur.on_stack.test(card)) continue;
        int dist = manhattan_idx(cur.pos, i);
        cand.push_back({dist, i});
    }
    if (!cand.empty()) {
        if (static_cast<int>(cand.size()) > OPEN_CANDS) {
            nth_element(
                cand.begin(), cand.begin() + OPEN_CANDS, cand.end(),
                [](const auto& a, const auto& b) { return a.first < b.first; });
            cand.resize(OPEN_CANDS);
        }
        sort(cand.begin(), cand.end(),
             [](const auto& a, const auto& b) { return a.first < b.first; });
        for (const auto& [dist, cell] : cand) {
            State nxt = cur;
            nxt.parent = sid;
            nxt.picked = cell;
            nxt.depth = next_depth;
            nxt.move_cost += dist;
            nxt.pos = cell;
            nxt.taken.set(cell);
            int card = board_flat[cell];
            nxt.stack.push_back(card);
            nxt.on_stack.set(card);
            push_state(std::move(nxt));
        }
    }
}

vector<int> reconstruct_path(int sid) {
    vector<int> path;
    int cur = sid;
    while (cur != -1) {
        const State& st = states[cur];
        if (st.picked != -1) path.push_back(st.picked);
        cur = st.parent;
    }
    reverse(path.begin(), path.end());
    return path;
}

vector<int> complete_path(State cur, vector<int> path) {
    while (cur.depth < BOARD_SIZE || !cur.stack.empty()) {
        if (!cur.stack.empty()) {
            int card = cur.stack.back();
            int target = other_cell(cur, card);
            if (target == -1) break;
            cur.move_cost += manhattan_idx(cur.pos, target);
            cur.pos = target;
            cur.taken.set(target);
            cur.stack.pop_back();
            cur.on_stack.reset(card);
            cur.depth++;
            path.push_back(target);
        } else {
            int best_cell = -1;
            int best_dist = INF_INT;
            for (int i = 0; i < BOARD_SIZE; i++) {
                if (cur.taken.test(i)) continue;
                int d = manhattan_idx(cur.pos, i);
                if (d < best_dist) {
                    best_dist = d;
                    best_cell = i;
                }
            }
            if (best_cell == -1) break;
            int card = board_flat[best_cell];
            cur.move_cost += best_dist;
            cur.pos = best_cell;
            cur.taken.set(best_cell);
            cur.stack.push_back(card);
            cur.on_stack.set(card);
            cur.depth++;
            path.push_back(best_cell);
        }
    }
    return path;
}

string build_operations(const vector<int>& path) {
    string ops;
    ops.reserve(BOARD_SIZE * 3);
    int cx = 0, cy = 0;
    vector<int> st;
    for (int cell : path) {
        int tx = row_of[cell];
        int ty = col_of[cell];
        while (cx < tx) {
            ops.push_back('D');
            cx++;
        }
        while (cx > tx) {
            ops.push_back('U');
            cx--;
        }
        while (cy < ty) {
            ops.push_back('R');
            cy++;
        }
        while (cy > ty) {
            ops.push_back('L');
            cy--;
        }
        ops.push_back('Z');
        int card = board_flat[cell];
        if (!st.empty() && st.back() == card) {
            st.pop_back();
        } else {
            st.push_back(card);
        }
    }
    return ops;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int x;
            cin >> x;
            int id = idx(i, j);
            board_flat[id] = x;
            row_of[id] = i;
            col_of[id] = j;
        }
    }

    for (auto& v : card_cells) v.fill(-1);
    for (int i = 0; i < BOARD_SIZE; i++) {
        int c = board_flat[i];
        if (card_cells[c][0] == -1)
            card_cells[c][0] = i;
        else
            card_cells[c][1] = i;
    }
    build_dist_matrix();

    states.clear();
    best_state_id = -1;
    for (auto& pq : beams)
        pq = priority_queue<int, vector<int>, CompareState>();
    timer.reset();

    State root;
    root.pos = 0;
    root.depth = 0;
    push_state(root);

    while (timer.elapsed_ms() < TIME_LIMIT_MS) {
        for (int d = 0; d < BOARD_SIZE; d++) {
            if (timer.elapsed_ms() >= TIME_LIMIT_MS) break;
            if (beams[d].empty()) continue;
            int sid = beams[d].top();
            beams[d].pop();
            expand(sid);
        }
    }

    vector<int> path = reconstruct_path(best_state_id);
    path = complete_path(states[best_state_id], std::move(path));
    string ops = build_operations(path);

    for (char c : ops) cout << c << '\n';
    return 0;
}

Submission Info

Judge Result