Submission #1102406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102406		daoquanglinh2007	Weird Numeral System (CCO21_day1problem2)	C++17	25 / 25	478 ms	12876 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define i128 __int128
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 5005;

i128 LIM = 1;
int K, Q, D, M, sz, a[NM+5];
vector <i128> pw;
i128 n;
pair <int, pii> dp[105][NM+5][2];
vector <int> ans;

void solve(){
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= D; i++){
        if (a[i] > n/pw[sz-1]) continue;
        if (n/pw[sz-1]-a[i] > 2*M) continue;
        dp[sz-1][n/pw[sz-1]-a[i]][i != D] = mp(i, mp(-1, -1));
    }
    for (int i = sz-1; i > 0; i--){
        for (int j = 0; j <= 2*M; j++)
            for (int b = 0; b < 2; b++){
                if (dp[i][j][b].fi == -1) continue;
                for (int t = 1; t <= D; t++){
                    ll tmp = 1LL*j*K+(n/pw[i-1])%K-a[t];
                    if (tmp < 0 || tmp > 2*M) continue;
                    if (b == 1 && t == D) continue;
                    dp[i-1][tmp][b|(t < D)] = mp(t, mp(j, b));
                }
            }
    }
    if (dp[0][0][1].fi == -1){
        cout << "IMPOSSIBLE\n";
        return;
    }
    ans.clear();
    int j = 0;
    for (int i = 0; i < sz; i++){
        ans.push_back(a[dp[i][j][1].fi]-M);
        if (dp[i][j][1].se.se == 0) break;
        j = dp[i][j][1].se.fi;
    }
    while ((int)ans.size() > 1 && ans.back() == 0) ans.pop_back();
    reverse(ans.begin(), ans.end());
    for (int i = 0; i < (int)ans.size(); i++){
        cout << ans[i];
        if (i+1 < (int)ans.size()) cout << ' ';
    }
    cout << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for (int i = 1; i <= 24; i++) LIM *= 10;
    
    cin >> K >> Q >> D >> M;
    for (int i = 1; i <= D; i++){
        cin >> a[i];
        a[i] += M;
    }
    a[++D] = M;
    pw.push_back(1);
    while (true){
        i128 x = pw.back()*K;
        pw.push_back(x);
        if (x > LIM) break;
    }
    sz = (int)pw.size();
    while (Q--){
        ll x; cin >> x;
        n = x;
        for (i128 x : pw) n += M*x;
        solve();
    }
    return 0;    
}

• Subtask 1: 8 / 8
• Subtask 2: 17 / 17