oj.uz

Submission #1102406

# Submission time Handle Problem Language Result Execution time Memory
1102406 2024-10-18T04:23:13 Z daoquanglinh2007 Weird Numeral System (CCO21_day1problem2) C++17
25 / 25
 478 ms 12876 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12624 KB OK
2 Correct 4 ms 12876 KB OK
3 Correct 4 ms 12696 KB OK
4 Correct 4 ms 12624 KB OK
5 Correct 4 ms 12624 KB OK
6 Correct 14 ms 12624 KB OK
7 Correct 4 ms 12624 KB OK
8 Correct 4 ms 12624 KB OK

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12624 KB OK
2 Correct 4 ms 12876 KB OK
3 Correct 4 ms 12696 KB OK
4 Correct 4 ms 12624 KB OK
5 Correct 4 ms 12624 KB OK
6 Correct 14 ms 12624 KB OK
7 Correct 4 ms 12624 KB OK
8 Correct 4 ms 12624 KB OK
9 Correct 10 ms 12820 KB OK
10 Correct 8 ms 12792 KB OK
11 Correct 7 ms 12624 KB OK
12 Correct 8 ms 12624 KB OK
13 Correct 24 ms 12624 KB OK
14 Correct 15 ms 12624 KB OK
15 Correct 14 ms 12624 KB OK
16 Correct 5 ms 12624 KB OK
17 Correct 12 ms 12624 KB OK
18 Correct 249 ms 12624 KB OK
19 Correct 478 ms 12624 KB OK
20 Correct 5 ms 12624 KB OK
21 Correct 18 ms 12624 KB OK
22 Correct 117 ms 12808 KB OK
23 Correct 36 ms 12624 KB OK
24 Correct 103 ms 12624 KB OK
25 Correct 246 ms 12624 KB OK
26 Correct 258 ms 12624 KB OK
27 Correct 4 ms 12624 KB OK
28 Correct 3 ms 12624 KB OK