oj.uz

Submission #762659

# Submission time Handle Problem Language Result Execution time Memory
762659 2023-06-21T15:46:40 Z rainboy Weird Numeral System (CCO21_day1problem2) C
25 / 25
 702 ms 82472 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;
		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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 79348 KB OK
2 Correct 54 ms 79136 KB OK
3 Correct 56 ms 78848 KB OK
4 Correct 53 ms 78892 KB OK
5 Correct 61 ms 78796 KB OK
6 Correct 58 ms 78544 KB OK
7 Correct 53 ms 78796 KB OK
8 Correct 53 ms 78860 KB OK

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 79348 KB OK
2 Correct 54 ms 79136 KB OK
3 Correct 56 ms 78848 KB OK
4 Correct 53 ms 78892 KB OK
5 Correct 61 ms 78796 KB OK
6 Correct 58 ms 78544 KB OK
7 Correct 53 ms 78796 KB OK
8 Correct 53 ms 78860 KB OK
9 Correct 54 ms 79956 KB OK
10 Correct 54 ms 79532 KB OK
11 Correct 54 ms 79180 KB OK
12 Correct 55 ms 78940 KB OK
13 Correct 59 ms 80676 KB OK
14 Correct 54 ms 79504 KB OK
15 Correct 54 ms 79276 KB OK
16 Correct 56 ms 78748 KB OK
17 Correct 53 ms 78484 KB OK
18 Correct 55 ms 80176 KB OK
19 Correct 54 ms 79712 KB OK
20 Correct 60 ms 78780 KB OK
21 Correct 76 ms 82460 KB OK
22 Correct 181 ms 82472 KB OK
23 Correct 702 ms 82396 KB OK
24 Correct 324 ms 82456 KB OK
25 Correct 54 ms 80212 KB OK
26 Correct 59 ms 80152 KB OK
27 Correct 53 ms 78524 KB OK
28 Correct 54 ms 78444 KB OK