結果

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

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
#include <functional>


using namespace std;
#define ll long long
#define MOD 998244353
#define ld long double
#define INF 2251799813685248
#define vall(A) A.begin(),A.end()
#define gridinput(vv,H,W) for (ll i = 0; i < H; i++){string T; cin >> T; for(ll j = 0; j < W; j++){vv[i][j] = {T[j]};}}
#define adjustedgridinput(vv,H,W) for (ll i = 1; i <= H; i++){string T; cin >> T; for(ll j = 1; j <= W; j++){vv[i][j] = {T[j-1]};}}
#define vin(A) for (ll i = 0, sz = A.size(); i < sz; i++){cin >> A[i];}
#define vout(A) for(ll i = 0, sz = A.size(); i < sz; i++){cout << A[i] << " \n"[i == sz-1];}
#define adjustedvin(A) for (ll i = 1, sz = A.size(); i < sz; i++){cin >> A[i];}
#define adjustedvout(A) for(ll i = 1, sz = A.size(); i < sz; i++){cout << A[i] << " \n"[i == sz-1];}
#define vout2d(A,H,W) for (ll i = 0; i < H; i++){for (ll j = 0; j < W; j++){cout << A[i][j] << " \n"[j==W-1];}}
#define encode(i,j) ((i)<<32)+j
#define decode(v,w) (w ? (v)%4294967296 : (v)>>32)
vector<ll> pow2ll{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296};
vector<ll> pow10ll{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000};
vector<ll> di{0,1,0,-1};
vector<ll> dj{1,0,-1,0};

/// @brief a^bをmで割った余りを返す。bに関して対数時間で計算できる。
/// @param a 
/// @param b 
/// @param m 
/// @return a^b%m
ll modpow(ll a, ll b, ll m){
    ll t = a%m;
    ll ans = 1;
    while (b > 0){
        if (b%2){
            ans = (ans*t)%m;
        }
        b /= 2;
        t = (t*t)%m;
    }
    return ans;
}

/// @brief a^nを返す。bに関して線形時間で計算できる。
/// @param a 
/// @param n
/// @param m 
/// @return a^n
ll powll(ll a, ll n){
    ll r = 1;
    for (ll i = 1; i <= n; i++){
        r *= a;
    }
    return r;
}


void dfs(vector<vector<bool>> &T, vector<bool> &temp, ll pos, ll d, ll target){
    if (d == target){
        T.push_back(temp);
        return;
    }
    for (ll i = pos; i <= target+d; i++){
        temp[i] = true;
        dfs(T,temp,i+1,d+1,target);
        temp[i] = false;
    }
}





int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    ll N;
    cin >> N;
    vector<ll> A(10,0);
    set<ll> d;
    for (ll i = 0; i < N; i++){
        ll t;
        cin >> t;
        d.insert(t);
        A[t]++;
    }

    if (N%2){
        ll ans = 0;
        
        vector<ll> X(N/2+1);
        vector<ll> Y(N/2+1);
        X.back() = *d.begin();
        A[*d.begin()]--;

        deque<ll> Q;
        for (ll i = 9; i >= 1; i--){
            for (ll j = 0; j < A[i]; j++){
                Q.push_back(i);
            }
        }

        for (ll i = N/2-1; i >= 0; i--){
            Y[i] = Q.front();
            Q.pop_front();
        }
        for (ll i = N/2-1; i >= 0; i--){
            X[i] = Q.back();
            Q.pop_back();
        }

        for (ll i = N/2; i >= 0; i--){
            ans += (X[i] - Y[i])*modpow(10,i,MOD);
            ans %= MOD;
        }
        ans += MOD;
        ans %= MOD;
        cout << ans << endl;
        return 0;
    }
    
    ll min_ans = __LONG_LONG_MAX__;
    vector<ll> digitlist;
    for (ll i = 1; i <= 9; i++){
        if (A[i]%2){
            digitlist.push_back(i);
            A[i]--;
        }
    }

    if (digitlist.empty()){min_ans = 0;}

    vector<vector<bool>> T;
    vector<bool> temp(digitlist.size(),0);
    dfs(T,temp,0,0,digitlist.size()/2);

    vector<ll> Xlist;
    vector<ll> Ylist;
    for (auto vec : T){
        Xlist.clear();
        Ylist.clear();
        for (ll i = 0; i < digitlist.size(); i++){
            if (vec[i]){
                Xlist.push_back(digitlist[i]);
            }
            else{
                Ylist.push_back(digitlist[i]);
            }
        }
        do{
            do{
                ll tempX = 0;
                ll tempY = 0;
                ll t = 1;
                for (auto v : Xlist){
                    tempX += t*v;
                    t *= 10;
                }
                t = 1;
                for (auto v : Ylist){
                    tempY += t*v;
                    t *= 10;
                }
                min_ans = min(min_ans, abs(tempX-tempY));
            }while(next_permutation(vall(Xlist)));
        }while(next_permutation(vall(Ylist)));
    }

    temp = vector<bool>(digitlist.size()+2);
    T.clear();
    dfs(T,temp,0,0,digitlist.size()/2 + 1);

    for (ll i = 1; i <= 9; i++){
        if (A[i] < 2){continue;}
        auto newdigitlist = digitlist;
        newdigitlist.push_back(i);
        newdigitlist.push_back(i);
        sort(vall(newdigitlist));

        for (auto vec : T){
            Xlist.clear();
            Ylist.clear();
            for (ll l = 0; l < newdigitlist.size(); l++){
                if (vec[l]){
                    Xlist.push_back(newdigitlist[l]);
                }
                else{
                    Ylist.push_back(newdigitlist[l]);
                }
            }
            do{
                do{
                    ll tempX = 0;
                    ll tempY = 0;
                    ll t = 1;
                    for (auto v : Xlist){
                        tempX += t*v;
                        t *= 10;
                    }
                    t = 1;
                    for (auto v : Ylist){
                        tempY += t*v;
                        t *= 10;
                    }
                    min_ans = min(min_ans, abs(tempX-tempY));
                }while(next_permutation(vall(Xlist)));
            }while(next_permutation(vall(Ylist)));
        }
    }

    cout << min_ans%998244353 << endl;
    
}
0