제출 #1103686

#제출 시각아이디문제언어결과실행 시간메모리
1103686BuzzyBeezWeird Numeral System (CCO21_day1problem2)C++17
0 / 25
1 ms336 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const long long inf = LLONG_MAX; map<long long, long long> memo; vector<int> arr; int d; long long K; // bool attempt(long long R) { // if (par.count(R)) return (par[R] != inf); // par[R] = inf; // for (int x : arr) if (abs(R - x) % K == 0) // if (R == x || attempt((R - x) / K)) {par[R] = x; return 1;} // return 0; // } bool attempt(long long a){ if(memo.count(a))return memo[a]!=LLONG_MAX; memo[a]=LLONG_MAX; for(auto x:arr){ if((a-x)%K==0){ if(a-x==0||attempt((a-x)/K)){ memo[a]=x; return true; } } } return false; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int q, m; cin >> K >> q >> d >> m; arr.resize(d); for (int i = 0; i < d; ++i) cin >> arr[i]; long long N; bool pass; while (q--) { cin >> N; pass = attempt(N); if (!pass) cout << "IMPOSSIBLE\n"; else { vector<int> ans; long long x; while (1) { x = memo[N]; ans.push_back(x); N = (N - x) / K; if (N == 0) break; } reverse(ans.begin(), ans.end()); for (int i : ans) cout << i << ' '; cout << '\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...