#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 = 10005;
int k, n;
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) <= MAXT && dist[N + MAXT] <= 1e7){
return dp[N] = true;
}
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(abs(N) > MAXT || dist[N + MAXT] > 1e7){
v.push_back(path[N]);
N -= v.back();
N /= k;
}
while(N){
v.push_back(par[N + MAXT]);
N -= v.back();
N /= k;
}
reverse(all(v));
for(auto &x : v) cout << x << " ";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int q, m;
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(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 << "\n";
trace(-x / k);
break;
}
}
if(!ok) cout << "IMPOSSIBLE\n";
continue;
}
if(dfs(N)){
trace(N);
cout << "\n";
}
else cout << "IMPOSSIBLE\n";
}
}
Compilation message
Main.cpp: In function 'bool dfs(lint)':
Main.cpp:22:16: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
22 | return dp[N] = true;
Main.cpp:25:36: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
25 | if(sz(a[modv]) == 0) return dp[N] =false;
Main.cpp:29:17: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
29 | return dp[N] = true;
Main.cpp:32:15: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
32 | return dp[N] = false;
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Query 1: Jury has an answer but participant does not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Query 1: Jury has an answer but participant does not |
| 2 |
Halted |
0 ms |
0 KB |
- |
