結果

問題 No.3363 Two Closest Numbers
コンテスト
ユーザー Rubikun
提出日時 2025-11-17 23:51:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 3,245 bytes
コンパイル時間 2,011 ms
コンパイル使用メモリ 201,084 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-11-17 23:51:31
合計ジャッジ時間 7,764 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 RE * 2
other AC * 26 RE * 33
権限があれば一括ダウンロードができます

ソースコード

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{
        assert(false);
        string S;
        bool f=false;
        for(int i=0;i<10;i++){
            int can=0;
            if(CN[i]&1) can=min(1,CN[i]);
            else if(!f){
                can=min(2,CN[i]);
                f=true;
            }else{
                can=0;
            }
            for(int j=0;j<can;j++) S+='0'+i;
        }
        ll ans=INF;
        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)));
        cout<<ans<<endl;
    }
    
}
0