Submission #1161313

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161313		ezzatw122	Necklace (Subtask 4) (BOI19_necklace4)	C++20	0 / 15	1 ms	320 KiB

necklace

#include <bits/stdc++.h>


// you just try again
using namespace std;
#define ll long long

void read() {
# ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
}


const int N = 400 + 5, M = 2;

vector<int> prefix_function(string s) {
    int n = s.size();
    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];
        j += (s[i] == s[j]);
        pi[i] = j;
    }
    return pi;
}

array<int, 3> solve(string a, string b, bool rev) {
    int n = a.size(), m = b.size();
    array<int, 3> ans = {0, 0, 0};
    for (int i = 0; i < n; ++i) {
        string f = a.substr(0, i);
        string s = a.substr(i, n - i);
        std::reverse(f.begin(), f.end());
        std::reverse(b.begin(), b.end());
        auto pi1 = prefix_function(f + '#' + b);
        std::reverse(b.begin(), b.end());
        auto pi2 = prefix_function(s + '#' + b);
        for (int j = 1; j <= m; ++j) {
            ans = max(ans, {pi2[n - i + j] + pi1[i + m - j], i - pi1[i + m - j],
                            !rev ? j - pi2[n - i + j] : m - j - pi1[i + m - j]});
        }
    }
    return ans;
}

void code() {
    string a, b;
    cin >> a >> b;
    auto ans = solve(a, b, 0);
    std::reverse(b.begin(), b.end());
    ans = max(ans, solve(a, b, 1));
    cout << ans[0] << '\n' << ans[1] << " " << ans[2];

}


int main() {

    read();
    int t = 1;
    // cin >> t;
    while (t--)code();
}

Compilation message (stderr)

necklace.cpp: In function 'void read()':
necklace.cpp:10:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:11:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15