#1182193 (C++23) No.3743 World Mapper

• 問題: No.3743 World Mapper
• ユーザー: 👑 kencho
• 提出日時: 2026-09-03 05:26:31
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 3,425 bytes
• コンパイル時間: 2,496 ms
• コンパイル使用メモリ: 348,340 KB
• 実行使用メモリ: 54,016 KB
• 最終ジャッジ日時: 2026-09-19 13:12:17
• 合計ジャッジ時間: 73,652 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

サブタスク	配点	結果
部分点1	10 %	AC * 4
部分点2	10 %	AC * 9
部分点3	10 %	AC * 14
部分点4	10 %	AC * 14 WA * 5
部分点5	10 %	AC * 14 WA * 10
部分点6	10 %	AC * 14 WA * 15
部分点7	10 %	AC * 14 WA * 20
部分点8	10 %	AC * 14 WA * 25
部分点9	10 %	AC * 14 WA * 30
満点	10 %	AC * 14 WA * 35
合計	5 * 30% = 150 点

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using Clock = chrono::steady_clock;
constexpr int MAX_W = 300000;
constexpr double TIME_LIMIT = 1.9;
constexpr int TRIALS_PER_VERTEX = 300;

int vertical_id(int n, int r, int c) {
    return r * n + c;
}

int horizontal_id(int n, int r, int c) {
    return n * (n - 1) + r * (n - 1) + c;
}

bool construct(int n, mt19937& rng, Clock::time_point deadline, vector<int>& answer) {
    int v = n * n;
    const ll INF = (1LL << 60);
    vector<ll> dist((size_t)v * v, INF), to_new(v);
    dist[0] = 0;
    answer.assign(2 * n * (n - 1), 1);
    uniform_int_distribution<int> weight(1, MAX_W);

    for (int x = 1; x < v; ++x) {
        int r = x / n, c = x % n;
        vector<pair<int, int>> edge;
        if (r > 0) edge.push_back({x - n, vertical_id(n, r - 1, c)});
        if (c > 0) edge.push_back({x - 1, horizontal_id(n, r, c - 1)});

        bool fixed = false;
        for (int trial = 0; trial < TRIALS_PER_VERTEX; ++trial) {
            if (Clock::now() >= deadline) return false;
            vector<int> w(edge.size());
            for (int& z : w) z = weight(rng);

            for (int i = 0; i < x; ++i) {
                to_new[i] = INF;
                for (int j = 0; j < (int)edge.size(); ++j)
                    to_new[i] = min(to_new[i], dist[(size_t)i * v + edge[j].first] + w[j]);
            }

            unordered_set<ll> seen;
            seen.reserve((size_t)(x + 1) * x);
            bool ok = true;
            for (int j = 1; j < x && ok; ++j) {
                for (int i = 0; i < j; ++i) {
                    ll d = min(dist[(size_t)i * v + j], to_new[i] + to_new[j]);
                    if (!seen.insert(d).second) { ok = false; break; }
                }
            }
            for (int i = 0; i < x && ok; ++i)
                if (!seen.insert(to_new[i]).second) ok = false;
            if (!ok) continue;

            // Floyd-Warshallで中継頂点 x を1つ追加する場合と同じ更新。
            for (int j = 1; j < x; ++j) for (int i = 0; i < j; ++i) {
                ll d = min(dist[(size_t)i * v + j], to_new[i] + to_new[j]);
                dist[(size_t)i * v + j] = dist[(size_t)j * v + i] = d;
            }
            for (int i = 0; i < x; ++i)
                dist[(size_t)i * v + x] = dist[(size_t)x * v + i] = to_new[i];
            dist[(size_t)x * v + x] = 0;
            for (int j = 0; j < (int)edge.size(); ++j) answer[edge[j].second] = w[j];
            fixed = true;
            break;
        }
        if (!fixed) return false;
    }
    return true;
}

void output(int n, const vector<int>& answer) {
    int k = 0;
    for (int r = 0; r + 1 < n; ++r) {
        for (int c = 0; c < n; ++c) cout << (c ? " " : "") << answer[k++];
        cout << '\n';
    }
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c + 1 < n; ++c) cout << (c ? " " : "") << answer[k++];
        cout << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    auto deadline = Clock::now() + chrono::duration_cast<Clock::duration>(chrono::duration<double>(TIME_LIMIT));
    vector<int> answer;
    while (Clock::now() < deadline) {
        if (construct(n, rng, deadline, answer)) {
            output(n, answer);
            return 0;
        }
    }
    cout << -1 << '\n';
}