Submission #75822323

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 20;
const int EXIT_I = 0;
const int EXIT_J = N / 2; // 10

int a[N][N];

struct Conveyor {
    int length;
    vector<pair<int, int>> cells;
};

struct Operation {
    int m;
    int d;
};

vector<Conveyor> conveyors;
vector<Operation> operations;

// 盤面を回すシミュレーション
void rotate_conveyor(int m, int d) {
    const auto& conv = conveyors[m];
    int len = conv.length;
    vector<int> vals(len);
    for (int i = 0; i < len; ++i) {
        vals[i] = a[conv.cells[i].first][conv.cells[i].second];
    }
    for (int i = 0; i < len; ++i) {
        int next_idx = (i + d + len) % len;
        a[conv.cells[next_idx].first][conv.cells[next_idx].second] = vals[i];
    }
}

// 操作の記録と実行
void do_operation(int m, int d, int count) {
    for (int c = 0; c < count; ++c) {
        operations.push_back({m, d});
        rotate_conveyor(m, d);
    }
}

// 特定のコンベア上のターゲットを指定のインデックス位置まで回転させて持ってくる関数
void move_target_to_idx(int m, pair<int, int> target_pos, int goal_idx) {
    const auto& conv = conveyors[m];
    int current_idx = -1;
    for (int i = 0; i < conv.length; ++i) {
        if (conv.cells[i] == target_pos) {
            current_idx = i;
            break;
        }
    }
    if (current_idx == -1 || current_idx == goal_idx) return;

    int len = conv.length;
    int diff = (goal_idx - current_idx + len) % len;
    if (diff <= len / 2) {
        do_operation(m, 1, diff);
    } else {
        do_operation(m, -1, len - diff);
    }
}

// ターゲットの現在の座標を探す補助関数
pair<int, int> find_target(int target) {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (a[i][j] == target) return {i, j};
        }
    }
    return {-1, -1};
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int input_N;
    if (!(cin >> input_N)) return 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> a[i][j];
        }
    }

    // 1. 正しいベルトコンベアの設置
    for (int i = 0; i < N; i += 2) {
        Conveyor conv;
        conv.length = 2 * N;
        for (int j = 0; j < N; ++j) conv.cells.push_back({i, j});
        for (int j = N - 1; j >= 0; --j) conv.cells.push_back({i + 1, j});
        conveyors.push_back(conv);
    }
    for (int j = 0; j < N; j += 2) {
        Conveyor conv;
        conv.length = 2 * N;
        for (int i = 0; i < N; ++i) conv.cells.push_back({i, j});
        for (int i = N - 1; i >= 0; --i) conv.cells.push_back({i, j + 1});
        conveyors.push_back(conv);
    }

    int next_target = 0;
    if (a[EXIT_I][EXIT_J] == 0) {
        a[EXIT_I][EXIT_J] = -1;
        next_target = 1;
    }

    const int GOAL_IDX_IN_ROW0 = 10;

    // 2. 貪欲法 ＋ 賢い先読み回収
    while (next_target < N * N) {
        pair<int, int> pos1 = find_target(next_target);

        if (pos1.first == EXIT_I && pos1.second == EXIT_J) {
            a[EXIT_I][EXIT_J] = -1;
            next_target++;
            continue;
        }

        // ステップA: ターゲット(T1)が属する縦ループを使って、行0まで運ぶ
        int v_idx = 10 + (pos1.second / 2);
        int v_goal_idx = -1;
        for (int idx = 0; idx < conveyors[v_idx].length; ++idx) {
            if (conveyors[v_idx].cells[idx].first == 0 && conveyors[v_idx].cells[idx].second == pos1.second) {
                v_goal_idx = idx;
                break;
            }
        }
        move_target_to_idx(v_idx, pos1, v_goal_idx);

        // 縦移動後のT1の位置を更新
        pos1 = find_target(next_target);

        // 🌟追加実装: ステップA2 (便乗計算付きの先読み)🌟
        if (next_target + 1 < N * N) {
            pair<int, int> pos2 = find_target(next_target + 1);
            int v2_idx = 10 + (pos2.second / 2);

            if (v2_idx != v_idx && pos2.first >= 2) {
                // T1の横移動でどれだけシフトするかを計算
                int t1_col = pos1.second; 
                int diff = (GOAL_IDX_IN_ROW0 - t1_col + 40) % 40;
                int shift = (diff <= 20) ? diff : -(40 - diff);
                
                // T2がそのままの場合のゴールへの距離
                int t2_col = pos2.second;
                int orig_dist = abs(GOAL_IDX_IN_ROW0 - t2_col);
                orig_dist = min(orig_dist, 40 - orig_dist);
                
                // T2がT1の横移動に便乗した場合のゴールへの距離
                int new_t2_col = (t2_col + shift + 40) % 40;
                int new_dist = abs(GOAL_IDX_IN_ROW0 - new_t2_col);
                new_dist = min(new_dist, 40 - new_dist);

                // 便乗することでT2がゴールに「確実に近づく」場合のみ上に引き上げる
                if (new_dist < orig_dist) {
                    int v2_goal_idx = -1;
                    for (int idx = 0; idx < conveyors[v2_idx].length; ++idx) {
                        if (conveyors[v2_idx].cells[idx].first == 0 && conveyors[v2_idx].cells[idx].second == pos2.second) {
                            v2_goal_idx = idx;
                            break;
                        }
                    }
                    move_target_to_idx(v2_idx, pos2, v2_goal_idx);
                }
            }
        }

        // T1の位置を再取得
        pos1 = find_target(next_target);

        // ステップB: 「横ループ0」を使って搬出口まで運ぶ
        move_target_to_idx(0, pos1, GOAL_IDX_IN_ROW0);

        // 搬出完了
        a[EXIT_I][EXIT_J] = -1;
        next_target++;
    }

    // 3. 出力
    cout << conveyors.size() << "\n";
    for (const auto& conv : conveyors) {
        cout << conv.length;
        for (const auto& cell : conv.cells) cout << " " << cell.first << " " << cell.second;
        cout << "\n";
    }
    cout << operations.size() << "\n";
    for (const auto& op : operations) {
        cout << op.m << " " << op.d << "\n";
    }

    return 0;
}

Submission Info

Judge Result