Submission #1162357

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

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

• Subtask 1: 0 / 15