結果

問題 No.3000 Optimal Run Length Encoding
ユーザー 👑 ygussany
提出日時 2024-12-25 23:06:03
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 4,759 bytes
コンパイル時間 668 ms
コンパイル使用メモリ 35,044 KB
実行使用メモリ 184,480 KB
最終ジャッジ日時 2024-12-25 23:24:47
合計ジャッジ時間 1,117,412 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 WA * 43 TLE * 98
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
#include <stdlib.h>
typedef struct HList {
    struct HList *next;
    int l, r, min, argmin[2];
} hlist;
#define HASH 5000011
const int H_Mod = HASH;
int hn;
hlist *hash[HASH] = {}, hd[10000001];
int hash_func(int l, int r)
{
    return (((long long)l << 30) + r) % H_Mod;
}
void Z_algorithm(char S[], int Z[])
{
    int i, j, k, l;
    for (l = 0; S[l] != 0; l++);
    Z[0] = l;
    for (i = 1, j = 0; i < l; i++) {
        for (; i + j < l && S[i+j] == S[j]; j++);
        Z[i] = j;
        if (j == 0) continue;
        
        for (k = 1; k < j && k + Z[k] < j; k++) Z[i+k] = Z[k];
        i += k - 1;
        j -= k;
    }
}
int recursion(char S[], int l, int r)
{
    if (r <= l) return 0;
    else if (r == l + 1) return 2;
    
    int h = hash_func(l, r);
    hlist *hp;
    for (hp = hash[h]; hp != NULL; hp = hp->next) if (hp->l == l && hp->r == r) return hp->min;
    hp = &(hd[hn++]);
    hp->l = l;
    hp->r = r;
    hp->min = r - l + 1;
    hp->argmin[0] = l;
    hp->argmin[1] = r;
    hp->next = hash[h];
    hash[h] = hp;
    
    int m = (l + r) / 2, tmp[2] = {recursion(S, l, m), recursion(S, m, r)};
    if (hp->min > tmp[0] + tmp[1]) {
        hp->min = tmp[0] + tmp[1];
        hp->argmin[0] = m;
        hp->argmin[1] = m;
    }
    
    int i, j, k, kk, kkk, ll, rr, *Z[2];
    char *T[2];
    T[0] = (char*)malloc(sizeof(char) * (m - l + 1));
    T[1] = (char*)malloc(sizeof(char) * (r - m + 1 + r - l + 1));
    Z[0] = (int*)malloc(sizeof(int) * (m - l + 1 + 1));
    Z[1] = (int*)malloc(sizeof(int) * (r - m + 1 + r - l + 1));
    for (i = 0, j = m - 1; j >= l; i++, j--) T[0][i] = S[j];
    T[0][i] = 0;
    Z[0][i] = 0;
    for (i = 0, j = m; j < r; i++, j++) T[1][i] = S[j];
    T[1][i++] = '#';
    for (j = l; j < r; i++, j++) T[1][i] = S[j];
    T[1][i] = 0;
    Z_algorithm(T[0], Z[0]);
    Z_algorithm(T[1], Z[1]);
    for (i = 1, j = m - l; i <= m - l && j >= 0; i++, j--) {
        k = Z[0][i] + Z[1][r-m+j] + i;
        if (k < i * 2) continue;
        for (kk = k / i, kkk = 0; kk > 0; kk /= 10, kkk++);
        kk = k / i * i;
        for (ll = m - i - Z[0][i], rr = ll + kk; rr <= m + Z[1][r-m+j]; ll++, rr++) {
            if (rr < m) continue;
            tmp[0] = recursion(S, l, ll);
            tmp[1] = recursion(S, rr, r);
            if (hp->min > tmp[0] + tmp[1] + i + kkk) {
                hp->min = tmp[0] + tmp[1] + i + kkk;
                hp->argmin[0] = ll;
                hp->argmin[1] = rr;
            }
        }
    }
    free(T[0]);
    free(T[1]);
    free(Z[0]);
    free(Z[1]);
    
    T[0] = (char*)malloc(sizeof(char) * (r - m + 1));
    T[1] = (char*)malloc(sizeof(char) * (m - l + 1 + r - l + 1));
    Z[0] = (int*)malloc(sizeof(int) * (r - m + 1 + 1));
    Z[1] = (int*)malloc(sizeof(int) * (m - l + 1 + r - l + 1));
    for (i = 0, j = m; j < r; i++, j++) T[0][i] = S[j];
    T[0][i] = 0;
    Z[0][i] = 0;
    for (i = 0, j = m - 1; j >= l; i++, j--) T[1][i] = S[j];
    T[1][i++] = '#';
    for (j = r - 1; j >= l; i++, j--) T[1][i] = S[j];
    T[1][i] = 0;
    Z_algorithm(T[0], Z[0]);
    Z_algorithm(T[1], Z[1]);
    for (i = 1, j = r - m; i <= r - m && j >= 0; i++, j--) {
        k = Z[0][i] + Z[1][m-l+j] + i;
        if (k < i * 2) continue;
        for (kk = k / i, kkk = 0; kk > 0; kk /= 10, kkk++);
        kk = k / i * i;
        for (rr = m + i + Z[0][i], ll = rr - kk; ll >= m - Z[1][m-l+j]; ll--, rr--) {
            if (ll > m) continue;
            tmp[0] = recursion(S, l, ll);
            tmp[1] = recursion(S, rr, r);
            if (hp->min > tmp[0] + tmp[1] + i + kkk) {
                hp->min = tmp[0] + tmp[1] + i + kkk;
                hp->argmin[0] = ll;
                hp->argmin[1] = rr;
            }
        }
    }
    free(T[0]);
    free(T[1]);
    free(Z[0]);
    free(Z[1]);
    // printf("%d %d: %d %d %d\n", l, r, hp->min, hp->argmin[0], hp->argmin[1]);
    return hp->min;
}
void recover(char S[], int l, int r, char ans[])
{
    if (r <= l) return;
    else if (r == l + 1) {
        ans[0] = S[l];
        ans[1] = '1';
        return;
    }
    
    int h = hash_func(l, r), i, j, k = 0, kk;
    char tmp[10];
    hlist *hp;
    for (hp = hash[h]; hp != NULL; hp = hp->next) if (hp->l == l && hp->r == r) break;
    if (hp->argmin[0] > l) {
        recover(S, l, hp->argmin[0], ans);
        k = recursion(S, l, hp->argmin[0]);
    }
    if (hp->argmin[0] < hp->argmin[1]) {
        for (i = 1; i < hp->argmin[1] - hp->argmin[0]; i++) {
            if ((hp->argmin[1] - hp->argmin[0]) % i != 0) continue;
            for (j = hp->argmin[0] + i; j < hp->argmin[1]; j++) if (S[j] != S[j-i]) break;
            if (j == hp->argmin[1]) break;
        }
        for (j = 0; j < i; j++) ans[k++] = S[hp->argmin[0] + j];
        for (j = (hp->argmin[1] - hp->argmin[0]) / i, kk = 0; j > 0; j /= 10, kk++) tmp[kk] = '0' + j % 10;
        while (kk--) ans[k++] = tmp[kk];
    }
    if (hp->argmin[1] < r) recover(S, hp->argmin[1], r, &(ans[k]));
}
void solve(char S[], char ans[])
{
    int h, i, l, min;
    for (l = 0, hn = 0; S[l] != 0; l++);
    min = recursion(S, 0, l);
    recover(S, 0, l, ans);
    ans[min] = 0;
    for (i = 0; i < hn; i++) hash[hash_func(hd[i].l, hd[i].r)] = NULL;
}
int main()
{
    int T;
    char S[500001], ans[500003];
    scanf("%d", &T);
    while (T--) {
        scanf("%s", S);
        solve(S, ans);
        printf("%s\n", ans);
    }
    fflush(stdout);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0