#include <stdio.h>
#include <stdlib.h>
#define N 5001
#define M 1000000
#define MD 0x7fffffff
#define X 1000000000000000000LL
long long *ek[M]; int *ev[M], eo[M], Z = 314159265;
void init() {
int h;
for (h = 0; h < M; h++) {
ek[h] = (long long *) malloc(2 * sizeof *ek[h]);
ev[h] = (int *) malloc(2 * sizeof *ev[h]);
}
}
int hash(long long k) {
long long k1, k2;
k += X, k1 = k / MD, k2 = k % MD;
return (k1 * Z % MD + k2) % MD * Z % MD % M;
}
void put(long long k, int v) {
int h = hash(k), o;
for (o = eo[h]; o--; )
if (ek[h][o] == k) {
ev[h][o] = v;
return;
}
o = eo[h]++;
if (o >= 2 && (o & o - 1) == 0) {
ek[h] = (long long *) realloc(ek[h], o * 2 * sizeof *ek[h]);
ev[h] = (int *) realloc(ev[h], o * 2 * sizeof *ev[h]);
}
ek[h][o] = k, ev[h][o] = v;
}
int get(long long k) {
int h = hash(k), o;
for (o = eo[h]; o--; )
if (ek[h][o] == k)
return ev[h][o];
return -1;
}
int dd[N], n, b;
int solve(long long a) {
int i;
if (a == 0)
return 1;
if ((i = get(a)) == -1) {
put(a, n);
for (i = 0; i < n; i++)
if ((a - dd[i]) % b == 0 && solve((a - dd[i]) / b)) {
put(a, i);
break;
}
}
return i < n;
}
void trace(long long a) {
int i;
if (a == 0)
return;
i = get(a);
trace((a - dd[i]) / b), printf("%d ", dd[i]);
}
int main() {
int q, i;
init();
scanf("%d%d%d%*d", &b, &q, &n);
for (i = 0; i < n; i++)
scanf("%d", &dd[i]);
while (q--) {
long long a;
scanf("%lld", &a);
if (a == 0)
printf("0\n");
else if (solve(a))
trace(a), printf("\n");
else
printf("IMPOSSIBLE\n");
}
return 0;
}
Compilation message
Main.c: In function 'put':
Main.c:36:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
36 | if (o >= 2 && (o & o - 1) == 0) {
| ~~^~~
Main.c: In function 'main':
Main.c:83:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | scanf("%d%d%d%*d", &b, &q, &n);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:85:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | scanf("%d", &dd[i]);
| ^~~~~~~~~~~~~~~~~~~
Main.c:89:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | scanf("%lld", &a);
| ^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
79376 KB |
Expected integer, but "IMPOSSIBLE" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
79376 KB |
Expected integer, but "IMPOSSIBLE" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
