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

• 問題: No.3506 All Distance is Square Number
• ユーザー: Naru820
• 提出日時: 2026-03-18 00:13:50
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 4,082 bytes
• コンパイル時間: 3,861 ms
• コンパイル使用メモリ: 349,512 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-04-17 19:41:39
• 合計ジャッジ時間: 10,095 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_1

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

ソースコード

// GPT 5.4-pro
#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, w;
};

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

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

    int N;
    cin >> N;

    vector<char> is_sq(1000, false);
    for (int x = 0; x * x < (int)is_sq.size(); ++x) is_sq[x * x] = true;

    vector<Edge> edges;
    edges.reserve(max(1, 2 * N - 3));
    edges.push_back({0, 1, 1}); // edge 0

    for (int t = 0; t < N - 2; ++t) {
        int v = t + 2;
        edges.push_back({0, v, PRE[2 * t]});     // edge 2t+1
        edges.push_back({1, v, PRE[2 * t + 1]}); // edge 2t+2
    }

    auto eid0 = [&](int v) -> int {
        return 1 + 2 * (v - 2);
    };
    auto eid1 = [&](int v) -> int {
        return 2 + 2 * (v - 2);
    };
    auto path_is_square = [&](const vector<int>& ids) -> bool {
        int sum = 0;
        for (int id : ids) sum += edges[id].w;
        return is_sq[sum];
    };

    vector<vector<vector<int>>> ans(N, vector<vector<int>>(N));

    auto set_if_square = [&](int i, int j, const vector<int>& ids) -> bool {
        if (path_is_square(ids)) {
            ans[i][j] = ids;
            return true;
        }
        return false;
    };

    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            bool ok = false;
            if (i == 0 && j == 1) {
                ok = set_if_square(i, j, {0});
            } else if (i == 0 && j >= 2) {
                ok = set_if_square(i, j, {eid0(j)});
                if (!ok) ok = set_if_square(i, j, {0, eid1(j)});
                for (int k = 2; !ok && k < N; ++k) if (k != j) {
                    ok = set_if_square(i, j, {eid0(k), eid1(k), eid1(j)});
                }
            } else if (i == 1 && j >= 2) {
                ok = set_if_square(i, j, {eid1(j)});
                if (!ok) ok = set_if_square(i, j, {0, eid0(j)});
                for (int k = 2; !ok && k < N; ++k) if (k != j) {
                    ok = set_if_square(i, j, {eid1(k), eid0(k), eid0(j)});
                }
            } else {
                ok = set_if_square(i, j, {eid0(i), eid0(j)});
                if (!ok) ok = set_if_square(i, j, {eid1(i), eid1(j)});
                if (!ok) ok = set_if_square(i, j, {eid0(i), 0, eid1(j)});
                if (!ok) ok = set_if_square(i, j, {eid1(i), 0, eid0(j)});
                for (int k = 2; !ok && k < N; ++k) if (k != i && k != j) {
                    ok = set_if_square(i, j, {eid0(i), eid0(k), eid1(k), eid1(j)});
                    if (!ok) ok = set_if_square(i, j, {eid1(i), eid1(k), eid0(k), eid0(j)});
                }
            }
            if (!ok) {
                cerr << "construction failed at pair (" << i << "," << j << ")\n";
                return 1;
            }
        }
    }


    cout << edges.size() << '\n';
    for (const auto& e : edges) {
        cout << e.u << ' ' << e.v << ' ' << e.w << '\n';
    }
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            cout << ans[i][j].size();
            for (int id : ans[i][j]) cout << ' ' << id;
            cout << '\n';
        }
    }
    return 0;
}