oj.uz

Submission #1096166

# Submission time Handle Problem Language Result Execution time Memory
1096166 2024-10-04T03:27:31 Z vjudge1 Necklace (Subtask 1-3) (BOI19_necklace1) C
0 / 85
 1 ms 1116 KB 
#include <stdio.h>
#include <string.h>

typedef struct {
    int max_len, i, j;
} res_t;

res_t max(res_t a, res_t b) {
    return a.max_len > b.max_len ? a : b;
}

void swap(char *a, char *b) {
    char tmp = *a;
    *a = *b;
    *b = tmp;
}

void reverse(char *T, int M) {
    int i = 0, j = M - 1;
    while (i < j) swap(T + i++, T + j--);
}

res_t solve(const char *S, int N, const char *T, int M) {
    static int pi1[3001][3001], pi2[3001][3001];

    for (int j = 0; j < M; j++) {
        for (int i = 2; i <= N; i++) {
            int k = pi1[j][i-1];
            while (k && S[i-1] != T[j+k]) k = pi1[j][k];
            if (S[i-1] == T[j+k]) k++;
            pi1[j][i] = k;
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 2; j <= M; j++) {
            int k = pi2[i][j-1];
            while (k && S[i+k] != T[j-1]) k = pi2[i][k];
            if (S[i+k] == T[j-1]) k++;
            pi2[i][j] = k;
        }
    }

    res_t res = {0};
    for (int i = 0; i <= N; i++)
        for (int j = 0; j <= M; j++)
            res = max(res, (res_t){ pi1[j][i] + pi2[i][j], i - pi1[j][i], j - pi2[i][j] });
    return res;
}

int main() {
    static char S[3001], T[3001];

    scanf("%s%s", S, T);
    int N = (int)strlen(S), M = (int)strlen(T);

    res_t res = solve(S, N, T, M);
    reverse(T, M);
    res = max(res, solve(S, N, T, M));

    printf("%d\n%d %d\n", res.max_len, res.i, res.j);

    return 0;
}

Compilation message

necklace.c: In function 'main':
necklace.c:54:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%s%s", S, T);
      |     ^~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 1112 KB Output is partially correct
2 Partially correct 1 ms 1116 KB Output is partially correct
3 Incorrect 1 ms 1116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 1112 KB Output is partially correct
2 Partially correct 1 ms 1116 KB Output is partially correct
3 Incorrect 1 ms 1116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 1112 KB Output is partially correct
2 Partially correct 1 ms 1116 KB Output is partially correct
3 Incorrect 1 ms 1116 KB Output isn't correct
4 Halted 0 ms 0 KB -