結果

問題 No.3506 All Distance is Square Number
コンテスト
ユーザー はじっこゆーれー
提出日時 2026-04-18 07:50:57
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,723 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,736 ms
コンパイル使用メモリ 352,900 KB
実行使用メモリ 7,976 KB
最終ジャッジ日時 2026-04-18 07:51:04
合計ジャッジ時間 4,586 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 5 RE * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
bool is_sq(int x) {
    if (x < 0) return false;
    int r = (int)sqrt(x);
    while (r*r < x) ++r;
    while (r*r > x) --r;
    return r*r == x;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<array<int,3>> edges;
    auto add = [&](int u, int v, int w) {
        edges.push_back({u, v, w});
        return (int)edges.size();
    };
    int e12 = add(1, 2, 1);
    vector<int> a(N+1), b(N+1);
    vector<int> e1(N+1), e2(N+1);
    vector<bool> used(201, false);
    used[1] = true;
    for (int i = 3; i <= N; ++i) {
        bool found = false;
        for (int av = 2; av <= 200 && !found; ++av) {
            if (used[av]) continue;
            for (int S : {196, 225, 169, 144, 256, 121, 289, 100, 324, 361, 64, 400}) {
                int bv = S - 1 - av;
                if (bv < 1 || bv > 200 || used[bv] || av == bv) continue;
                bool ok = true;
                for (int j = 3; j < i; ++j) {
                    if (!is_sq(av + a[j]) && !is_sq(bv + b[j]) &&
                        !is_sq(av + 1 + b[j]) && !is_sq(bv + 1 + a[j])) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    a[i] = av; b[i] = bv;
                    used[av] = used[bv] = true;
                    e1[i] = add(1, i, av);
                    e2[i] = add(2, i, bv);
                    found = true;
                    break;
                }
            }
        }
        if (!found) {
            cerr << "Failed\n";
            return 1;
        }
    }
    vector<vector<vector<int>>> path(N+1, vector<vector<int>>(N+1));
    auto setp = [&](int i, int j, const vector<int>& v) { path[i][j] = v; };
    setp(1, 2, {e12});
    for (int i = 3; i <= N; ++i) {
        setp(1, i, {e1[i]});
        setp(2, i, {e2[i]});
    }
    for (int i = 3; i <= N; ++i) {
        for (int j = i+1; j <= N; ++j) {
            vector<pair<int, vector<int>>> cand = {
                {a[i]+a[j], {e1[i], e1[j]}},
                {b[i]+b[j], {e2[i], e2[j]}},
                {a[i]+1+b[j], {e1[i], e12, e2[j]}},
                {b[i]+1+a[j], {e2[i], e12, e1[j]}}
            };
            for (auto& [sum, ids] : cand) {
                if (is_sq(sum)) { setp(i, j, ids); break; }
            }
        }
    }
    cout << edges.size() << "\n";
    for (auto& [u,v,w] : edges) cout << u << " " << v << " " << w << "\n";
    for (int i = 1; i <= N; ++i) {
        for (int j = i+1; j <= N; ++j) {
            cout << path[i][j].size();
            for (int id : path[i][j]) cout << " " << id;
            cout << "\n";
        }
    }
}
0