#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;
const int MAX = 120;
bool dp[MAX][SHIFT * 2 + 10];
int vis[MAX][SHIFT*2 + 10];
int go[MAX][SHIFT * 2 + 10];
int T;
int fdiv(int a, int b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
vi posi;
int TAM;
int solve(int p,int carry){
// dbg(p, carry)
if(abs(carry) >= SHIFT * 2)return 0;
if(p >= MAX)return 0;
bool &x = dp[p][carry + SHIFT];
if(vis[p][carry + SHIFT] == T)return x;
// cout << p << " " << carry << endl;cout.flush();
vis[p][carry + SHIFT] = T;
go[p][carry + SHIFT] = 0;
x = 0;
if(p >= TAM && carry == 0){
go[p][carry + SHIFT] = -1;
return x = 1;
}
if(p >= TAM){
rep(i,0,d){
int nv = carry + a[i];
// dbg(p,carry, nv);
if((nv%k + k)%k != (posi[p]%k + k)%k)continue;
if(fdiv(nv,k) == 0){
// dbg("here", p, carry + SHIFT);
go[p][carry + SHIFT] = i;
go[p+1][SHIFT] = -1;
return x = 1;
}
}
}
// dbg(p, carry);
rep(i,0,d){
int nv = carry + a[i] ;
if((nv%k + k)%k != (posi[p]%k + k)%k)continue;
// dbg(p,carry,nv, a[i], nv/k);
if(solve(p+1,fdiv(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)posi.pb(0);
while( N > 0 )posi.pb( N % k), N/= k;
TAM = sz(posi);
while(sz(posi) < MAX)posi.pb(0);
T++;
memset(dp,0,sizeof(dp)),memset(go,0,sizeof(go));
if(solve(0,0)){
int p = 0,carry = 0;
vi vals;
while(1){
int i = go[p][carry + SHIFT];
if(i==-1)break;
carry = fdiv(carry + a[i],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];
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9048 KB |
OK |
| 2 |
Correct |
2 ms |
8792 KB |
OK |
| 3 |
Correct |
2 ms |
8796 KB |
OK |
| 4 |
Correct |
2 ms |
8796 KB |
OK |
| 5 |
Correct |
2 ms |
8792 KB |
OK |
| 6 |
Correct |
2 ms |
8796 KB |
OK |
| 7 |
Correct |
2 ms |
9048 KB |
OK |
| 8 |
Correct |
2 ms |
9048 KB |
OK |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9048 KB |
OK |
| 2 |
Correct |
2 ms |
8792 KB |
OK |
| 3 |
Correct |
2 ms |
8796 KB |
OK |
| 4 |
Correct |
2 ms |
8796 KB |
OK |
| 5 |
Correct |
2 ms |
8792 KB |
OK |
| 6 |
Correct |
2 ms |
8796 KB |
OK |
| 7 |
Correct |
2 ms |
9048 KB |
OK |
| 8 |
Correct |
2 ms |
9048 KB |
OK |
| 9 |
Correct |
2 ms |
9048 KB |
OK |
| 10 |
Correct |
2 ms |
9052 KB |
OK |
| 11 |
Correct |
2 ms |
9052 KB |
OK |
| 12 |
Correct |
2 ms |
9048 KB |
OK |
| 13 |
Correct |
2 ms |
9304 KB |
OK |
| 14 |
Correct |
2 ms |
9052 KB |
OK |
| 15 |
Correct |
2 ms |
9048 KB |
OK |
| 16 |
Incorrect |
2 ms |
8796 KB |
Query 1: Jury has an answer but participant does not |
| 17 |
Halted |
0 ms |
0 KB |
- |
