#1160616 (C++23) No.3506 All Distance is Square Number

• 問題: No.3506 All Distance is Square Number
• ユーザー: YuukunA
• 提出日時: 2026-04-19 18:49:14
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 3,863 bytes
• コンパイル時間: 1,963 ms
• コンパイル使用メモリ: 166,132 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-04-19 18:49:24
• 合計ジャッジ時間: 3,157 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

ファイルパターン	結果
other	AC * 29

ソースコード

#include <array>
#include <iostream>
#include <vector>
using namespace std;

static constexpr int C = 9;
static constexpr int W[98][2] = {
    {4, 16},
    {100, 36},
    {55, 33},
    {81, 105},
    {91, 8},
    {7, 12},
    {144, 1},
    {44, 56},
    {69, 156},
    {45, 5},
    {64, 13},
    {21, 17},
    {120, 62},
    {31, 6},
    {112, 39},
    {63, 131},
    {94, 14},
    {130, 67},
    {83, 135},
    {38, 26},
    {18, 2},
    {117, 43},
    {125, 65},
    {27, 22},
    {29, 80},
    {49, 25},
    {15, 95},
    {124, 30},
    {151, 57},
    {99, 107},
    {88, 111},
    {187, 161},
    {40, 61},
    {87, 32},
    {66, 86},
    {72, 19},
    {118, 28},
    {102, 48},
    {52, 24},
    {194, 74},
    {182, 68},
    {103, 10},
    {162, 23},
    {89, 190},
    {173, 53},
    {168, 11},
    {46, 79},
    {51, 70},
    {149, 160},
    {136, 77},
    {78, 147},
    {170, 127},
    {60, 121},
    {42, 98},
    {142, 96},
    {181, 119},
    {175, 116},
    {159, 129},
    {196, 85},
    {139, 35},
    {76, 93},
    {143, 104},
    {191, 84},
    {171, 137},
    {198, 73},
    {71, 109},
    {178, 50},
    {177, 158},
    {174, 122},
    {133, 47},
    {184, 20},
    {123, 180},
    {165, 164},
    {82, 145},
    {192, 97},
    {110, 34},
    {172, 58},
    {157, 167},
    {141, 134},
    {152, 166},
    {126, 193},
    {176, 59},
    {92, 195},
    {189, 90},
    {155, 101},
    {115, 54},
    {113, 197},
    {200, 108},
    {199, 37},
    {75, 150},
    {138, 188},
    {146, 179},
    {153, 148},
    {132, 140},
    {169, 3},
    {183, 106},
    {114, 128},
    {154, 185}
};

static array<bool, 1001> is_square;

static inline int a(int k) {
    return W[k - 3][0];
}

static inline int b(int k) {
    return W[k - 3][1];
}

static inline int aid(int k) {
    return 2 * (k - 3) + 2;
}

static inline int bid(int k) {
    return 2 * (k - 3) + 3;
}

static vector<int> find_path(int n, int s, int t) {
    if (s == 1 && t == 2) return {1};

    if (s == 1) {
        int k = t;
        if (is_square[a(k)]) return {aid(k)};
        if (is_square[C + b(k)]) return {1, bid(k)};
        for (int x = 3; x <= n; x++) {
            if (x != k && is_square[a(x) + b(x) + b(k)]) {
                return {aid(x), bid(x), bid(k)};
            }
        }
    }

    if (s == 2) {
        int k = t;
        if (is_square[b(k)]) return {bid(k)};
        if (is_square[C + a(k)]) return {1, aid(k)};
        for (int x = 3; x <= n; x++) {
            if (x != k && is_square[a(x) + b(x) + a(k)]) {
                return {bid(x), aid(x), aid(k)};
            }
        }
    }

    int i = s, j = t;
    if (is_square[a(i) + a(j)]) return {aid(i), aid(j)};
    if (is_square[b(i) + b(j)]) return {bid(i), bid(j)};
    if (is_square[a(i) + C + b(j)]) return {aid(i), 1, bid(j)};
    if (is_square[b(i) + C + a(j)]) return {bid(i), 1, aid(j)};

    for (int x = 3; x <= n; x++) {
        if (x == i || x == j) continue;
        if (is_square[a(i) + a(x) + b(x) + b(j)]) {
            return {aid(i), aid(x), bid(x), bid(j)};
        }
        if (is_square[b(i) + b(x) + a(x) + a(j)]) {
            return {bid(i), bid(x), aid(x), aid(j)};
        }
    }

    return {};
}

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

    for (int x = 0; x * x < (int)is_square.size(); x++) {
        is_square[x * x] = true;
    }

    int n;
    cin >> n;

    cout << 2 * n - 3 << '\n';
    cout << "1 2 " << C << '\n';
    for (int k = 3; k <= n; k++) {
        cout << "1 " << k << ' ' << a(k) << '\n';
        cout << "2 " << k << ' ' << b(k) << '\n';
    }

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            vector<int> path = find_path(n, i, j);
            cout << path.size();
            for (int id : path) cout << ' ' << id;
            cout << '\n';
        }
    }

    return 0;
}