Submission #1203918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203918		jioung	Necklace (Subtask 4) (BOI19_necklace4)	C++20	0 / 15	194 ms	636 KiB

necklace

#include <bits/stdc++.h>
#include <tuple>
using namespace std;

#define int long long
#define fi first
#define se second
#define NAME ""
#define eb emplace_back
#define pii pair<int, int>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define REP(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define FORD(i, a, b, x) for (int i = (a), _b = (b); i <= _b; i += x)

const int MAX = 6005, BLOCK = sqrt(MAX) + 1, LOG = __lg(MAX) + 1, mod = 1e9 + 7;
const int INF = 1e18;
typedef long long ll;

namespace Solution
{
    string s, t;
    int p1[MAX], p2[MAX];
    void fill(string s, int *p)
    {
        FOR(i, 1, s.size() - 1)
        {
            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;
        }
    }
    void solve()
    {
        cin >> s >> t;
        function<tuple<int, int, int>(string, string, bool)> f = [&](string s, string t, bool rev)
        {
            int n = s.size(), m = t.size();
            tuple<int, int, int> res = {0, 0, 0};
            FOR(i, 0, n - 1)
            {
                string s1 = s.substr(0, i);
                reverse(s1.begin(), s1.end());
                string s2 = s.substr(i, n - i);
                string t1 = t, t2 = t;
                reverse(t1.begin(), t1.end());
                fill(s1 + '#' + t1, p1);
                fill(s2 + '#' + t2, p2);
                FOR(j, 0, m - 1)
                {
                    res = max(res, {p1[i + j] + p2[n + m - i - j], i - p1[i + j], rev ? m - j - p2[n + m - i - j] : j - p1[i + j]});
                }
            }
            return res;
        };
        tuple<int, int, int> res = f(s, t, false);
        reverse(t.begin(), t.end());
        res = max(res, f(t, s, true));
        cout << get<0>(res) << '\n'
             << get<1>(res) << ' ' << get<2>(res);
    }
}

signed main()
{
    if (fopen(NAME ".inp", "r"))
    {
        freopen(NAME ".inp", "r", stdin);
        freopen(NAME ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T--)
    {
        Solution::solve();
    }
    return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'int main()':
necklace.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(NAME ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen(NAME ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15