oj.uz

답안 #621484

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
621484 2022-08-03T21:09:03 Z brobat Necklace (Subtask 1-3) (BOI19_necklace1) C++17
17 / 85
 207 ms 35760 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();
    b = '0' + b;
    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 - 1 << '\n';
    
    return 0;
}

Subtask #1
5.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Partially correct 1 ms 340 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Partially correct 1 ms 340 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 4 ms 960 KB Output is correct
7 Correct 4 ms 980 KB Output is correct
8 Correct 4 ms 852 KB Output is correct
9 Correct 5 ms 980 KB Output is correct
10 Correct 4 ms 960 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Partially correct 1 ms 340 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 4 ms 960 KB Output is correct
7 Correct 4 ms 980 KB Output is correct
8 Correct 4 ms 852 KB Output is correct
9 Correct 5 ms 980 KB Output is correct
10 Correct 4 ms 960 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 4 ms 852 KB Output is correct
13 Correct 207 ms 35760 KB Output is correct
14 Correct 192 ms 35700 KB Output is correct
15 Partially correct 207 ms 33620 KB Output is partially correct
16 Correct 201 ms 35220 KB Output is correct
17 Correct 144 ms 34628 KB Output is correct
18 Correct 174 ms 35472 KB Output is correct
19 Correct 193 ms 35460 KB Output is correct
20 Correct 181 ms 34424 KB Output is correct
21 Correct 184 ms 34828 KB Output is correct