Submission #475817

#	Time	Username	Problem	Language	Result	Execution time	Memory
475817		utr491	Necklace (Subtask 4) (BOI19_necklace4)	C++14	0 / 15	302 ms	588 KiB

necklace

#include "bits/stdc++.h"
using namespace std;

#define ll long long int
#define pb(a) push_back(a)
#define vll vector<ll>
#define loop(i, n) for (ll i = 1; i <= n; i++)
#define loop0(i, n) for (ll i = 0; i < n; i++)
#define in(i) cin>>i
#define out(i) printf("%lld", i)
#define pll pair<ll, ll>
#define vpll vector<pair<ll, ll>>
#define mp(i, j) make_pair(i, j)
#define google cout << "Case #" << tc - t << ": ";
const ll mod = 1000000007;
const ll big = 2999999999999999999;
const ll small = -2999999999999999999;
void in2(ll &a, ll &b) { cin >> a >> b; }
void in3(ll &a, ll &b, ll &c) {cin >> a >> b >> c; }
void arrayIn(vll &a, ll &n) { loop0(i, n) in(a[i]); }

string s, t;
vll pi1, pi2;

void prefix(string s, vll& pi)
{
  ll n = s.size();
  pi.resize(n);
  pi[0] = 0;
  loop(i, n-1)
  {
    ll j = pi[i-1];
    while(j && s[i] != s[j]) j = pi[j-1];
    if(s[i] == s[j]) j += 1;
    pi[i] = j;
  }
}

tuple<ll, ll, ll> solve(string s, string t, bool rev)
{
  ll n = s.size();
  ll m = t.size();
  tuple<ll, ll, ll> ans = {0, 0, 0};
  loop0(i, n)
  {
    string s1 = s.substr(0, i), s2 = s.substr(i, n-i);
    reverse(s1.begin(), s1.end());
    string t1 = t, t2 = t;
    // suffix of s1 that is prefix of t1 for a given j...
    reverse(t1.begin(), t1.end());
    prefix(s1 + '#' + t1, pi1);
    prefix(s2 + '#' + t2, pi2);
    loop(j, m)
    {
      ans = max(ans,
      {
        pi1[i+j] + pi2[n+m-i-j],
        i-pi1[i+j],
        !rev ? j - pi2[n+m-i-j] : pi1[i+j]
      });
    }
  }
  return ans;
}

void solve()
{
  cin >> s >> t;
  tuple<ll, ll, ll> ans = solve(s, t, false);
  reverse(t.begin(), t.end());
  ans = max(solve(s, t, true), ans);
  cout<<get<0>(ans)<<"\n"<<get<1>(ans)<<" "<<get<2>(ans)<<"\n";
}

int main()
{
  solve();
}

• Subtask 1: 0 / 15