제출 #1162363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162363		estebanolmedo	Necklace (Subtask 4) (BOI19_necklace4)	C++20	15 / 15	261 ms	576 KiB

necklace

#include<bits/stdc++.h>
#define lli long long int
#define ld long double
#define forn(i,n) for(int i = 0; i < n; i++)
#define forr(i,a,n) for(int i = a; i <= n; i++)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(),v.end()
#define SZ(v) (int)v.size()
#define endl '\n'
#define fastIO() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<lli> vlli;

vi preffix_function(const string patt) {
        // vi pi(SZ(s));
        // for(int i = 1, j = 0; i < SZ(s); i++) {
        //         while(j > 0 && s[i] != s[j]) j = pi[j-1];
        //         if(s[i] == s[j]) j++;
        //         pi[i] = j;
        // }
        // return pi;
        //
  int len = patt.size();
  vi lps(len, 0);
  int j = 0;
  for(int i = 1; i < len; i++) {
    j = lps[i-1];
    while(j > 0 && patt[j] != patt[i]) j = lps[j-1];
    lps[i] = j + (patt[i] == patt[j]);
  }
  return lps;
}


tuple<int,int,int> get_ans(const string& s, const string& t, bool rev) {
        int N = SZ(s);
        int M = SZ(t);
        tuple<int,int,int> ans = {0,0,0};
        string rev_t = t;
        reverse(all(rev_t));
        for(int i = 0; i < N; ++i) {
                string pref_s = s.substr(0, i);
                string suf_s = s.substr(i, N - i);
                reverse(all(pref_s));

                vi a = preffix_function(pref_s + "$" + t);
                vi b = preffix_function(suf_s + "$" + rev_t);

                for(int j = 1; j <= M; j++) {
                        tuple<int,int,int> curr = {
                                a[i + j] + b[N + M - i - j],
                                i - a[i + j],
                                rev ? M - j - b[N + M - i - j] : j - a[i + j],
                        };
                        ans = max(ans, curr);
                }
        }
        return ans;
}

void solve() {
        string s, t;
        cin >> s >> t;
        auto ans = get_ans(s, t, 0);
        reverse(all(t));
        ans = max(ans, get_ans(s, t, 1));
        auto[sz, i, j] = ans;
        cout << sz << '\n' << i << ' ' << j << endl;
}

int main() {
  fastIO();
  solve();
  return 0;
}

• Subtask 1: 15 / 15