結果

問題 No.3363 Two Closest Numbers
コンテスト
ユーザー 달콤한마시로
提出日時 2025-12-21 10:47:25
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 18 ms / 2,000 ms
コード長 2,861 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 375 ms
コンパイル使用メモリ 38,412 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-12-21 10:47:30
合計ジャッジ時間 4,804 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘ll readint()’:
main.cpp:100:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  100 |     scanf("%lld", &n);
      |     ~~~~~^~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <cassert>
#include <cstdio>
#include <array>

using std::scanf;
using std::printf;

using ll = long long;

const int MOD = 998244353;

int solve_odd(std::array<int, 10> cnt) {
    int n = 0;
    for (int t : cnt) {
        n += t;
    }
    assert(n % 2 == 1);
    int nbig = n / 2 + 1;
    int wbig = 0;
    for (int i = 0; i < 10; ++i) {
        while (nbig > 0 && cnt[i] > 0) {
            wbig = (10LL * wbig + i) % MOD;
            --nbig;
            --cnt[i];
        }
    }
    int wsmall = 0;
    for (int i = 10; i-- > 0; ) {
        while (cnt[i] > 0) {
            wsmall = (10LL * wsmall + i) % MOD;
            --cnt[i];
        }
    }
    int ans = (0LL + wbig + (MOD - wsmall)) % MOD;
    return ans;
}

int solve_even(std::array<int, 10> cnt) {
    {
        bool any_odd = false;
        for (int v = 0; v < 10; ++v) {
            if (cnt[v] % 2 != 0) {
                any_odd = true;
                break;
            }
        }
        if (!any_odd) return 0;
    }
    for (int v = 0; v < 10; ++v) {
        if (cnt[v] > 3) {
            cnt[v] = cnt[v] % 2 + 2;
        }
    }
    ll ans = 1LL << 60;
    auto cnt_orig = cnt;
    for (int ik = 0; ik < 10; ++ik) {
        cnt = cnt_orig;
        for (int i = 0; i < 10; ++i) {
            if (i == ik) continue;
            cnt[i] %= 2;
        }
        auto cnt_red = cnt;
        for (int ibig = 1; ibig < 10; ++ibig) {
            if (cnt_red[ibig] == 0) continue;
            for (int ismall = 1; ismall < ibig; ++ismall) {
                if (cnt_red[ismall] == 0) continue;
                cnt = cnt_red;
                cnt[ibig] -= 1;
                cnt[ismall] -= 1;
                int ncurr = 0;
                for (int t : cnt) ncurr += t;
                int nbig = ncurr / 2;
                ll wbig = ibig;
                for (int i = 0; i < 10; ++i) {
                    while (nbig > 0 && cnt[i] > 0) {
                        wbig = (10LL * wbig + i);
                        --nbig;
                        --cnt[i];
                    }
                }
                ll wsmall = ismall;
                for (int i = 10; i-- > 0; ) {
                    while (cnt[i] > 0) {
                        wsmall = (10LL * wsmall + i);
                        --cnt[i];
                    }
                }
                assert(wbig > wsmall);
                if (wbig - wsmall < ans) {
                    ans = wbig - wsmall;
                }
            }
        }
    }
    return static_cast<int>(ans % MOD);
}

ll readint() {
    long long n;
    scanf("%lld", &n);
    return n;
}

int main() {
    int n = readint();
    std::array<int, 10> cnt = {};
    for (int i = 0; i < n; ++i) {
        int v = readint();
        cnt[v] += 1;
    }
    int ans = n % 2 ? solve_odd(cnt) : solve_even(cnt);
    printf("%d\n", ans);

    return 0;
}
0