제출 #466046

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
466046		mithilshah23	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	330 ms	588 KiB

necklace

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define vi vector<int>
#define rep(i, n) for (int i = 0; i < n; i++)
#define w(t)  \
    int t;    \
    cin >> t; \
    while (t--)
#define ff first
#define ss second
#define in(azz, sz)                 \
    for (int ix = 0; ix < sz; ix++) \
        cin >> azz[ix];
#define in2d(azz, row, column) rep(i, row) rep(j, column) cin >> azz[i][j];
#define out2d(azz, row, column)                  \
    rep(i, row)                                  \
    {                                            \
        rep(j, column) cout << azz[i][j] << " "; \
        cout << "\n"                             \
    };
#define out(azz, sz)                \
    for (int ix = 0; ix < sz; ix++) \
    {                               \
        cout << azz[ix] << " ";     \
    }                               \
    cout << endl
#define mii map<int, int>
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define mod 1000000007
#define endl '\n'
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define ALL(a) a.begin(), a.end()
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define ps(x, y) fixed << setprecision(y) << x
#define mp make_pair
#define all(vx) vx.begin(), vx.end()
#define maxv(azz) max_element(all(azz)) - azz.begin() //return index of max element of vector;
#define minv(azz) min_element(all(azz)) - azz.begin() //return index of min element of vector;
#define maxa(azz) max_element(azz, azz + n) - azz     //return index of max element of array, n==size of array;
#define mina(azz) min_element(azz, azz + n) - azz     //return index of min element of array, n==size of array;
#define isort(azz) is_sorted(all(azz))                //check if elements are sorted;
#define setpres cout.precision(numeric_limits<double>::max_digits10);
#define rev(vx) reverse(all(vx))
#define fastio                    \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef set<int> seti;
#define am(a, b) MOD(MOD(a) + MOD(b))
#define mm(a, b) MOD(MOD(a) * MOD(b))
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
const ll INF = 1000000007;
ll MOD(ll a)
{
    a = a % INF;
    while (a < 0)
        a += INF;
    return a;
}

ll binpow(ll a, ll b)
{
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = mm(res, a);
        a = mm(a, a);
        b >>= 1;
    }
    return res;
}
ll modInverse(ll a)
{
    return binpow(a, INF - 2);
}
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                                DON'T MAKE CHANGES BEFORE THIS LINE!
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
#define int ll //use only if needed;
vector<int> prefix_function(string s)
{
    int n = (int)s.length();
    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;
}
/*
$A$ is a suffix of $S[0 : i]$ and a prefix of $T[j + 1 : M - 1]$.

$B$ is a prefix of $S[i + 1 : N - 1]$ and a suffix of $T[0 : j]$.

$|A| + |B|$ is maximal.
*/
void tosolve()
{
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size(), ans = 0, l, r;
    rep(i, n)
    {
        string s1 = s.substr(0, i), s2 = s.substr(i, n - i);
        reverse(s1.begin(), s1.end());
        string t1 = t, t2 = t;
        reverse(t2.begin(), t2.end());
        vi temp1 = prefix_function(s1 + "#" + t1);
        vi temp2 = prefix_function(s2 + "#" + t2);
        for (int j = 0; j < m; j++)
        {
            if (ans <= temp1[i + j] + temp2[n + m - i - j])
            {
                ans = max(ans, temp1[i + j] + temp2[n + m - i - j]);
                l = i - temp1[i + j];
                r = j - temp1[i + j];
            }
        }
    }
    reverse(t.begin(), t.end());
    rep(i, n)
    {
        string s1 = s.substr(0, i), s2 = s.substr(i, n - i);
        reverse(s1.begin(), s1.end());
        string t1 = t, t2 = t;
        reverse(t2.begin(), t2.end());
        vi temp1 = prefix_function(s1 + "#" + t1);
        vi temp2 = prefix_function(s2 + "#" + t2);
        for (int j = 0; j < m; j++)
        {
            if (ans <= temp1[i + j] + temp2[n + m - i - j])
            {
                ans = max(ans, temp1[i + j] + temp2[n + m - i - j]);
                l = i - temp1[i + j];
                r = m - j - temp2[n + m - i - j];
            }
        }
    }
    cout << ans << endl;
    cout << l << " " << r << endl;
    return;
}

int32_t main()
{
    fastio
    {
        tosolve();
    }
    return 0;
}
/*

███╗░░░███╗██╗████████╗██╗░░██╗██╗██╗░░░░░
████╗░████║██║╚══██╔══╝██║░░██║██║██║░░░░░
██╔████╔██║██║░░░██║░░░███████║██║██║░░░░░
██║╚██╔╝██║██║░░░██║░░░██╔══██║██║██║░░░░░
██║░╚═╝░██║██║░░░██║░░░██║░░██║██║███████╗
╚═╝░░░░░╚═╝╚═╝░░░╚═╝░░░╚═╝░░╚═╝╚═╝╚══════╝

 *  Author : mithilshah23
 *  Website : Oj
 *  Problem : necklace
 *  Time : 17-08-2021 20:49:52
 *  Lang : GNU C++17
 */

• Subtask 1: 15 / 15