Submission #852215

#TimeUsernameProblemLanguageResultExecution timeMemory
852215NaimSSWeird Numeral System (CCO21_day1problem2)C++14
25 / 25
796 ms5164 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...