結果
問題 | No.1654 Binary Compression |
ユーザー | ygussany |
提出日時 | 2021-06-17 22:31:27 |
言語 | C (gcc 12.3.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,156 bytes |
コンパイル時間 | 300 ms |
コンパイル使用メモリ | 30,592 KB |
実行使用メモリ | 51,712 KB |
最終ジャッジ日時 | 2024-10-14 02:54:43 |
合計ジャッジ時間 | 6,141 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,248 KB |
testcase_04 | AC | 1 ms
5,248 KB |
testcase_05 | AC | 1 ms
5,248 KB |
testcase_06 | AC | 1 ms
5,248 KB |
testcase_07 | AC | 1 ms
5,248 KB |
testcase_08 | AC | 1 ms
5,248 KB |
testcase_09 | AC | 1 ms
5,248 KB |
testcase_10 | AC | 63 ms
27,008 KB |
testcase_11 | AC | 63 ms
27,264 KB |
testcase_12 | AC | 66 ms
28,160 KB |
testcase_13 | AC | 65 ms
28,032 KB |
testcase_14 | AC | 63 ms
27,264 KB |
testcase_15 | AC | 66 ms
27,776 KB |
testcase_16 | AC | 73 ms
51,584 KB |
testcase_17 | AC | 74 ms
51,712 KB |
testcase_18 | AC | 64 ms
28,032 KB |
testcase_19 | AC | 65 ms
28,032 KB |
testcase_20 | AC | 64 ms
28,160 KB |
testcase_21 | AC | 64 ms
28,032 KB |
testcase_22 | AC | 64 ms
28,032 KB |
testcase_23 | AC | 20 ms
5,248 KB |
testcase_24 | AC | 19 ms
5,248 KB |
testcase_25 | AC | 20 ms
5,248 KB |
testcase_26 | AC | 19 ms
5,248 KB |
testcase_27 | TLE | - |
testcase_28 | TLE | - |
testcase_29 | AC | 14 ms
5,248 KB |
testcase_30 | AC | 14 ms
5,248 KB |
testcase_31 | AC | 14 ms
5,248 KB |
testcase_32 | AC | 14 ms
5,248 KB |
testcase_33 | AC | 55 ms
36,096 KB |
testcase_34 | AC | 55 ms
36,096 KB |
testcase_35 | AC | 15 ms
5,248 KB |
testcase_36 | AC | 14 ms
5,248 KB |
testcase_37 | AC | 13 ms
5,248 KB |
testcase_38 | AC | 13 ms
5,248 KB |
testcase_39 | AC | 14 ms
5,248 KB |
testcase_40 | AC | 14 ms
5,248 KB |
testcase_41 | AC | 13 ms
5,248 KB |
testcase_42 | AC | 14 ms
5,248 KB |
testcase_43 | AC | 13 ms
5,248 KB |
testcase_44 | AC | 14 ms
5,248 KB |
testcase_45 | AC | 13 ms
5,248 KB |
testcase_46 | AC | 13 ms
5,248 KB |
testcase_47 | AC | 1 ms
5,248 KB |
testcase_48 | AC | 1 ms
5,248 KB |
testcase_49 | AC | 68 ms
46,848 KB |
testcase_50 | AC | 67 ms
46,848 KB |
testcase_51 | AC | 40 ms
16,384 KB |
testcase_52 | AC | 40 ms
16,512 KB |
ソースコード
#include <stdio.h> const int Mod = 924844033; typedef struct List { struct List *next; int len; long long sum; } list; int main() { char S[3000001]; scanf("%s", S); int i, j, k = 0, n = 0, A[3000001]; for (i = 0; S[i] != 0; i = j) { for (j = i + 1; S[j] == S[i]; j++); if (S[i] == '0') { if (n < j - i) n = j - i; A[k++] = i - j; } else A[k++] = j - i; } int m = 0; long long ans = 1, zero_lr = 1, tmp; list head, tail, d[3000001], *p; head.len = 0; tail.len = n + 1; tail.sum = 0; head.next = &tail; tail.next = NULL; if (A[k-1] < 0) zero_lr = -A[--k] + 1; if (k > 0) { if (A[0] < 0) zero_lr = zero_lr * (-A[0] + 1) % Mod; ans = A[k-1]; for (i = k - 3, j = k - 2; i >= 0; i -= 2, j -= 2) { for (p = &head; p->next->len <= -A[j]; p = p->next); d[m].len = -A[j]; d[m].sum = ans; d[m].next = p->next; head.next = &(d[m++]); for (p = &head, tmp = 0; p->next->len <= n; p = p->next) tmp += p->next->sum * (p->next->len - p->len) % Mod; ans += (tmp % Mod + 1) * A[i] % Mod; if (ans >= Mod) ans -= Mod; } } else zero_lr--; printf("%lld\n", ans * zero_lr % Mod); fflush(stdout); return 0; }