#1173568 (C++17) No.3743 World Mapper

• 問題: No.3743 World Mapper
• ユーザー: 👑 kencho
• 提出日時: 2026-07-25 06:00:38
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 15 ms / 2,000 ms
• コード長: 4,533 bytes
• コンパイル時間: 1,434 ms
• コンパイル使用メモリ: 224,052 KB
• 実行使用メモリ: 6,528 KB
• 最終ジャッジ日時: 2026-09-19 12:37:41
• 合計ジャッジ時間: 10,123 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

サブタスク	配点	結果
部分点1	10 %	AC * 4
部分点2	10 %	AC * 9
部分点3	10 %	AC * 14
部分点4	10 %	AC * 19
部分点5	10 %	AC * 24
部分点6	10 %	AC * 29
部分点7	10 %	AC * 34
部分点8	10 %	AC * 39
部分点9	10 %	AC * 44
満点	10 %	AC * 49
合計	5 * 100% = 500 点

ソースコード

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

using int64 = long long;

bool is_prime(int x) {
    if (x < 2) return false;
    if (x % 2 == 0) return x == 2;

    for (int d = 3; 1LL * d * d <= x; d += 2) {
        if (x % d == 0) return false;
    }
    return true;
}

vector<int> distinct_prime_factors(int x) {
    vector<int> factors;

    for (int d = 2; 1LL * d * d <= x; ++d) {
        if (x % d != 0) continue;

        factors.push_back(d);
        while (x % d == 0) x /= d;
    }

    if (x > 1) factors.push_back(x);
    return factors;
}

int64 mod_pow(int64 a, int64 e, int64 mod) {
    int64 result = 1;

    while (e > 0) {
        if (e & 1) result = result * a % mod;
        a = a * a % mod;
        e >>= 1;
    }

    return result;
}

// p は素数
int primitive_root(int p) {
    vector<int> factors = distinct_prime_factors(p - 1);

    for (int g = 2; g < p; ++g) {
        bool ok = true;

        for (int q : factors) {
            if (mod_pow(g, (p - 1) / q, p) == 1) {
                ok = false;
                break;
            }
        }

        if (ok) return g;
    }

    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    const int M = N * N;

    // p - 1 >= M となる最小の素数
    int p = M + 1;
    while (!is_prime(p)) ++p;

    const int g = primitive_root(p);
    const int Q = p - 1;
    const int64 MOD = 1LL * p * (p - 1);

    /*
     * Ruzsa の巡回 Sidon 集合
     *
     * a_i = p*i + (p-1)*g^i mod p(p-1)
     * 0 <= i <= p-2
     */
    vector<int64> cyclic_marks;
    cyclic_marks.reserve(Q);

    int64 power = 1;

    for (int i = 0; i < Q; ++i) {
        int64 value =
            (1LL * p * i + 1LL * (p - 1) * power) % MOD;

        cyclic_marks.push_back(value);
        power = power * g % p;
    }

    sort(cyclic_marks.begin(), cyclic_marks.end());

    // 円周を 2 周分展開する
    vector<int64> extended(2 * Q);

    for (int i = 0; i < Q; ++i) {
        extended[i] = cyclic_marks[i];
        extended[i + Q] = cyclic_marks[i] + MOD;
    }

    // 蛇行順での位置
    auto position = [N](int row, int column) -> int {
        if (row % 2 == 0) {
            return row * N + column;
        } else {
            return row * N + (N - 1 - column);
        }
    };

    // 蛇行順で表現した全グリッド辺
    vector<pair<int, int>> edges;
    edges.reserve(2 * N * (N - 1));

    // 縦辺
    for (int row = 0; row + 1 < N; ++row) {
        for (int column = 0; column < N; ++column) {
            edges.emplace_back(
                position(row, column),
                position(row + 1, column)
            );
        }
    }

    // 横辺
    for (int row = 0; row < N; ++row) {
        for (int column = 0; column + 1 < N; ++column) {
            edges.emplace_back(
                position(row, column),
                position(row, column + 1)
            );
        }
    }

    int best_start = -1;
    int64 best_maximum_weight = (1LL << 60);

    // 円を切る位置を全探索
    for (int start = 0; start < Q; ++start) {
        int64 maximum_weight = 0;

        for (auto [u, v] : edges) {
            int64 weight =
                llabs(extended[start + u] - extended[start + v]);
            maximum_weight = max(maximum_weight, weight);
        }

        if (maximum_weight < best_maximum_weight) {
            best_maximum_weight = maximum_weight;
            best_start = start;
        }
    }

    if (best_start == -1 || best_maximum_weight > 300000) {
        cout << -1 << '\n';
        return 0;
    }

    vector<int64> mark(M);

    for (int i = 0; i < M; ++i) {
        mark[i] =
            extended[best_start + i] - extended[best_start];
    }

    auto weight = [&](int r1, int c1, int r2, int c2) -> int64 {
        int x = position(r1, c1);
        int y = position(r2, c2);
        return llabs(mark[x] - mark[y]);
    };

    // 縦辺
    for (int row = 0; row + 1 < N; ++row) {
        for (int column = 0; column < N; ++column) {
            if (column > 0) cout << ' ';
            cout << weight(
                row, column,
                row + 1, column
            );
        }
        cout << '\n';
    }

    // 横辺
    for (int row = 0; row < N; ++row) {
        for (int column = 0; column + 1 < N; ++column) {
            if (column > 0) cout << ' ';
            cout << weight(
                row, column,
                row, column + 1
            );
        }
        cout << '\n';
    }
}