Submission #1162328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162328		estebanolmedo	Necklace (Subtask 4) (BOI19_necklace4)	C++20	0 / 15	1585 ms	320 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 s) {
        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;
}

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};
        for(int i = 0; i < N; ++i) {
                for(int j = 0; j < M; ++j) {
                        string pref_s = s.substr(0, i);
                        string suf_s = s.substr(i, N - i);

                        string pref_t = t.substr(0, j);
                        string suf_t = t.substr(j, M - j);

                        vi a = preffix_function(suf_t + "$" + pref_s);
                        vi b = preffix_function(suf_s + "$" + pref_t);

                        tuple<int,int,int> curr = {a.back() + b.back(), i - a.back(), rev ? j + b.back() - 1 : j - b.back()};
                        ans = max(ans, curr);
                }
        }
        if(rev) get<2>(ans) = M - get<2>(ans) - 1;
        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 << endl;
        cout << i << ' ' << j << endl;
}

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

• Subtask 1: 0 / 15