結果

問題 No.1631 Sorting Integers (Multiple of K) Easy
ユーザー 👑 ygussanyygussany
提出日時 2021-07-30 21:57:28
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 417 ms / 3,000 ms
コード長 1,396 bytes
コンパイル時間 239 ms
コンパイル使用メモリ 30,136 KB
実行使用メモリ 111,956 KB
最終ジャッジ日時 2023-10-14 04:37:34
合計ジャッジ時間 4,467 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
4,348 KB
testcase_01 AC 5 ms
4,348 KB
testcase_02 AC 6 ms
4,348 KB
testcase_03 AC 15 ms
4,700 KB
testcase_04 AC 2 ms
4,352 KB
testcase_05 AC 2 ms
4,352 KB
testcase_06 AC 3 ms
4,352 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 5 ms
4,352 KB
testcase_09 AC 10 ms
4,348 KB
testcase_10 AC 9 ms
4,352 KB
testcase_11 AC 9 ms
4,348 KB
testcase_12 AC 8 ms
4,348 KB
testcase_13 AC 9 ms
4,352 KB
testcase_14 AC 176 ms
75,996 KB
testcase_15 AC 388 ms
110,944 KB
testcase_16 AC 391 ms
111,956 KB
testcase_17 AC 401 ms
111,356 KB
testcase_18 AC 398 ms
111,816 KB
testcase_19 AC 417 ms
111,148 KB
testcase_20 AC 18 ms
4,348 KB
testcase_21 AC 20 ms
4,352 KB
testcase_22 AC 20 ms
4,348 KB
testcase_23 AC 27 ms
9,244 KB
testcase_24 AC 22 ms
4,816 KB
testcase_25 AC 21 ms
4,348 KB
testcase_26 AC 34 ms
16,380 KB
testcase_27 AC 135 ms
51,456 KB
testcase_28 AC 67 ms
32,128 KB
testcase_29 AC 33 ms
13,272 KB
testcase_30 AC 71 ms
32,784 KB
testcase_31 AC 84 ms
39,476 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

#define HASH 1000003
const int H_Mod = HASH;

typedef struct List {
	struct List *next;
	int r;
	long long x, num;
} list;

int hash_func(long long x, int r)
{
	return ((x << 10) + r) % H_Mod;
}

int n = 1;
list *hash[15][HASH] = {}, d[5000000];

void BFS(int N, int K)
{
	if (N == 0) return;

	int h, hh, i, j;
	long long y, z;
	list *p, *pp;
	for (h = 0; h < H_Mod; h++) {
		for (p = hash[N][h]; p != NULL; p = p->next) {
			for (i = 9, y = p->x, z = 1; i >= 1; i--, y >>= 4, z <<= 4) {
				if (y % 16 == 0) continue;
				j = (p->r * 10 + i) % K;
				hh = hash_func(p->x - z, j);
				for (pp = hash[N-1][hh]; pp != NULL; pp = pp->next) if (pp->x == p->x - z && pp->r == j) break;
				if (pp != NULL) pp->num += p->num;
				else {
					d[n].x = p->x - z;
					d[n].r = j;
					d[n].num = p->num;
					d[n].next = hash[N-1][hh];
					hash[N-1][hh] = &(d[n++]);
				}
			}
		}
	}
	BFS(N - 1, K);
}

int main()
{
	int h, i, j, N, K, c[10];
	list *p;
	scanf("%d %d", &N, &K);
	for (i = 1, c[0] = 0, d[0].x = 0; i <= 9; i++) {
		scanf("%d", &(c[i]));
		d[0].x = (d[0].x << 4) + c[i];
	}
	d[0].r = 0;
	d[0].num = 1;
	h = hash_func(d[0].x, d[0].r);
	d[0].next = hash[N][h];
	hash[N][h] = &(d[0]);
	BFS(N, K);
	for (p = hash[0][0]; p != NULL; p = p->next) if (p->x == 0 && p->r == 0) break;
	if (p != NULL) printf("%lld\n", p->num);
	else printf("0\n");
	fflush(stdout);
	return 0;
}
0