結果
問題 | No.434 占い |
ユーザー |
![]() |
提出日時 | 2019-05-08 23:34:56 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,466 bytes |
コンパイル時間 | 332 ms |
コンパイル使用メモリ | 31,616 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-02 00:33:50 |
合計ジャッジ時間 | 1,793 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
コンパイルメッセージ
main.c: In function 'in': main.c:8:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration] 8 | #define gc() getchar_unlocked() | ^~~~~~~~~~~~~~~~ main.c:16:24: note: in expansion of macro 'gc' 16 | int n = 0, c = gc(); | ^~ main.c: In function 'main': main.c:9:15: warning: implicit declaration of function 'putchar_unlocked' [-Wimplicit-function-declaration] 9 | #define pc(c) putchar_unlocked(c) | ^~~~~~~~~~~~~~~~ main.c:77:17: note: in expansion of macro 'pc' 77 | pc('0'+s), pc('\n'); | ^~
ソースコード
// yukicoder: No.432 占い(Easy)// 2019.4.17 bal4u#include <stdio.h>#include <string.h>#if 1#define gc() getchar_unlocked()#define pc(c) putchar_unlocked(c)#else#define gc() getchar()#define pc(c) putchar(c)#endifint in(){int n = 0, c = gc();do n = 10 * n + (c & 0xf), c = gc(); while (c >= '0');return n;}int ins(char *s) // 文字列の入力 スペース以下の文字で入力終了{char *p = s;do *s = gc();while (*s++ > ' ');*--s = 0;return s - p;}#define MOD 9char S[100003], *p;int tbl[100003][2]; int id = -1;char t[100003];int inv[10] = {0,1,5,0,7,2,0,4,8,0};int p3(int *a, int n) {int r = 0;while (n % 3 == 0) r++, n /= 3;*a = n;return r;}void calcBC(int n){int i, a, b;tbl[0][0] = 1, tbl[0][1] = 0, t[0] = 1;if (n == 0) return;tbl[1][1] = p3(&a, n), tbl[1][0] = a % MOD, t[1] = n % MOD;for (i = 2; i <= n; i++) {tbl[i][1] = tbl[i-1][1] + p3(&a, n+1-i) - p3(&b, i);tbl[i][0] = (tbl[i-1][0] * a * inv[(b % MOD)]) % MOD;if (tbl[i][1] >= 2) t[i] = 0;else if (tbl[i][1] == 0) t[i] = tbl[i][0] % MOD;else t[i] = tbl[i][0]*3 % MOD;}}int main(){int i, w, s, T;T = in();while (T--) {w = ins(p = S)-1;while (*p == '0') p++;if (*p == 0) s = 0;else {if (id != w) calcBC(w), id = w;s = 0; for (i = 0; i <= w; i++) {if (S[i] < '9') s += (S[i] & 0xf) * t[i];}s %= 9;if (s == 0) s = 9;}pc('0'+s), pc('\n');}return 0;}