#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int mod = 1e9 + 7;
const int MAXT = 30005;
int k, n, m;
vector<vector<int>> a;
int Mod(lint x){
return (x % k + k) % k;
}
int dist[3 * MAXT], par[3 * MAXT];
map<lint, int> dp, path;
bool dfs(lint N){
if(abs(N) <= k + m){
if(dist[N + MAXT] <= 1e7) return dp[N] = true;
return dp[N] = false;
}
lint modv = Mod(N);
if(sz(a[modv]) == 0) return dp[N] =false;
for(auto &x : a[modv]){
if(dfs((N - x) / k)){
path[N] = x;
return dp[N] = true;
}
}
return dp[N] = false;
}
void trace(lint N){
vector<int> v;
while(N){
if(abs(N) > k + m){
v.push_back(path[N]);
N -= v.back();
N /= k;
}
else{
v.push_back(par[N + MAXT]);
N -= v.back();
N /= k;
}
}
reverse(all(v));
for(auto &x : v) cout << x << " ";
cout << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int q;
cin >> k >> q >> n >> m;
a.resize(k);
vector<int> v(n);
for(int i = 0; i < n; i++){
cin >> v[i];
a[Mod(v[i])].push_back(v[i]);
}
memset(dist, 0x3f, sizeof(dist));
queue<int> que;
auto enq = [&](lint x, int d, int p){
if(abs(x) > MAXT) return;
if(dist[x + MAXT] > d){
dist[x + MAXT] = d;
par[x + MAXT] = p;
que.push(x);
}
};
enq(0, 0, -1);
while(sz(que)){
int x = que.front(); que.pop();
for(int i = 0; i < n; i++){
enq(1ll * x * k + v[i], dist[x + MAXT] + 1, v[i]);
}
}
while(q--){
lint N; cin >> N;
if(N == 0){
bool ok = 0;
for(auto &x : a[0]){
if(dfs(-x / k)){
ok = 1;
cout << x << " ";
trace(-x / k);
break;
}
}
if(!ok) cout << "IMPOSSIBLE\n";
continue;
}
if(dfs(N)){
trace(N);
}
else cout << "IMPOSSIBLE\n";
}
}
Compilation message
Main.cpp: In function 'bool dfs(lint)':
Main.cpp:22:42: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
22 | if(dist[N + MAXT] <= 1e7) return dp[N] = true;
Main.cpp:23:16: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
23 | return dp[N] = false;
Main.cpp:26:36: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
26 | if(sz(a[modv]) == 0) return dp[N] =false;
Main.cpp:30:17: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
30 | return dp[N] = true;
Main.cpp:33:15: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
33 | return dp[N] = false;
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
852 KB |
Expected integer, but "IMPOSSIBLE" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
852 KB |
Expected integer, but "IMPOSSIBLE" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
