oj.uz

Submission #1102407

# Submission time Handle Problem Language Result Execution time Memory
1102407 2024-10-18T04:23:23 Z vjudge1 Weird Numeral System (CCO21_day1problem2) C++17
25 / 25
 504 ms 12824 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 5 ms 12624 KB OK
2 Correct 4 ms 12624 KB OK
3 Correct 5 ms 12624 KB OK
4 Correct 5 ms 12624 KB OK
5 Correct 5 ms 12624 KB OK
6 Correct 15 ms 12624 KB OK
7 Correct 4 ms 12624 KB OK
8 Correct 6 ms 12624 KB OK

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12624 KB OK
2 Correct 4 ms 12624 KB OK
3 Correct 5 ms 12624 KB OK
4 Correct 5 ms 12624 KB OK
5 Correct 5 ms 12624 KB OK
6 Correct 15 ms 12624 KB OK
7 Correct 4 ms 12624 KB OK
8 Correct 6 ms 12624 KB OK
9 Correct 10 ms 12624 KB OK
10 Correct 7 ms 12624 KB OK
11 Correct 8 ms 12624 KB OK
12 Correct 9 ms 12624 KB OK
13 Correct 28 ms 12636 KB OK
14 Correct 15 ms 12624 KB OK
15 Correct 13 ms 12624 KB OK
16 Correct 5 ms 12624 KB OK
17 Correct 13 ms 12824 KB OK
18 Correct 229 ms 12624 KB OK
19 Correct 504 ms 12624 KB OK
20 Correct 4 ms 12624 KB OK
21 Correct 18 ms 12816 KB OK
22 Correct 115 ms 12624 KB OK
23 Correct 38 ms 12804 KB OK
24 Correct 105 ms 12624 KB OK
25 Correct 232 ms 12820 KB OK
26 Correct 275 ms 12624 KB OK
27 Correct 4 ms 12624 KB OK
28 Correct 3 ms 12772 KB OK