結果

問題 No.3506 All Distance is Square Number
コンテスト
ユーザー はじっこゆーれー
提出日時 2026-04-18 07:15:41
言語 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
結果
TLE  
実行時間 -
コード長 6,521 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,104 ms
コンパイル使用メモリ 240,984 KB
実行使用メモリ 7,972 KB
最終ジャッジ日時 2026-04-18 07:16:13
合計ジャッジ時間 10,836 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
using namespace std;
int N;
int W_edge[105];
vector<int> unused_even;
int adj_to[105][5];
int adj_weight[105][5];
int adj_id[105][5];
int adj_deg[105];
bool is_sq[40005];
void build_adj() {
    for(int i=1; i<=N; ++i) adj_deg[i] = 0;
    for(int i=1; i<N; ++i) {
        adj_to[i][adj_deg[i]] = i+1; adj_weight[i][adj_deg[i]] = 2*i-1; adj_id[i][adj_deg[i]] = i; adj_deg[i]++;
        adj_to[i+1][adj_deg[i+1]] = i; adj_weight[i+1][adj_deg[i+1]] = 2*i-1; adj_id[i+1][adj_deg[i+1]] = i; adj_deg[i+1]++;
    }
    for(int k=1; k<=N-2; ++k) {
        adj_to[k][adj_deg[k]] = k+2; adj_weight[k][adj_deg[k]] = W_edge[k]; adj_id[k][adj_deg[k]] = N-1+k; adj_deg[k]++;
        adj_to[k+2][adj_deg[k+2]] = k; adj_weight[k+2][adj_deg[k+2]] = W_edge[k]; adj_id[k+2][adj_deg[k+2]] = N-1+k; adj_deg[k+2]++;
    }
}
int evaluate_graph() {
    int missing = 0;
    static int q_u[4005];
    static int q_sum[4005];
    static unsigned __int128 q_vis[4005];
    for (int i = 1; i < N; ++i) {
        int needed = N - i;
        int found = 0;
        bool ok[105] = {false};
        int head = 0, tail = 0;
        q_u[tail] = i; q_sum[tail] = 0; q_vis[tail] = ((unsigned __int128)1 << i); tail++;
        while(head < tail && head < 1500 && found < needed) {
            int u = q_u[head];
            int sum = q_sum[head];
            unsigned __int128 vmask = q_vis[head];
            head++;
            if (u > i && sum > 0 && is_sq[sum] && !ok[u]) {
                ok[u] = true;
                found++;
                if (found == needed) break;
            }
            for(int k = 0; k < adj_deg[u]; ++k) {
                int v = adj_to[u][k];
                if (!((vmask >> v) & 1)) {
                    int nsum = sum + adj_weight[u][k];
                    if (nsum < 40005 && tail < 4000) {
                        q_u[tail] = v; q_sum[tail] = nsum; q_vis[tail] = vmask | ((unsigned __int128)1 << v); tail++;
                    }
                }
            }
        }
        missing += (needed - found);
    }
    return missing;
}
struct QState { int u; int sum; unsigned __int128 vis; short path[105]; short len; };
QState q_out[30005];
vector<int> solve_path(int start, int target) {
    int head = 0, tail = 0;
    q_out[tail].u = start; q_out[tail].sum = 0; q_out[tail].vis = ((unsigned __int128)1 << start); q_out[tail].len = 0; tail++;
    while(head < tail) {
        QState curr = q_out[head++];
        if (curr.u == target && curr.sum > 0 && is_sq[curr.sum]) {
            vector<int> res;
            for(int i=0; i<curr.len; ++i) res.push_back(curr.path[i]);
            return res;
        }
        for(int k=0; k<adj_deg[curr.u]; ++k) {
            int v = adj_to[curr.u][k];
            if (!((curr.vis >> v) & 1)) {
                int nsum = curr.sum + adj_weight[curr.u][k];
                if (nsum < 40005 && tail < 30000) {
                    q_out[tail].u = v; q_out[tail].sum = nsum; q_out[tail].vis = curr.vis | ((unsigned __int128)1 << v);
                    for(int p=0; p<curr.len; ++p) q_out[tail].path[p] = curr.path[p];
                    q_out[tail].path[curr.len] = adj_id[curr.u][k]; q_out[tail].len = curr.len + 1; tail++;
                }
            }
        }
    }
    return {};
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (!(cin >> N)) return 0;
    for (int i = 0; i < 40005; ++i) is_sq[i] = false;
    for (int i = 1; i * i < 40005; ++i) is_sq[i * i] = true;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    int odd_squares[] = {9, 25, 49, 81, 121, 169, 225, 289, 361};
    bool used_init[205] = {false};
    for(int k=1; k<=N-2; ++k) {
        vector<int> magics;
        for(int s : odd_squares) {
            int w = s - (2*k - 1);
            if(w >= 2 && w <= 200 && w % 2 == 0 && !used_init[w]) magics.push_back(w);
        }
        if(!magics.empty()) {
            int chosen = magics[rng() % magics.size()];
            W_edge[k] = chosen;
            used_init[chosen] = true;
        } else {
            W_edge[k] = 0;
        }
    }
    for(int i=2; i<=200; i+=2) {
        if(!used_init[i]) unused_even.push_back(i);
    }
    shuffle(unused_even.begin(), unused_even.end(), rng);
    for(int k=1; k<=N-2; ++k) {
        if(W_edge[k] == 0) {
            W_edge[k] = unused_even.back(); unused_even.pop_back();
        }
    }
    build_adj();
    int best_score = evaluate_graph();
    int no_improve = 0;
    while (best_score > 0) {
        int r1 = rng() % (N - 2) + 1;
        int type = rng() % 2;
        int old_w1 = W_edge[r1];
        if (type == 0 && !unused_even.empty()) {
            int idx = rng() % unused_even.size();
            int old_w2 = unused_even[idx];
            W_edge[r1] = old_w2;
            build_adj();
            int new_score = evaluate_graph();
            if (new_score <= best_score) {
                best_score = new_score; unused_even[idx] = old_w1; no_improve = 0;
            } else {
                W_edge[r1] = old_w1; build_adj(); no_improve++;
            }
        } else {
            int r2 = rng() % (N - 2) + 1;
            if (r1 == r2) continue;
            swap(W_edge[r1], W_edge[r2]);
            build_adj();
            int new_score = evaluate_graph();
            if (new_score <= best_score) {
                best_score = new_score; no_improve = 0;
            } else {
                swap(W_edge[r1], W_edge[r2]); build_adj(); no_improve++;
            }
        }
        if (no_improve > 300) {
            for(int step=0; step<3; ++step) {
                int a = rng() % (N - 2) + 1;
                int b = rng() % (N - 2) + 1;
                swap(W_edge[a], W_edge[b]);
            }
            build_adj();
            best_score = evaluate_graph();
            no_improve = 0;
        }
    }
    cout << (2 * N - 3) << "\n";
    for (int i = 1; i < N; ++i) cout << i << " " << (i + 1) << " " << (2 * i - 1) << "\n";
    for (int k = 1; k <= N - 2; ++k) cout << k << " " << (k + 2) << " " << W_edge[k] << "\n";
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            vector<int> path = solve_path(i, j);
            cout << path.size() << "\n";
            for (int k = 0; k < path.size(); ++k) {
                cout << path[k] << (k == path.size() - 1 ? "" : " ");
            }
            cout << "\n";
        }
    }
    return 0;
}
0