結果
問題 | No.938 賢人を探せ |
ユーザー |
![]() |
提出日時 | 2019-12-05 19:37:41 |
言語 | C (gcc 13.3.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,464 bytes |
コンパイル時間 | 327 ms |
コンパイル使用メモリ | 30,464 KB |
実行使用メモリ | 16,196 KB |
最終ジャッジ日時 | 2024-12-14 11:48:58 |
合計ジャッジ時間 | 7,163 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 TLE * 1 |
ソースコード
// yuki 938 賢人を探せ // 2019.12.5 bal4u #include <stdio.h> #include <string.h> int getchar_unlocked(void); #define gc() getchar_unlocked() int in() { // 非負整数の入力 int n = 0, c = gc(); do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0'); return n; } void ins(char *s) { // 文字列の入力 スペース以下の文字で入力終了 do *s = gc(); while (*s++ > ' '); *(s-1) = 0; } // 文字列のハッシュ関数 #define HASHSIZ 199999 typedef struct { char *s; int id; } HASH; HASH hash[HASHSIZ+2], *hashend = hash + HASHSIZ; int insert(char *s, int id) { unsigned long long i; int j; char *p; HASH *tp; i = 0, p = s; for (j = 0; *p && j < 12; j++) i = (i << 5) + (*p++ +1-'a'); tp = hash + (int)(i % HASHSIZ); while (tp->s != NULL) { if (!strcmp(tp->s, s)) return tp->id; if (++tp == hashend) tp = hash; } tp->s = s, tp->id = id; return -1; } int lookup(char *s) { unsigned long long i; int j; char *p; HASH *tp; i = 0, p = s; for (j = 0; *p && j < 12; j++) i = (i << 5) + (*p++ +1-'a'); tp = hash + (int)(i % HASHSIZ); while (tp->s != NULL) { if (!strcmp(tp->s, s)) return 1; if (++tp == hashend) tp = hash; } return 0; } int w; char A[20005][12], B[20005][12]; int main() { int i, n, N; N = in(); for (i = 0; i < N; ++i) { ins(A[i]), insert(A[i], i); ins(B[i]); } n = N; for (i = 0; i < N; ++i) { if (!lookup(B[i])) { puts(B[i]); insert(B[i], n++); } } return 0; }