oj.uz

Submission #621475

# Submission time Handle Problem Language Result Execution time Memory
621475 2022-08-03T20:54:44 Z brobat Necklace (Subtask 1-3) (BOI19_necklace1) C++17
17 / 85
 210 ms 35764 KB 
#include <bits/stdc++.h>
using namespace std;

vector <int> kmp(string &a, string &b) {
    string s = b + '#' + a;
    int n = s.length();
    vector <int> p(n);
    p[0] = 0;
    for(int i = 1; i < n; i++) {
        int j = p[i - 1];
        while(j > 0 && s[i] != s[j]) {
            j = p[j - 1];
        }
        if(s[i] == s[j]) {
            j++;
        }
        p[i] = j;
    }
    vector <int> q(a.length());
    for(int i = 0; i < (int)a.length(); i++) {
        q[i] = p[i + (int)b.length() + 1];
    }
    return q;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string a, b;
    cin >> a >> b;
    int m = a.length();
    int n = b.length();
    vector<vector<int>> p(m, vector<int>(n));
    for(int i = 0; i < m; i++) {
        string temp;
        for(int j = i; j < m; j++) temp += a[j];
        p[i] = kmp(b, temp);
    }
    int ans = 0;
    pair <int, int> pos = {-1, -1};
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(p[i][j] > ans) {
                ans = p[i][j];
                pos = {i, j - p[i][j] + 1};
            }
            int x = p[i][j];
            if(x > 0 && i + x < m && j - x >= 0) {
                if(p[i + x][j - x] + p[i][j] > ans) {
                    ans = p[i + x][j - x] + p[i][j];
                    pos = {i, j - ans + 1};
                }
            }
        }
    }
    // repeat entire procedure after reversing a
    reverse(a.begin(), a.end());
    for(int i = 0; i < m; i++) {
        string temp;
        for(int j = i; j < m; j++) temp += a[j];
        // cout << temp << " ";
        p[i] = kmp(b, temp);
    }
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(p[i][j] > ans) {
                ans = p[i][j];
                int ind = i + p[i][j] - 1;
                // cout << i << " " << j << ind << '\n';
                pos = {m - ind - 1, j - p[i][j] + 1};
            }
            int x = p[i][j];
            if(x > 0 && i + x < m && j - x >= 0) {
                if(p[i + x][j - x] + p[i][j] > ans) {
                    ans = p[i + x][j - x] + p[i][j];
                    int ind = i + x + p[i + x][j - x] - 1;
                    // cout << i << " " << j << ind << '\n';
                    pos = {m - ind - 1, j - ans + 1};
                }
            }
        }
    }
    cout << ans << '\n';
    cout << pos.first << " " << pos.second << '\n';
    
    return 0;
}

Subtask #1
5.0 / 25.0

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

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Partially correct 1 ms 324 KB Output is partially correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 5 ms 980 KB Output is correct
7 Correct 4 ms 980 KB Output is correct
8 Correct 4 ms 852 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 4 ms 960 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 3 ms 852 KB Output is correct

Subtask #3
8.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Partially correct 1 ms 324 KB Output is partially correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 5 ms 980 KB Output is correct
7 Correct 4 ms 980 KB Output is correct
8 Correct 4 ms 852 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 4 ms 960 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 3 ms 852 KB Output is correct
13 Correct 210 ms 35764 KB Output is correct
14 Correct 194 ms 35760 KB Output is correct
15 Partially correct 187 ms 33696 KB Output is partially correct
16 Correct 177 ms 35200 KB Output is correct
17 Correct 155 ms 34456 KB Output is correct
18 Correct 164 ms 35500 KB Output is correct
19 Correct 157 ms 35424 KB Output is correct
20 Correct 168 ms 34464 KB Output is correct
21 Correct 182 ms 34792 KB Output is correct