# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
852216 | 2023-09-21T12:37:58 Z | NaimSS | Weird Numeral System (CCO21_day1problem2) | C++14 | 795 ms | 5248 KB |
#include <bits/stdc++.h> #define rep(i,a,b) for(int i=(a);i<(b);++i) #define all(v) begin(v),end(v) using namespace std; typedef long long ll; int k,d; unordered_map<ll,int> dp, go; set<int> A; int a[2505]; int solve(ll num){ if(dp.count(num))return dp[num]; dp[num] = 0; rep(i,0,d){ ll nv = num - a[i]; if(nv%k)continue; if(solve(nv/k)){ dp[num] = 1; go[num] = a[i]; return 1; } } return dp[num] = 0; } int32_t main(){ ios_base::sync_with_stdio(0);cin.tie(0); int q,m; cin >> k >> q >> d >> m; rep(i,0,d)cin >> a[i],dp[a[i]] = 1, go[a[i]] = a[i]; while(q--){ ll N; cin >> N; if(solve(N)){ vector<int> vals; while(N != 0 || vals.size()==0){ int put = go[N]; N = (N-put)/k; vals.push_back(put); } reverse(all(vals)); rep(i,0,vals.size())cout<<vals[i]<<" \n"[i == vals.size()-1]; }else{ cout << "IMPOSSIBLE\n"; } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | OK |
2 | Correct | 0 ms | 348 KB | OK |
3 | Correct | 0 ms | 348 KB | OK |
4 | Correct | 0 ms | 348 KB | OK |
5 | Correct | 0 ms | 348 KB | OK |
6 | Correct | 1 ms | 348 KB | OK |
7 | Correct | 0 ms | 348 KB | OK |
8 | Correct | 0 ms | 348 KB | OK |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | OK |
2 | Correct | 0 ms | 348 KB | OK |
3 | Correct | 0 ms | 348 KB | OK |
4 | Correct | 0 ms | 348 KB | OK |
5 | Correct | 0 ms | 348 KB | OK |
6 | Correct | 1 ms | 348 KB | OK |
7 | Correct | 0 ms | 348 KB | OK |
8 | Correct | 0 ms | 348 KB | OK |
9 | Correct | 1 ms | 348 KB | OK |
10 | Correct | 0 ms | 348 KB | OK |
11 | Correct | 0 ms | 348 KB | OK |
12 | Correct | 0 ms | 348 KB | OK |
13 | Correct | 1 ms | 344 KB | OK |
14 | Correct | 1 ms | 348 KB | OK |
15 | Correct | 0 ms | 348 KB | OK |
16 | Correct | 0 ms | 348 KB | OK |
17 | Correct | 0 ms | 348 KB | OK |
18 | Correct | 1 ms | 600 KB | OK |
19 | Correct | 0 ms | 348 KB | OK |
20 | Correct | 0 ms | 348 KB | OK |
21 | Correct | 22 ms | 1112 KB | OK |
22 | Correct | 166 ms | 1420 KB | OK |
23 | Correct | 795 ms | 5248 KB | OK |
24 | Correct | 323 ms | 1896 KB | OK |
25 | Correct | 1 ms | 348 KB | OK |
26 | Correct | 1 ms | 348 KB | OK |
27 | Correct | 0 ms | 348 KB | OK |
28 | Correct | 1 ms | 348 KB | OK |