結果

問題 No.3363 Two Closest Numbers
コンテスト
ユーザー Rubikun
提出日時 2025-11-18 00:02:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,698 bytes
コンパイル時間 1,995 ms
コンパイル使用メモリ 205,304 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-11-18 00:02:26
合計ジャッジ時間 4,587 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 53 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=15<<26;

string add(string a,string b){
    if(si(a)<si(b)) swap(a,b);
    
    for(int i=0;i<si(b);i++){
        a[si(a)-1-i]+=int(b[si(b)-1-i]-'0');
        if(a[si(a)-1-i]>'9'&&si(a)-1-i){
            a[si(a)-1-i]-=10;
            a[si(a)-1-i-1]++;
        }
    }
    for(int i=si(a)-1;i>=1;i--){
        if(a[i]>'9'){
            a[i]-=10;
            a[i-1]++;
        }
    }
    string res;
    
    if(a[0]>'9'){
        a[0]-=10;
        res+='1';
    }
    res+=a;
    
    for(int i=si(res)-1;i>=0;i--){
        if(res[i]>'9'){
            res[i]-=10;
            res[i-1]++;
        }
    }
    
    return res;
}

string sub(string a,string b){
    if(si(a)<si(b)) return "";
    if(si(a)==si(b)&&a<=b) return "";
    
    for(int i=0;i<si(b);i++){
        if(a[si(a)-1-i]<b[si(b)-1-i]){
            a[si(a)-1-i-1]--;
            a[si(a)-1-i]+=10;
        }
        a[si(a)-1-i]-=int(b[si(b)-1-i]-'0');
    }
    
    for(int i=si(a)-1;i>=0;i--){
        if(a[i]<'0'){
            a[i-1]--;
            a[i]+=10;
        }
    }
    int i=0;
    while(a[i]=='0') i++;
    
    return a.substr(i);
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;cin>>N;
    vi CN(10);
    for(int i=0;i<N;i++){
        int x;cin>>x;
        CN[x]++;
    }
    if(N&1){
        string S;
        for(int i=0;i<10;i++){
            for(int j=0;j<CN[i];j++) S.pb('0'+i);
        }
        string A=S.substr(0,(N+1)/2),B=S.substr((N+1)/2);
        reverse(all(B));
        auto res=sub(A,B);
        ll ans=0;
        for(char c:res){
            ans*=10;
            ans+=(c-'0');
            ans%=mod;
        }
        cout<<ans<<"\n";
    }else{
        ll ans=INF;
        {
            string S;
            for(int i=0;i<10;i++){
                if(CN[i]&1) S.pb('0'+i);
            }
            if(si(S)==0){
                cout<<0<<endl;
                return 0;
            }
            do{
                string A=S.substr(0,si(S)/2),B=S.substr(si(S)/2);
                chmin(ans,abs(stoll(A)-stoll(B)));
            }while(next_permutation(all(S)));
        }
        {
            string S;
            for(int i=0;i<10;i++){
                int can=0;
                if(CN[i]&1) can=min(1,CN[i]);
                else can=min(2,CN[i]);
                for(int j=0;j<can;j++) S+='0'+i;
            }
            
            if(si(S)){
                for(int a=0;a<si(S);a++){
                    string T=S;T.erase(T.begin()+a);
                    string A=S[a]+T.substr(0,si(T)/2);
                    string B=T.substr(si(T)/2);
                    reverse(all(B));
                    ll res=abs(stoll(A)-stoll(B));
                    chmin(ans,res);
                }
            }
        }
        cout<<ans<<"\n";
    }
    
}
0