#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;
int a[2505];
const int SHIFT = 2500 * 2;
bool dp[SHIFT * 4 + 10][80];
int vis[SHIFT*4 + 10][80];
int go[SHIFT * 4 + 10][80];
int T;
vi posi;
int solve(int p,int carry){
if(abs(carry) >= SHIFT * 4)return 0;
if(p >= 80)return 0;
bool &x = dp[p][carry + SHIFT];
if(vis[p][carry + SHIFT] == T)return x;
vis[p][carry + SHIFT] = T;
x = 0;
if(p >= sz(posi) && carry == 0){
go[p][carry + SHIFT] = -1;
return x = 1;
}
rep(i,0,d){
int nv = carry + a[i] - (p < sz(posi) ? posi[p] : 0);
if(nv%k != 0)continue;
if((nv/k) == 0){
go[p][carry + SHIFT] = i;
return x = 1;
}
}
// dbg(p, carry);
rep(i,0,d){
int nv = carry + a[i] - (p < sz(posi) ? posi[p] : 0);
if(nv%k !=0 )continue;
// dbg(p,carry,nv, a[i], nv/k);
if(solve(p+1,(nv/k))){
go[p][carry + SHIFT] = i;
return x = 1;
}
}
return x = 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];
sort(a,a+d);
while(q--){
posi.clear();
ll N;
cin >> N;
int rev = 0;
if( N < 0 ){
N *= -1;
rep(i,0,d)a[i] = -a[i];
rev = 1;
}
if(N == 0) {
int ok =0;
rep(i,0,d){
if(a[i] == 0){
ok = 1;
}
}
if(ok)cout << "0\n";
else cout << "IMPOSSIBLE\n";
continue;
}
while( N > 0 )posi.pb( N % k), N/= k;
T++;
if(solve(0,0)){
int p = 0,carry = 0;
vi vals;
while(1){
int i = go[p][carry + SHIFT];
if(i==-1)break;
carry = (carry + a[i] - ( p < sz(posi)? posi[p] : 0))/k;
vals.pb(a[i]);
p++;
}
reverse(all(vals));
rep(i,0,sz(vals)){
if(rev)vals[i]*=-1;
cout << vals[i] <<" \n"[i == sz(vals)-1];
}
}else{
cout << "IMPOSSIBLE\n";
}
if(rev){
rep(i,0,d)a[i] = -a[i];
}
}
}
Compilation message
Main.cpp: In function 'int _Z5solveii.part.0(int, int)':
Main.cpp:43:28: warning: array subscript 5000 is above array bounds of 'int [80]' [-Warray-bounds]
43 | go[p][carry + SHIFT] = -1;
| ~~~~~~~~~~~~~~~~~~~^
Main.cpp:38:34: warning: array subscript 5000 is above array bounds of 'bool [80]' [-Warray-bounds]
38 | bool &x = dp[p][carry + SHIFT];
| ~~~~~~~~~~~~~~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1248 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1248 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
