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

• 問題: No.3506 All Distance is Square Number
• ユーザー: gojoxd
• 提出日時: 2026-04-18 15:07:35
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 7,338 bytes
• コンパイル時間: 1,749 ms
• コンパイル使用メモリ: 227,812 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-04-18 15:07:52
• 合計ジャッジ時間: 12,636 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_1

ファイルパターン	結果
other	AC * 25 WA * 4

ソースコード

#include <iostream>
#include <vector>
#include <cmath>
#include <random>
#include <chrono>
#include <algorithm>
#include <numeric>

using namespace std;

// Precompute perfect squares up to the maximum possible sum (~800)
bool is_sq[200005];

int main() {
    // Optimize input/output operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    for (int i = 1; i * i < 200005; ++i) {
        is_sq[i * i] = true;
    }

    int N;
    if (!(cin >> N)) return 0;
    
    // Base Case
    if (N == 2) {
        cout << 1 << "\n";
        cout << 1 << " " << 2 << " " << 1 << "\n";
        cout << 1 << " " << 1 << "\n";
        return 0;
    }

    int M = 2 * N - 3;
    vector<int> vals(200);
    iota(vals.begin(), vals.end(), 1); // Fill with available weights 1 to 200
    
    mt19937 rng(1337);
    shuffle(vals.begin(), vals.end(), rng);
    
    int W = vals[0];
    vector<int> X(N + 1), Y(N + 1);
    for (int i = 3; i <= N; ++i) {
        X[i] = vals[2 * i - 5];
        Y[i] = vals[2 * i - 4];
    }
    
    // Calculates how many pairs of vertices DO NOT have a square-sum path
    auto get_score = [&]() {
        int bad = 0;
        bool ok;
        
        // Check paths between 1 and 2
        ok = is_sq[W];
        if (!ok) {
            for (int k = 3; k <= N; ++k) {
                if (is_sq[X[k] + Y[k]]) { ok = true; break; }
            }
        }
        if (!ok) bad++;
        
        // Check paths between 1 and v
        for (int v = 3; v <= N; ++v) {
            ok = is_sq[X[v]] || is_sq[W + Y[v]];
            if (!ok) {
                for (int k = 3; k <= N; ++k) {
                    if (k == v) continue;
                    if (is_sq[X[k] + Y[k] + Y[v]]) { ok = true; break; }
                }
            }
            if (!ok) bad++;
        }
        
        // Check paths between 2 and v
        for (int v = 3; v <= N; ++v) {
            ok = is_sq[Y[v]] || is_sq[W + X[v]];
            if (!ok) {
                for (int k = 3; k <= N; ++k) {
                    if (k == v) continue;
                    if (is_sq[Y[k] + X[k] + X[v]]) { ok = true; break; }
                }
            }
            if (!ok) bad++;
        }
        
        // Check paths between leaf u and leaf v
        for (int u = 3; u <= N; ++u) {
            for (int v = u + 1; v <= N; ++v) {
                ok = is_sq[X[u] + X[v]] || is_sq[Y[u] + Y[v]] || 
                     is_sq[X[u] + W + Y[v]] || is_sq[Y[u] + W + X[v]];
                if (!ok) {
                    for (int k = 3; k <= N; ++k) {
                        if (k == u || k == v) continue;
                        if (is_sq[X[u] + X[k] + Y[k] + Y[v]] || 
                            is_sq[Y[u] + Y[k] + X[k] + X[v]]) { 
                            ok = true; break; 
                        }
                    }
                }
                if (!ok) bad++;
            }
        }
        return bad;
    };
    
    int best_score = get_score();
    auto start_time = chrono::steady_clock::now();
    int iters = 0;
    
    // Hill Climbing 
    while (best_score > 0) {
        auto now = chrono::steady_clock::now();
        if (chrono::duration<double>(now - start_time).count() > 1.8) break; 
        
        int type = rng() % 2;
        int idx1 = rng() % M;
        int idx2 = (type == 0) ? (rng() % M) : (M + (rng() % (200 - M)));
        
        swap(vals[idx1], vals[idx2]);
        
        W = vals[0];
        for (int i = 3; i <= N; ++i) {
            X[i] = vals[2 * i - 5];
            Y[i] = vals[2 * i - 4];
        }
        
        int new_score = get_score();
        if (new_score <= best_score) {
            best_score = new_score;
        } else { // Rollback if the new state is worse
            swap(vals[idx1], vals[idx2]);
            W = vals[0];
            for (int i = 3; i <= N; ++i) {
                X[i] = vals[2 * i - 5];
                Y[i] = vals[2 * i - 4];
            }
        }
        
        // Perform a complete reset if caught in a local minima
        iters++;
        if (iters % 3000 == 0 && best_score > 0) {
            shuffle(vals.begin(), vals.end(), rng);
            W = vals[0];
            for (int i = 3; i <= N; ++i) {
                X[i] = vals[2 * i - 5];
                Y[i] = vals[2 * i - 4];
            }
            best_score = get_score();
        }
    }

    // --- Output Geometry & Edge Weights ---
    cout << M << "\n";
    cout << "1 2 " << W << "\n";
    for (int i = 3; i <= N; ++i) {
        cout << "1 " << i << " " << X[i] << "\n";
        cout << "2 " << i << " " << Y[i] << "\n";
    }
    
    // Helper lambda to print array paths
    auto print_path = [&](const vector<int>& p) {
        cout << p.size();
        for (int e : p) cout << " " << e;
        cout << "\n";
    };

    // --- Retrieve paths mapped chronologically ---
    for (int u = 1; u <= N; ++u) {
        for (int v = u + 1; v <= N; ++v) {
            
            if (u == 1 && v == 2) {
                if (is_sq[W]) { print_path({1}); continue; }
                bool found = false;
                for (int k = 3; k <= N; ++k) {
                    if (is_sq[X[k] + Y[k]]) { print_path({2*k-4, 2*k-3}); found = true; break; }
                }
                if (!found) print_path({1}); 
                continue;
            }
            
            if (u == 1) {
                if (is_sq[X[v]]) { print_path({2*v-4}); continue; }
                if (is_sq[W + Y[v]]) { print_path({1, 2*v-3}); continue; }
                bool found = false;
                for (int k = 3; k <= N; ++k) {
                    if (k == v) continue;
                    if (is_sq[X[k] + Y[k] + Y[v]]) { print_path({2*k-4, 2*k-3, 2*v-3}); found = true; break; }
                }
                if (!found) print_path({2*v-4});
                continue;
            }
            
            if (u == 2) {
                if (is_sq[Y[v]]) { print_path({2*v-3}); continue; }
                if (is_sq[W + X[v]]) { print_path({1, 2*v-4}); continue; }
                bool found = false;
                for (int k = 3; k <= N; ++k) {
                    if (k == v) continue;
                    if (is_sq[Y[k] + X[k] + X[v]]) { print_path({2*k-3, 2*k-4, 2*v-4}); found = true; break; }
                }
                if (!found) print_path({2*v-3});
                continue;
            }
            
            // u >= 3 and v >= 3
            if (is_sq[X[u] + X[v]]) { print_path({2*u-4, 2*v-4}); continue; }
            if (is_sq[Y[u] + Y[v]]) { print_path({2*u-3, 2*v-3}); continue; }
            if (is_sq[X[u] + W + Y[v]]) { print_path({2*u-4, 1, 2*v-3}); continue; }
            if (is_sq[Y[u] + W + X[v]]) { print_path({2*u-3, 1, 2*v-4}); continue; }
            bool found = false;
            for (int k = 3; k <= N; ++k) {
                if (k == u || k == v) continue;
                if (is_sq[X[u] + X[k] + Y[k] + Y[v]]) {
                    print_path({2*u-4, 2*k-4, 2*k-3, 2*v-3});
                    found = true; break;
                }
                if (is_sq[Y[u] + Y[k] + X[k] + X[v]]) {
                    print_path({2*u-3, 2*k-3, 2*k-4, 2*v-4});
                    found = true; break;
                }
            }
            if (!found) print_path({2*u-4, 2*v-4});
        }
    }
    
    return 0;
}