oj.uz

답안 #762658

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
762658 2023-06-21T15:43:52 Z rainboy Weird Numeral System (CCO21_day1problem2) C
0 / 25
 53 ms 79376 KB 
#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);
      |   ^~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 53 ms 79376 KB Expected integer, but "IMPOSSIBLE" found
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 53 ms 79376 KB Expected integer, but "IMPOSSIBLE" found
2 Halted 0 ms 0 KB -