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

• 問題: No.3743 World Mapper
• ユーザー: 👑 kencho
• 提出日時: 2026-09-03 05:21:33
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 4,681 bytes
• コンパイル時間: 2,411 ms
• コンパイル使用メモリ: 346,432 KB
• 実行使用メモリ: 7,040 KB
• 最終ジャッジ日時: 2026-09-19 13:10:57
• 合計ジャッジ時間: 87,812 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

サブタスク	配点	結果
部分点1	10 %	AC * 4
部分点2	10 %	AC * 8 WA * 1
部分点3	10 %	AC * 8 WA * 6
部分点4	10 %	AC * 8 WA * 11
部分点5	10 %	AC * 8 WA * 16
部分点6	10 %	AC * 8 WA * 21
部分点7	10 %	AC * 8 WA * 26
部分点8	10 %	AC * 8 WA * 31
部分点9	10 %	AC * 8 WA * 36
満点	10 %	AC * 8 WA * 39 TLE * 2
合計	5 * 10% = 50 点

ソースコード

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

using Clock = chrono::steady_clock;
constexpr int MAX_W = 300000;
constexpr double TIME_LIMIT = 1.9;

int edge_id(int n, int a, int b) {
    if (a > b) swap(a, b);
    if (b - a == n) return (a / n) * n + a % n;
    return n * (n - 1) + (a / n) * (n - 1) + a % n;
}

vector<int> snake(int n) {
    vector<int> p;
    for (int r = 0; r < n; ++r) {
        if (r % 2 == 0) for (int c = 0; c < n; ++c) p.push_back(r * n + c);
        else for (int c = n - 1; c >= 0; --c) p.push_back(r * n + c);
    }
    return p;
}

// 重複数を数え、同じ区間和を持つ [i,j), [k,l) も一組返す。
int analyze(const vector<int>& w, array<int, 4>& dup,
            vector<int>& freq, vector<int>& owner, vector<int>& touched) {
    int m = w.size() + 1;
    vector<int> sum(m);
    for (int i = 0; i + 1 < m; ++i) sum[i + 1] = sum[i] + w[i];
    int score = 0;
    touched.clear();
    for (int j = 1; j < m; ++j) for (int i = 0; i < j; ++i) {
        int d = sum[j] - sum[i];
        if (freq[d]) {
            if (score == 0) {
            int code = owner[d];
            dup = {code / m, code % m, i, j};
            }
            ++score;
        } else {
            owner[d] = i * m + j;
            touched.push_back(d);
        }
        ++freq[d];
    }
    for (int d : touched) freq[d] = 0;
    return score;
}

void random_start(vector<int>& w, mt19937& rng) {
    int m = w.size() + 1;
    vector<int> marks(m);
    marks[0] = 0;
    do {
        for (int i = 1; i < m; ++i) marks[i] = 1 + rng() % (MAX_W - 1);
        sort(marks.begin(), marks.end());
    } while (adjacent_find(marks.begin(), marks.end()) != marks.end());
    for (int i = 0; i + 1 < m; ++i) w[i] = marks[i + 1] - marks[i];
}

void output(int n, const vector<int>& w) {
    int total = accumulate(w.begin(), w.end(), 0);
    vector<int> ans(2 * n * (n - 1), total + 1);
    auto p = snake(n);
    for (int i = 0; i + 1 < (int)p.size(); ++i)
        ans[edge_id(n, p[i], p[i + 1])] = w[i];
    int k = 0;
    for (int r = 0; r + 1 < n; ++r) {
        for (int c = 0; c < n; ++c) cout << (c ? " " : "") << ans[k++];
        cout << '\n';
    }
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c + 1 < n; ++c) cout << (c ? " " : "") << ans[k++];
        cout << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    int m = n * n;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    vector<int> w(m - 1), freq(MAX_W), owner(MAX_W), touched;
    touched.reserve((size_t)m * (m - 1) / 2);
    random_start(w, rng);
    int total = accumulate(w.begin(), w.end(), 0), steps = 0, stagnation = 0;
    auto deadline = Clock::now() + chrono::duration_cast<Clock::duration>(chrono::duration<double>(TIME_LIMIT));
    array<int, 4> d;
    int score = analyze(w, d, freq, owner, touched);
    while (Clock::now() < deadline) {
        if (score == 0) { output(n, w); return 0; }

        // 一方の区間だけに含まれる辺を変えれば、重複した二距離の片方だけが1変わる。
        if (rng() & 1) { swap(d[0], d[2]); swap(d[1], d[3]); }
        vector<int> candidate;
        for (int e = d[0]; e < d[1]; ++e)
            if (!(d[2] <= e && e < d[3])) candidate.push_back(e);
        if (candidate.empty()) {
            swap(d[0], d[2]); swap(d[1], d[3]);
            for (int e = d[0]; e < d[1]; ++e)
                if (!(d[2] <= e && e < d[3])) candidate.push_back(e);
        }
        int e = candidate[rng() % candidate.size()];
        int delta = (rng() & 1) ? 1 : -1;
        if ((delta < 0 && w[e] == 1) || (delta > 0 && total == MAX_W - 1)) delta = -delta;
        if ((delta < 0 && w[e] == 1) || (delta > 0 && total == MAX_W - 1)) {
            random_start(w, rng);
            total = accumulate(w.begin(), w.end(), 0);
            score = analyze(w, d, freq, owner, touched);
            stagnation = 0;
            continue;
        }
        w[e] += delta; total += delta;
        array<int, 4> next_dup;
        int next_score = analyze(w, next_dup, freq, owner, touched);
        if (next_score < score || (next_score == score && rng() % 4 == 0)) {
            stagnation = next_score < score ? 0 : stagnation + 1;
            score = next_score;
            d = next_dup;
        } else {
            w[e] -= delta; total -= delta;
            ++stagnation;
        }
        ++steps;
        if (stagnation >= 5000) {
            random_start(w, rng);
            total = accumulate(w.begin(), w.end(), 0);
            score = analyze(w, d, freq, owner, touched);
            stagnation = 0;
        }
    }
    cout << -1 << '\n';
}