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

• 問題: No.3506 All Distance is Square Number
• ユーザー: はじっこゆーれー
• 提出日時: 2026-04-19 05:04:12
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 4,045 bytes
• コンパイル時間: 1,963 ms
• コンパイル使用メモリ: 202,776 KB
• 実行使用メモリ: 7,968 KB
• 最終ジャッジ日時: 2026-04-19 05:04:21
• 合計ジャッジ時間: 4,571 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_1

ファイルパターン	結果
other	AC * 3 WA * 26

ソースコード

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <random>
using namespace std;
const int MAX_SUM = 50000;
bool is_sq_arr[MAX_SUM + 5];
inline bool is_sq(int n) {
    if (n < 0 || n > MAX_SUM) return false;
    return is_sq_arr[n];
}
int N;
int W[105];
bool used_w[205];
vector<int> evens;
mt19937 rng(42);
int tree_dist_func(int a, int b) {
    return abs((a - 1) * (a - 1) - (b - 1) * (b - 1));
}
int get_edge_1(int x) {
    if (x == 2) return 1;
    return N - 3 + x;
}
vector<int> get_tree_edges(int a, int b) {
    vector<int> res;
    if (a < b) {
        for (int k = a; k < b; ++k) res.push_back(k);
    } else {
        for (int k = a - 1; k >= b; --k) res.push_back(k);
    }
    return res;
}
vector<int> build_path(int u, int v) {
    if (is_sq(tree_dist_func(u, v))) {
        return get_tree_edges(u, v);
    }
    for (int x = 2; x <= N; ++x) {
        for (int y = 2; y <= N; ++y) {
            int min_ux = min(u, x), max_ux = max(u, x);
            int min_vy = min(v, y), max_vy = max(v, y);
            if (max_ux < min_vy || max_vy < min_ux) {
                int w = tree_dist_func(u, x) + W[x] + W[y] + tree_dist_func(y, v);
                if (is_sq(w)) {
                    vector<int> path;
                    vector<int> p1 = get_tree_edges(u, x);
                    path.insert(path.end(), p1.begin(), p1.end());
                    path.push_back(get_edge_1(x));
                    path.push_back(get_edge_1(y));
                    vector<int> p2 = get_tree_edges(y, v);
                    path.insert(path.end(), p2.begin(), p2.end());
                    return path;
                }
            }
        }
    }
    return {};
}
bool assign_W(int j) {
    if (j > N) return true;
    vector<int> unsatisfied_i;
    for (int i = 2; i < j; ++i) {
        bool ok = false;
        if (is_sq(tree_dist_func(i, j))) ok = true;
        if (!ok) {
            for (int x = 2; x < j && !ok; ++x) {
                for (int y = max(i, x) + 1; y < j && !ok; ++y) {
                    int w_path = tree_dist_func(i, x) + W[x] + W[y] + tree_dist_func(y, j);
                    if (is_sq(w_path)) ok = true;
                }
            }
        }
        if (!ok) unsatisfied_i.push_back(i);
    }
    vector<vector<int>> bases(105);
    for (int i : unsatisfied_i) {
        for (int x = 2; x < j; ++x) {
            bases[i].push_back(tree_dist_func(i, x) + W[x]);
        }
    }
    vector<int> local_evens;
    for (int w : evens) {
        if (!used_w[w]) local_evens.push_back(w);
    }
    shuffle(local_evens.begin(), local_evens.end(), rng);
    for (int w : local_evens) {
        bool ok_w = true;
        for (int i : unsatisfied_i) {
            bool ok_i = false;
            for (int b : bases[i]) {
                if (is_sq(b + w)) {
                    ok_i = true;
                    break;
                }
            }
            if (!ok_i) {
                ok_w = false;
                break;
            }
        }
        if (ok_w) {
            W[j] = w;
            used_w[w] = true;
            if (assign_W(j + 1)) return true;
            used_w[w] = false;
        }
    }
    return false;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    for (int i = 0; i * i <= MAX_SUM; ++i) {
        is_sq_arr[i * i] = true;
    }
    if (!(cin >> N)) return 0;
    for (int i = 2; i <= 200; i += 2) {
        evens.push_back(i);
    }
    W[2] = 1;
    if (!assign_W(3)) {
        return 0;
    }
    int M = (N == 2) ? 1 : 2 * N - 3;
    cout << M << "\n";
    for (int i = 1; i < N; ++i) {
        cout << i << " " << i + 1 << " " << 2 * i - 1 << "\n";
    }
    for (int j = 3; j <= N; ++j) {
        cout << 1 << " " << j << " " << W[j] << "\n";
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            vector<int> path = build_path(i, j);
            cout << path.size();
            for (int e : path) cout << " " << e;
            cout << "\n";
        }
    }
    return 0;
}