結果

問題 No.1631 Sorting Integers (Multiple of K) Easy
ユーザー 👑 ygussanyygussany
提出日時 2021-07-30 21:57:28
言語 C
(gcc 13.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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