Submission #1072154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072154		Tam_theguide	Necklace (Subtask 4) (BOI19_necklace4)	C++14	15 / 15	228 ms	592 KiB

necklace

#include <bits/stdc++.h>
using namespace std;
using Answer = tuple<int, int, int>;

const int MAXN = 3000;

string s, t;

int pi1[2 * MAXN + 5], pi2[2 * MAXN + 5];

Answer Res = {0, 0, 0};

void Calc(string st, int *pi) {
    pi[0] = 0;

    for (int i = 1; i < (int)st.size(); i++) {
        int cur = pi[i - 1];

        while (st[i] != st[cur] && cur > 0)
            cur = pi[cur - 1];

        if (st[i] == st[cur]) cur++;
        pi[i] = cur;
    }
}

void Solve(bool Rev) {
    int n = (int)s.size();
    int m = (int)t.size();

    for (int i = 0; i < n; i++) {
        // Split : [0, i - 1](reverse) + [i, |s| - 1]

        string s1 = s.substr(0, i);
        string s2 = s.substr(i, n - i);
        
        reverse(s1.begin(), s1.end());
        Calc(s1 + '#' + t, pi1);
        
        reverse(t.begin(), t.end());
        Calc(s2 + '#' + t, pi2);
        reverse(t.begin(), t.end());

        for (int j = 1; j <= m; j++)
		    Res = max(Res, {pi1[i + j] + pi2[n + m - i - j], i - pi1[i + j],
			          Rev ? m - j - pi2[n + m - i - j] : j - pi1[i + j]});
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> s >> t;

    Solve(false);
    reverse(t.begin(), t.end());
    Solve(true);

    int l, u, v;
    tie(l, u, v) = Res;

    cout << l << "\n" << u << " " << v;
}

• Subtask 1: 15 / 15