Submission #762659

#	Time	Username	Problem	Language	Result	Execution time	Memory
762659		rainboy	Weird Numeral System (CCO21_day1problem2)	C11	25 / 25	702 ms	82472 KiB

Main

#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;
		int possible;

		scanf("%lld", &a);
		possible = 0;
		for (i = 0; i < n; i++)
			if ((a - dd[i]) % b == 0 && solve((a - dd[i]) / b)) {
				trace((a - dd[i]) / b), printf("%d\n", dd[i]);
				possible = 1;
				break;
			}
		if (!possible)
			printf("IMPOSSIBLE\n");
	}
	return 0;
}

Compilation message (stderr)

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:90:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |   scanf("%lld", &a);
      |   ^~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 17 / 17