#1172711 (C++23(gcc16)) No.3735 Offbeat Permutation Tree

• 問題: No.3735 Offbeat Permutation Tree
• ユーザー: 👑 kencho
• 提出日時: 2026-07-24 11:04:48
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 65 ms / 2,000 ms
• コード長: 6,644 bytes
• コンパイル時間: 3,209 ms
• コンパイル使用メモリ: 370,132 KB
• 実行使用メモリ: 30,356 KB
• 最終ジャッジ日時: 2026-09-19 12:37:06
• 合計ジャッジ時間: 8,165 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_0

ファイルパターン	結果
sample	AC * 2
other	AC * 35

ソースコード

#include <bits/stdc++.h>
using namespace std;

struct Candidate {
    int column;
    int position;
    vector<int> alternatives;
    bool enabled = true;
};

vector<int> snake_path(int n) {
    vector<int> path;
    path.reserve(n * n);
    for (int r = 0; r < n; ++r) {
        if (r % 2 == 0) {
            for (int c = 0; c < n; ++c) path.push_back(r * n + c);
        } else {
            for (int c = n - 1; c >= 0; --c) path.push_back(r * n + c);
        }
    }
    return path;
}

vector<vector<int>> backbite_paths(const vector<int>& original, int n) {
    vector<vector<int>> result;
    for (int reverse_path = 0; reverse_path < 2; ++reverse_path) {
        vector<int> path = original;
        if (reverse_path) reverse(path.begin(), path.end());
        vector<int> index(n * n);
        for (int i = 0; i < (int)path.size(); ++i) index[path[i]] = i;
        int endpoint = path.back();
        int r = endpoint / n, c = endpoint % n;
        const int dr[4] = {-1, 1, 0, 0};
        const int dc[4] = {0, 0, -1, 1};
        for (int d = 0; d < 4; ++d) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
            int cut = index[nr * n + nc];
            if (cut >= (int)path.size() - 2) continue;
            vector<int> next = path;
            reverse(next.begin() + cut + 1, next.end());
            if (reverse_path) reverse(next.begin(), next.end());
            result.push_back(move(next));
        }
    }
    return result;
}

bool construct_from_path(const vector<int>& path, int n,
                         vector<pair<int, int>>& answer) {
    const int vertices = n * n;
    vector<int> index(vertices);
    for (int i = 0; i < vertices; ++i) index[path[i]] = i;

    int first = path.front(), last = path.back();
    int first_row = first / n, first_col = first % n;
    int last_row = last / n, last_col = last % n;
    if (first_row == last_row || first_col == last_col) return false;

    vector<unsigned char> forced_row(n, 0), forced_col(n, 0);
    forced_row[first_row] = forced_row[last_row] = 1;
    forced_col[first_col] = forced_col[last_col] = 1;

    vector<vector<Candidate>> candidates(n);
    const int dr[4] = {-1, 1, 0, 0};
    const int dc[4] = {0, 0, -1, 1};
    for (int position = 1; position + 1 < vertices; ++position) {
        int leaf = path[position];
        int row = leaf / n, column = leaf % n;
        if (forced_row[row] || forced_col[column]) continue;
        int successor = path[position + 1];
        int sr = successor / n, sc = successor % n;
        vector<int> alternatives;
        for (int d = 0; d < 4; ++d) {
            int nr = sr + dr[d], nc = sc + dc[d];
            if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
            int other = nr * n + nc;
            if (other != leaf && index[other] <= position) alternatives.push_back(other);
        }
        if (!alternatives.empty()) {
            candidates[row].push_back({column, position, move(alternatives), true});
        }
    }

    for (int retry = 0; retry <= n * n; ++retry) {
        vector<int> matched_row(n, -1), chosen_candidate(n, -1);
        function<bool(int, vector<unsigned char>&)> augment =
                [&](int row, vector<unsigned char>& used_column) {
            for (int i = 0; i < (int)candidates[row].size(); ++i) {
                const Candidate& candidate = candidates[row][i];
                if (!candidate.enabled || used_column[candidate.column]) continue;
                used_column[candidate.column] = 1;
                int previous_row = matched_row[candidate.column];
                if (previous_row == -1 || augment(previous_row, used_column)) {
                    matched_row[candidate.column] = row;
                    chosen_candidate[row] = i;
                    return true;
                }
            }
            return false;
        };

        bool matched = true;
        for (int row = 0; row < n; ++row) {
            if (forced_row[row]) continue;
            vector<unsigned char> used_column(n, 0);
            if (!augment(row, used_column)) {
                matched = false;
                break;
            }
        }
        if (!matched) return false;

        vector<unsigned char> is_leaf(vertices, 0);
        is_leaf[first] = is_leaf[last] = 1;
        for (int row = 0; row < n; ++row) {
            if (!forced_row[row]) {
                is_leaf[row * n + candidates[row][chosen_candidate[row]].column] = 1;
            }
        }

        int bad_row = -1;
        vector<int> attachment(n, -1);
        for (int row = 0; row < n; ++row) {
            if (forced_row[row]) continue;
            Candidate& candidate = candidates[row][chosen_candidate[row]];
            for (int other : candidate.alternatives) {
                if (!is_leaf[other]) {
                    attachment[row] = other;
                    break;
                }
            }
            if (attachment[row] == -1) {
                bad_row = row;
                candidate.enabled = false;
                break;
            }
        }
        if (bad_row != -1) continue;

        vector<unsigned char> removed(vertices - 1, 0);
        vector<pair<int, int>> added;
        for (int row = 0; row < n; ++row) {
            if (forced_row[row]) continue;
            const Candidate& candidate = candidates[row][chosen_candidate[row]];
            removed[candidate.position] = 1;
            added.push_back({path[candidate.position + 1], attachment[row]});
        }

        answer.clear();
        answer.reserve(vertices - 1);
        for (int i = 0; i + 1 < vertices; ++i) {
            if (!removed[i]) answer.push_back({path[i], path[i + 1]});
        }
        answer.insert(answer.end(), added.begin(), added.end());
        return (int)answer.size() == vertices - 1;
    }
    return false;
}

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

    int n;
    cin >> n;
    if (n <= 3) {
        cout << -1 << '\n';
        return 0;
    }

    vector<vector<int>> queue;
    queue.push_back(snake_path(n));
    set<vector<int>> seen;
    seen.insert(queue.front());
    vector<pair<int, int>> answer;
    for (size_t head = 0; head < queue.size() && head < 200; ++head) {
        if (construct_from_path(queue[head], n, answer)) {
            for (auto [u, v] : answer) cout << u + 1 << ' ' << v + 1 << '\n';
            return 0;
        }
        for (vector<int>& next : backbite_paths(queue[head], n)) {
            if (seen.insert(next).second) queue.push_back(move(next));
        }
    }
    cout << -1 << '\n';
    return 0;
}