oj.uz

Submission #1096169

# Submission time Handle Problem Language Result Execution time Memory
1096169 2024-10-04T03:43:38 Z vjudge1 Necklace (Subtask 1-3) (BOI19_necklace1) C
17 / 85
 257 ms 70740 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, int t_rev) {
    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] });
    if (t_rev) {
        res.j = M - 1 - res.j;
        res.j = res.j - res.max_len + 1;
    }
    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, 0);
    reverse(T, M);
    res = max(res, solve(S, N, T, M, 1));

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

    return 0;
}

Compilation message

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

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 1116 KB Output is partially correct
2 Partially correct 1 ms 1116 KB Output is partially correct
3 Correct 1 ms 1116 KB Output is correct
4 Partially correct 1 ms 1116 KB Output is partially correct
5 Correct 1 ms 1116 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 1116 KB Output is partially correct
2 Partially correct 1 ms 1116 KB Output is partially correct
3 Correct 1 ms 1116 KB Output is correct
4 Partially correct 1 ms 1116 KB Output is partially correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 5 ms 4836 KB Output is correct
7 Partially correct 4 ms 4700 KB Output is partially correct
8 Correct 5 ms 4188 KB Output is correct
9 Correct 5 ms 4696 KB Output is correct
10 Correct 4 ms 4700 KB Output is correct
11 Correct 4 ms 4700 KB Output is correct
12 Partially correct 7 ms 4644 KB Output is partially correct

Subtask #3
8.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 1116 KB Output is partially correct
2 Partially correct 1 ms 1116 KB Output is partially correct
3 Correct 1 ms 1116 KB Output is correct
4 Partially correct 1 ms 1116 KB Output is partially correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 5 ms 4836 KB Output is correct
7 Partially correct 4 ms 4700 KB Output is partially correct
8 Correct 5 ms 4188 KB Output is correct
9 Correct 5 ms 4696 KB Output is correct
10 Correct 4 ms 4700 KB Output is correct
11 Correct 4 ms 4700 KB Output is correct
12 Partially correct 7 ms 4644 KB Output is partially correct
13 Partially correct 194 ms 70740 KB Output is partially correct
14 Correct 195 ms 70740 KB Output is correct
15 Correct 257 ms 68536 KB Output is correct
16 Correct 240 ms 70228 KB Output is correct
17 Correct 146 ms 69620 KB Output is correct
18 Correct 151 ms 70632 KB Output is correct
19 Partially correct 180 ms 70312 KB Output is partially correct
20 Partially correct 202 ms 69372 KB Output is partially correct
21 Partially correct 190 ms 69720 KB Output is partially correct