結果

問題 No.1631 Sorting Integers (Multiple of K) Easy
ユーザー ygussanyygussany
提出日時 2021-07-30 21:50:15
言語 C
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 1,391 bytes
コンパイル時間 296 ms
コンパイル使用メモリ 31,104 KB
実行使用メモリ 87,680 KB
最終ジャッジ日時 2024-09-15 23:47:18
合計ジャッジ時間 5,824 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 WA -
testcase_03 AC 10 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 WA -
testcase_06 AC 3 ms
5,376 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 8 ms
5,376 KB
testcase_10 AC 8 ms
5,376 KB
testcase_11 WA -
testcase_12 AC 6 ms
5,376 KB
testcase_13 AC 7 ms
5,376 KB
testcase_14 WA -
testcase_15 AC 649 ms
84,736 KB
testcase_16 AC 619 ms
85,248 KB
testcase_17 AC 750 ms
82,688 KB
testcase_18 AC 540 ms
87,680 KB
testcase_19 AC 761 ms
83,072 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 14 ms
5,376 KB
testcase_23 AC 21 ms
6,016 KB
testcase_24 WA -
testcase_25 AC 15 ms
5,376 KB
testcase_26 AC 17 ms
5,376 KB
testcase_27 AC 176 ms
38,656 KB
testcase_28 AC 97 ms
19,072 KB
testcase_29 AC 29 ms
8,832 KB
testcase_30 AC 112 ms
21,120 KB
testcase_31 AC 135 ms
28,544 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(int x, int r)
{
	return ((x << 4) + 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