This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(v) begin(v),end(v)
#define endl '\n'
#define sz(v) ((int)v.size())
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<int> vi;
void dbg_out(){ cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){
cerr << ' ' << H;
dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "): ", dbg_out(__VA_ARGS__), cerr << endl;
#else
#define dbg(...) 42
#endif
mt19937 rng(422);
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)){
vi vals;
while(N != 0 || sz(vals)==0){
int put = go[N];
N = (N-put)/k;
vals.pb(put);
}
reverse(all(vals));
rep(i,0,sz(vals))cout<<vals[i]<<" \n"[i == sz(vals)-1];
}else{
cout << "IMPOSSIBLE\n";
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |