Submission #706675

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
706675	2023-03-07T10:50:24 Z	LittleCube	Necklace (Subtask 4) (BOI19_necklace4)	C++14	15 / 15	787 ms	460 KB

necklace

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

string s, t;

vector<int> Z(string s)
{
    int N = s.size(), mxZ = 0, mxi = 0;
    vector<int> z(N);
    for (int i = 1; i < N; i++)
    {
        if (i <= mxZ)
            z[i] = min(z[i - mxi], mxZ - i);
        while (i + z[i] >= mxZ && i + z[i] < N && s[i + z[i]] == s[z[i]])
        {
            z[i]++;
            mxZ = i + z[i], mxi = i;
        }
    }
    return z;
}

pair<int, pii> solve(string s, string t)
{
    int ans = 0, N = s.size(), M = t.size();
    pii sol;
    for (int i = 0; i <= N; i++)
    {
        string L, R;
        for (int j = i - 1; j >= 0; j--)
            L.push_back(s[j]);
        for (int j = M - 1; j >= 0; j--)
            L.push_back(t[j]);
        for (int j = i; j < N; j++)
            R.push_back(s[j]);
        for (int j = 0; j < M; j++)
            R.push_back(t[j]);
        vector<int> zL = Z(L), zR = Z(R);
        // cerr << t << '\n';
        // cerr << s.substr(0, i) << ' ' << s.substr(i) << '\n';
        vector<int> lL(M + 1), lR(M + 1);
        for (int j = i; j < i + M; j++)
        {
            int k = M - (j - i) - 1;
            zL[j] = min(zL[j], i);
            if(k - zL[j] + 1 < 0)
                lL[0] = max(lL[0], k + 1);
            else if(zL[j])
                lL[k - zL[j] + 1] = max(lL[k - zL[j] + 1], zL[j]);
        }
        for (int j = 1; j < M; j++)
            lL[j] = max(lL[j], lL[j - 1] - 1);

        for (int j = (N - i); j < (N - i) + M; j++)
        {
            int k = j - (N - i);
            zR[j] = min(zR[j], N - i);
            if(k + zR[j] - 1 > M)
                lR[M] = max(lR[M], M - k + 1);
            else if(zR[j])
                lR[k + zR[j] - 1] = max(lR[k + zR[j] - 1], zR[j]);
        }
        for (int j = M - 1; j >= 0; j--)
            lR[j] = max(lR[j], lR[j + 1] - 1);

        // for (int j = 0; j <= M; j++)
        //     cout << lL[j] << " \n"[j == M];
        // for (int j = 0; j <= M; j++)
        //     cout << lR[j] << " \n"[j == M];
        for (int j = 1; j <= M; j++)
            if(lL[j] + lR[j - 1] > ans)
                ans = lL[j] + lR[j - 1], sol = pii(i - lL[j], j - lR[j - 1]);
    }
    return make_pair(ans, sol);
}

signed main()
{
    // ios::sync_with_stdio(0), cin.tie(0);
    cin >> s >> t;
    pair<int, pii> ans1 = solve(s, t);
    reverse(t.begin(), t.end());
    pair<int, pii> ans2 = solve(s, t);
    ans2.S.S = t.size() - 1 - (ans2.S.S + ans2.F - 1);
    pair<int, pii> ans = max(ans1, ans2);

    cout << ans.F << '\n';
    cout << ans.S.F << " " << ans.S.S << '\n';
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	787 ms	392 KB	Output is correct
2	Correct	739 ms	460 KB	Output is correct
3	Correct	764 ms	380 KB	Output is correct
4	Correct	651 ms	380 KB	Output is correct
5	Correct	624 ms	384 KB	Output is correct
6	Correct	679 ms	392 KB	Output is correct
7	Correct	675 ms	388 KB	Output is correct
8	Correct	696 ms	392 KB	Output is correct
9	Correct	718 ms	388 KB	Output is correct