結果

問題 No.1631 Sorting Integers (Multiple of K) Easy
ユーザー 👑 ygussanyygussany
提出日時 2021-07-30 21:57:28
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 464 ms / 3,000 ms
コード長 1,396 bytes
コンパイル時間 238 ms
コンパイル使用メモリ 30,976 KB
実行使用メモリ 109,952 KB
最終ジャッジ日時 2024-09-16 00:04:35
合計ジャッジ時間 4,419 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 AC 4 ms
5,376 KB
testcase_02 AC 5 ms
5,376 KB
testcase_03 AC 13 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 4 ms
5,376 KB
testcase_09 AC 8 ms
5,376 KB
testcase_10 AC 7 ms
5,376 KB
testcase_11 AC 7 ms
5,376 KB
testcase_12 AC 6 ms
5,376 KB
testcase_13 AC 7 ms
5,376 KB
testcase_14 AC 194 ms
75,136 KB
testcase_15 AC 464 ms
109,056 KB
testcase_16 AC 452 ms
109,952 KB
testcase_17 AC 463 ms
109,440 KB
testcase_18 AC 456 ms
109,824 KB
testcase_19 AC 464 ms
109,312 KB
testcase_20 AC 14 ms
5,376 KB
testcase_21 AC 16 ms
5,376 KB
testcase_22 AC 15 ms
5,376 KB
testcase_23 AC 22 ms
7,808 KB
testcase_24 AC 17 ms
5,376 KB
testcase_25 AC 15 ms
5,376 KB
testcase_26 AC 30 ms
16,256 KB
testcase_27 AC 132 ms
50,560 KB
testcase_28 AC 69 ms
30,464 KB
testcase_29 AC 28 ms
11,648 KB
testcase_30 AC 75 ms
30,976 KB
testcase_31 AC 100 ms
39,168 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