// #pragma GCC optimize("O3","unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define no cout << "NO\n"
#define yes cout << "YES\n"
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) a * b / gcd(a, b)
#define all(v) v.begin(),v.end()
#define ret(a) return void(cout << a << "\n")
#define coutf(x) cout << fixed << setprecision(x)
#define inter(a) cout << a << "\n"; fflush(stdout)
#define shuf(v) shuffle(all(v), rnd);
#define sortuni(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define ar1d(a) for (int i = 1; i <= n; ++i) cin >> a[i];
#define ar2d(a) for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j) cin >> a[i][j];
#define graph(n, m) for (int i = 1; i <= m; ++i){int u, v; cin >> u >> v;g[u].push_back(v); g[v].push_back(u);};
#define graphd(n, m) for (int i = 1; i <= m; ++i){int u, v; cin >> u >> v;g[u].push_back(v);};
#define graphw(n, m) for (int i = 1; i <= m; ++i){int u, v, w; cin >> u >> v >> w;g[u].push_back({v, w}); g[v].push_back({u, w});};
#define graphdw(n, m) for (int i = 1; i <= m; ++i){int u, v, w; cin >> u >> v >> w;g[u].push_back({v, w});};
#define graph1(n, m) for (int i = 1; i <= m; ++i){int u[i], v[i]; cin >> u[i] >> v[i];g[u[i]].push_back(v[i]); g[v[i]].push_back(u[i]);}
#define graphd1(n, m) for (int i = 1; i <= m; ++i){int u[i], v[i]; cin >> u[i] >> v[i];g[u[i]].push_back(v[i]);}
#define graphw1(n, m) for (int i = 1; i <= m; ++i){int u[i], v[i], w[i]; cin >> u[i] >> v[i] >> w[i];g[u[i]].push_back({v[i], w[i]}); g[v[i]].push_back({u[i], w[i]});}
#define graphdw1(n, m) for (int i = 1; i <= m; ++i){int u[i], v[i], w[i]; cin >> u[i] >> v[i] >> w[i];g[u[i]].push_back({v[i], w[i]});}
#define trees(n) for (int i = 2; i <= n; ++i){int p; cin >> p; g[p].push_back(i);}
#define trees1(n) for (int i = 2; i <= n; ++i){int p[i]; cin >> p[i]; g[p[i]].push_back(i);}
const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[] = {0, 1, 0, -1, -1, 1, 1, -1};
mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
void _max(int &a, int b){a = max(a, b);}
void _min(int &a, int b){a = min(a, b);}
bool is_square(ll n){ll k = sqrt(n); return k * k == n;}
bool is_prime(ll n){if (n <= 3) return n > 1; if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i <= sqrt(n); i += 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true;}
ll rand(ll l, ll r){ll d = r - l + 1; return rnd() % d + l;}
ll bin_pow(ll a, ll b, ll MOD){ll ans = 1; if (a >= MOD) a %= MOD; while (b){if (b & 1) ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
ll bin_mul(ll a, ll b, ll MOD){ll ans = 0; if (a >= MOD) a %= MOD; while (b){if (b & 1) ans = (ans + a) % MOD; a = (a + a) % MOD; b /= 2;} return ans;}
// build(n, mod)
struct math{int N, MOD; vector <int> gt, rl; void build(int n, int mod){N = n; MOD = mod; gt.resize(N + 5); rl.resize(N + 5); gt[0] = rl[0] = 1; for (int i = 1; i <= N; ++i){gt[i] = 1LL * gt[i - 1] * i % MOD; rl[i] = bin_pow(gt[i], MOD - 2, MOD);}} int C(int a, int b){return 1LL * gt[b] * rl[a] % MOD * rl[b - a] % MOD;}};
// build(mod)
struct fibonacci{int MOD; map <ll,int> fibo; void build(int mod){MOD = mod; fibo[1] = fibo[2] = 1;} int fb(ll n){if (fibo.count(n)) return fibo[n]; if (n & 1) return fibo[n] = (1LL * fb(n / 2) * fb(n / 2) + 1LL * fb(n / 2 + 1) * fb(n / 2 + 1)) % MOD; return fibo[n] = (1LL * 2 * fb(n / 2 - 1) * fb(n / 2) + 1LL * fb(n / 2) * fb(n / 2)) % MOD;}};
const int D = 5e3, K = 1e6;
vector <int> ans, md[K + 5];
int k, q, d, m, a[D + 5];
map <int,bool> mp;
bool Check(int n)
{
if (mp.count(n)) return false;
mp[n] = true;
int p = n % k;
if (p < 0) p += k;
for (int x : md[p])
{
if (n == x)
{
ans.push_back(x);
return true;
}
else if (Check((n - x) / k))
{
ans.push_back(x);
return true;
}
}
return false;
}
void Solve()
{
cin >> k >> q >> d >> m;
for (int i = 1; i <= d; ++i)
{
cin >> a[i];
int p = a[i] % k;
if (p < 0) p += k;
md[p].push_back(a[i]);
}
while (q--)
{
int n;
cin >> n;
mp.clear();
ans.clear();
if (Check(n))
{
for (int i = 0; i < ans.size(); ++i)
{
cout << ans[i];
if (i < ans.size() - 1) cout << ' ';
}
}
else cout << "IMPOSSIBLE";
if (q) cout << "\n";
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
if (fopen("file.inp", "r"))
{
freopen ("file.inp", "r", stdin);
freopen ("file.out", "w", stdout);
}
int TEST = 1;
// cin >> TEST;
while (TEST--) Solve();
cerr << "\nTIME: " << 1000 * clock() / CLOCKS_PER_SEC << "ms.";
}
Compilation message
Main.cpp: In function 'void Solve()':
Main.cpp:93:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int i = 0; i < ans.size(); ++i)
| ~~^~~~~~~~~~~~
Main.cpp:96:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | if (i < ans.size() - 1) cout << ' ';
| ~~^~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:111:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | freopen ("file.inp", "r", stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:112:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | freopen ("file.out", "w", stdout);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
23888 KB |
OK |
| 2 |
Correct |
6 ms |
23904 KB |
OK |
| 3 |
Correct |
5 ms |
24056 KB |
OK |
| 4 |
Correct |
5 ms |
23888 KB |
OK |
| 5 |
Correct |
6 ms |
23916 KB |
OK |
| 6 |
Correct |
5 ms |
23896 KB |
OK |
| 7 |
Correct |
7 ms |
23888 KB |
OK |
| 8 |
Correct |
6 ms |
23888 KB |
OK |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
23888 KB |
OK |
| 2 |
Correct |
6 ms |
23904 KB |
OK |
| 3 |
Correct |
5 ms |
24056 KB |
OK |
| 4 |
Correct |
5 ms |
23888 KB |
OK |
| 5 |
Correct |
6 ms |
23916 KB |
OK |
| 6 |
Correct |
5 ms |
23896 KB |
OK |
| 7 |
Correct |
7 ms |
23888 KB |
OK |
| 8 |
Correct |
6 ms |
23888 KB |
OK |
| 9 |
Correct |
5 ms |
23888 KB |
OK |
| 10 |
Correct |
5 ms |
23888 KB |
OK |
| 11 |
Correct |
6 ms |
23884 KB |
OK |
| 12 |
Correct |
6 ms |
23888 KB |
OK |
| 13 |
Correct |
5 ms |
23904 KB |
OK |
| 14 |
Correct |
5 ms |
23888 KB |
OK |
| 15 |
Correct |
5 ms |
23888 KB |
OK |
| 16 |
Correct |
5 ms |
23888 KB |
OK |
| 17 |
Correct |
5 ms |
23888 KB |
OK |
| 18 |
Correct |
5 ms |
23888 KB |
OK |
| 19 |
Correct |
5 ms |
23888 KB |
OK |
| 20 |
Correct |
5 ms |
23888 KB |
OK |
| 21 |
Correct |
37 ms |
25160 KB |
OK |
| 22 |
Correct |
233 ms |
25116 KB |
OK |
| 23 |
Correct |
1061 ms |
25232 KB |
OK |
| 24 |
Correct |
429 ms |
25208 KB |
OK |
| 25 |
Correct |
5 ms |
23888 KB |
OK |
| 26 |
Correct |
5 ms |
23888 KB |
OK |
| 27 |
Correct |
5 ms |
24004 KB |
OK |
| 28 |
Correct |
4 ms |
23952 KB |
OK |
