結果

問題 No.1631 Sorting Integers (Multiple of K) Easy
ユーザー 👑 ygussanyygussany
提出日時 2021-07-30 21:51:54
言語 C
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 1,392 bytes
コンパイル時間 145 ms
コンパイル使用メモリ 30,112 KB
実行使用メモリ 232,252 KB
最終ジャッジ日時 2023-10-14 04:24:03
合計ジャッジ時間 12,325 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
4,348 KB
testcase_01 AC 5 ms
4,348 KB
testcase_02 WA -
testcase_03 AC 14 ms
4,348 KB
testcase_04 AC 2 ms
4,352 KB
testcase_05 WA -
testcase_06 AC 3 ms
4,348 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 10 ms
4,352 KB
testcase_10 AC 10 ms
4,352 KB
testcase_11 WA -
testcase_12 AC 8 ms
4,352 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 466 ms
91,692 KB
testcase_17 AC 592 ms
85,608 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 20 ms
4,368 KB
testcase_23 AC 27 ms
9,348 KB
testcase_24 WA -
testcase_25 AC 20 ms
4,372 KB
testcase_26 AC 23 ms
5,728 KB
testcase_27 AC 147 ms
40,636 KB
testcase_28 WA -
testcase_29 AC 39 ms
9,548 KB
testcase_30 AC 96 ms
24,016 KB
testcase_31 WA -
権限があれば一括ダウンロードができます

ソースコード

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(int x, int r)
{
	return ((x << 10) + r) % H_Mod;
}

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

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("-1\n");
	fflush(stdout);
	return 0;
}
0