Submission #584695

#	Time	Username	Problem	Language	Result	Execution time	Memory
584695		tengiz05	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	85 / 85	282 ms	456 KiB

necklace

#include <bits/stdc++.h>

using i64 = long long;
using namespace std;

std::vector<int> z_function(std::string s) {
    int n = s.length();
    std::vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i <= r)
            z[i] = std::min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
    return z;
}

std::vector<int> prefix_function(std::string s) {
    int n = s.size();
    std::vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    string a, b;
    cin >> a >> b;
    
    int n = a.size();
    int m = b.size();
    
    auto work = [&](string a, string b) -> array<int, 3> {
        array<int, 3> ans{-1, -1, -1};
        
        for (int i = 0; i < n; i++) {
            string S = a.substr(i, n - i) + "#" + b;
            string s1 = a.substr(0, i);
            string s2 = b;
            reverse(s1.begin(), s1.end());
            reverse(s2.begin(), s2.end());
            string T = s1 + "#" + s2;
            
            auto f = z_function(S);
            auto s = prefix_function(T);
            
            for (int j = 0; j < m; j++) {
                int k = f[n - i + 1 + j];
                if (j + k < m) {
                    int x = s[int(T.size()) - j - k - 1];
                    ans = max(ans, {k + x, i - x, j});
                } else {
                    ans = max(ans, {k, i, j});
                }
            }
        }
        
        return ans;
    };
    
    auto ans = work(a, b);
    reverse(b.begin(), b.end());
    auto res = work(a, b);
    res[2] = m - res[2] - res[0];
    
    ans = max(ans, res);
    
    cout << ans[0] << "\n";
    cout << ans[1] << " " << ans[2] << "\n";
    
    return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40