結果

問題 No.3363 Two Closest Numbers
コンテスト
ユーザー jupiter_68
提出日時 2025-10-30 14:32:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 4,850 bytes
コンパイル時間 2,141 ms
コンパイル使用メモリ 207,480 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-11-17 20:41:32
合計ジャッジ時間 6,550 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47 WA * 1 RE * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using vl = vector<ll>;
template <class T> using vec = vector<T>;
template <class T> using vv = vec<vec<T>>;
template <class T> using vvv = vv<vec<T>>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
#define all(a) (a).begin(),(a).end()
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define reps(i, l, r) for(ll i = (l); i < (r); ++i)
#define rrep(i, l, r) for(ll i = (r)-1; i >= (l); --i)
#define sz(x) (ll) (x).size()
template <typename T>
bool chmax(T &a, const T& b) { return a < b ? a = b, true : false; }
template <typename T>
bool chmin(T &a, const T& b) { return a > b ? a = b, true : false; }

struct Edge {
    ll from, to, cost;
    Edge (ll from, ll to, ll cost = 1ll) : from(from), to(to), cost(cost) {}
};
struct Graph {
    vector<vector<Edge>> G;
    Graph() = default;
    explicit Graph(ll N) : G(N) {}
    size_t size() const {
        return G.size();
    }
    void add(ll from, ll to, ll cost = 1ll, bool direct = 0) {
        G[from].emplace_back(from, to, cost);
        if (!direct) G[to].emplace_back(to, from, cost);
    }
    vector<Edge> &operator[](const int &k) {
        return G[k];
    }
};
using Edges = vector<Edge>;

const ll mod = 998244353;
struct mint {
	ll x;
	mint(ll y = 0) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
	mint &operator+=(const mint &p) {
		if ((x += p.x) >= mod) x -= mod;
		return *this;
	}
	mint &operator-=(const mint &p) {
		if ((x += mod - p.x) >= mod) x -= mod;
		return *this;
	}
	mint &operator*=(const mint &p) {
		x = (ll)(1ll * x * p.x % mod);
		return *this;
	}
	mint &operator/=(const mint &p) {
		*this *= p.inv();
		return *this;
	}
	mint operator-() const { return mint(-x); }
	mint operator+(const mint &p) const { return mint(*this) += p; }
	mint operator-(const mint &p) const { return mint(*this) -= p; }
	mint operator*(const mint &p) const { return mint(*this) *= p; }
	mint operator/(const mint &p) const { return mint(*this) /= p; }
	bool operator==(const mint &p) const { return x == p.x; }
	bool operator!=(const mint &p) const { return x != p.x; }
	friend ostream &operator<<(ostream &os, const mint &p) { return os << p.x; }
	friend istream &operator>>(istream &is, mint &a) {
		ll t; is >> t; a = mint(t); return (is);
	}
	mint inv() const { return pow(mod - 2); }
	mint pow(ll n) const {
		mint ret(1), mul(x);
		while (n > 0) {
			if (n & 1) ret *= mul;
			mul *= mul;
			n >>= 1;
		}
		return ret;
	}
};

void solve(){
    ll N; cin >> N;
    vl a(10, 0);
    rep(i, N){
        ll x; cin >> x;
        a[x]++;
    }
    vec<mint> Tn(N+1, 1); rep(i, N) Tn[i+1] = Tn[i] * 10;
    if(N % 2){
        ll M = N/2;
        mint ans = 0;
        ll ct = M+1;
        while(ct){
            ct--;
            reps(t, 1, 10){
                if(a[t]){
                    a[t]--;
                    ans += Tn[ct] * t;
                    break;
                }
            }
        }
        ct = M;
        while(ct){
            ct--;
            rrep(t, 1, 10){
                if(a[t]){
                    a[t]--;
                    ans -= Tn[ct] * t;
                    break;
                }
            }
        }
        cout << ans << endl;
        return;
    }
    vl odd = a;
    rep(i, 10) odd[i] %= 2;
    ll D = reduce(all(odd)) / 2;
    if(D == 0){
        cout << 0 << endl;
        return;
    }
    vl V;
    rep(i, 10) if(odd[i]) V.push_back(i);
    ll ans = 4e18;
    {
        vl v = V;
        do{
            ll X = 0, Y = 0;
            ll tn = 1;
            rep(i, D){
                X += tn * v[i];
                Y += tn * v[i+D];
                tn *= 10;
            }
            chmin(ans, abs(X - Y));
        }while(next_permutation(all(v)));
    }
    reps(t, 1, 10){
        if(a[t] < 2) continue;
        odd[t] += 2;
        reps(k, 1, 9){
            if(odd[k] && odd[k+1]){
                odd[k]--; odd[k+1]--;
                vl v;
                reps(i, 1, 10){
                    rep(l, odd[i]){
                        v.push_back(i);
                    }
                }
                do{
                    ll X = 0, Y = 0;
                    ll tn = 1;
                    rep(i, D){
                        X += tn * v[i];
                        Y += tn * v[i+D];
                        tn *= 10;
                    }
                    X += tn;
                    chmin(ans, abs(X - Y));
                }while(next_permutation(all(v)));
                odd[k]++; odd[k+1]--;
            }
        }
        odd[t] -= 2;
    }
    cout << ans << endl;
}

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}
0