#include<bits/stdc++.h>
using namespace std;
#define int long long
#define tii tuple<int,int,int>
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
const int maxk = 1e6+5, INF=0x3f3f3f3f, MOD=1e9+7;
map<int,bool> have;
int fast_exp(int a, int xp){
int rt=1;
while(xp>0){
if(xp&1) rt*=a;
xp/=2;
a*=a;
}
return rt;
}
int32_t main(){
int k,q,d,m; cin >> k >> q >> d >> m;
for(int i=0; i<d; i++){
int x; cin >> x;
have[x]=true;
}
while(q--){
int goal; cin >> goal;
if(goal==0){
if(have[0]) cout << 0 << '\n';
continue;
}
bool sinal=false;
if(goal<0) sinal=true, goal=-goal;
vector<int> real;
for(int b=0; fast_exp(k,b)<=goal; b++){
real.pb(goal%(fast_exp(k,b+1))/fast_exp(k,b));
}
vector<int> ans;
bool stc=false, ok=true;
if(!sinal){
for(int b=0; fast_exp(k,b-1)<=goal; b++){
if(have[real[b]+stc]) ans.pb(real[b]+stc), stc=false;
else if(have[real[b]+stc-k])ans.pb(real[b]+stc-k), stc=true;
else {ok=false; break;}
}
}
else{
for(int& x : real) x=-x;
for(int b=0; fast_exp(k,b-1)<=goal; b++){
if(have[real[b]-stc]) ans.pb(real[b]-stc), stc=false;
else if(have[real[b]-stc+k])ans.pb(real[b]-stc+k), stc=true;
else {ok=false; break;}
}
}
if(stc || !ok) cout << "IMPOSSIBLE\n";
else{
reverse(all(ans));
for(int x : ans) cout << x << " ";
cout << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 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 |
0 ms |
348 KB |
Query 1: Jury has an answer but participant does not |
| 2 |
Halted |
0 ms |
0 KB |
- |
