結果

問題 No.3363 Two Closest Numbers
コンテスト
ユーザー AK_Mi
提出日時 2025-11-18 15:51:49
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 98 ms / 2,000 ms
コード長 2,220 bytes
コンパイル時間 5,069 ms
コンパイル使用メモリ 335,764 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-11-18 15:51:58
合計ジャッジ時間 8,808 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
int main(){
    ll n;
    cin >> n;

    vector<ll> num(10,0);
    ll c;

    for(ll i = 0; i < n; i++){
        cin >> c;
        num[c]++;
    }

    if(n % 2 == 1){
        deque<ll> big;
        deque<ll> small;
        ll s = (n-1)/2;

        for(ll i = 0; i < 10; i++){
            for(ll t = 0; t < num[i]; t++){
                big.push_back(i);
            }
        }

        for(ll i = 0; i < s; i++){
            small.push_back(big.back());
            big.pop_back();
        }

        ll ans = 0;
        ll kake = 1;
        for(ll i = 0; i < s; i++){
            ans += 9982443530;
            ans += (big.back() - small.back()) * kake;
            ans %= 998244353;
            kake *= 10;
            kake %= 998244353;
            big.pop_back();
            small.pop_back();
        }
        ans += big.back() * kake;
        ans %= 998244353;

        cout << ans << '\n';
        
    }else{
        vector<ll> nokori;
        vector<ll> ari(10,0);
        for(ll i = 0; i < 10; i++){
            if(num[i] >= 2)ari[i] = 1;
            num[i] %= 2;
            if(num[i] == 1)nokori.push_back(i);
        }
        ll s = nokori.size()/2;

        ll minn = -1;

        for(ll i = 0; i < 10; i++){
            if(i > 0 && ari[i] == 0)continue;
            vector<ll> nok = nokori;
            if(ari[i] == 1){
                nok.push_back(i);
                nok.push_back(i);
                sort(nok.begin(),nok.end());
                s++;
            }

            do{
                ll a = 0;
                ll b = 0;
                for(ll t = 0; t < s; t++){
                    a *= 10;
                    a += nok[t];
                }
                for(ll t = 0; t < s; t++){
                    b *= 10;
                    b += nok[t+s];
                }
                if(abs(a-b) < minn || minn == -1){
                    minn = abs(a-b);
                }

            }while(next_permutation(nok.begin(),nok.end()));

            if(ari[i] == 1)s--;
        }
        


        cout << minn << '\n';
    }



    return 0;
}
0