oj.uz

Submission #621492

# Submission time Handle Problem Language Result Execution time Memory
621492 2022-08-03T21:17:38 Z brobat Necklace (Subtask 1-3) (BOI19_necklace1) C++17
17 / 85
 191 ms 35864 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;
    a = '2' + a + '3';
    int m = a.length();
    b = '0' + b + '1';
    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 - 1 << " " << pos.second - 1 << '\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 320 KB Output is correct
3 Partially correct 1 ms 340 KB Output is partially correct
4 Correct 1 ms 324 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 320 KB Output is correct
3 Partially correct 1 ms 340 KB Output is partially correct
4 Correct 1 ms 324 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 956 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 4 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 320 KB Output is correct
3 Partially correct 1 ms 340 KB Output is partially correct
4 Correct 1 ms 324 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 956 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 4 ms 852 KB Output is correct
13 Correct 190 ms 35864 KB Output is correct
14 Correct 191 ms 35792 KB Output is correct
15 Partially correct 189 ms 33712 KB Output is partially correct
16 Correct 169 ms 35216 KB Output is correct
17 Correct 140 ms 34524 KB Output is correct
18 Correct 146 ms 35564 KB Output is correct
19 Correct 185 ms 35476 KB Output is correct
20 Correct 184 ms 34476 KB Output is correct
21 Correct 172 ms 34816 KB Output is correct