Submission #668682

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
668682	2022-12-04T12:55:19 Z	gokussjz	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	299 ms	468 KB

necklace

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define all(x)      x.begin(), x.end()
#define pb          push_back
#define sz(x)       (int)(x.size())
#define ll          long long
#define fi          first
#define se          second
#define lbd         lower_bound
#define ubd         upper_bound

template <typename T>
using ordered_set = tree<T, null_type,
      less<T>, rb_tree_tag,
      tree_order_statistics_node_update>;

const int MOD = 1e9 + 7;
const double eps = 1e-10;
const long long INF = 1e18;
const int N = 2e5 + 10;

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 && s[i] != s[j]) j = pi[j - 1];
		if (s[i] == s[j]) j++;
		pi[i] = j;
	}
	return pi;
}

void solve() {
	string s, t;
	cin >> s >> t;
	int n = sz(s), m = sz(t);
	int ans = 0;
	pair<int, int> pos;
	for (int i = 0; i < n; i++) {
		string s1 = s.substr(0, i);
		string s2 = s.substr(i, n - i);
		reverse(all(s1));
		string t1 = t;
		reverse(all(t1));
		vector<int> p1 = prefix_function(s1 + '#' + t);
		vector<int> p2 = prefix_function(s2 + '#' + t1);

		for (int j = 1; j <= m; j++) {
			int curr = p1[i + j] + p2[n + m - i - j];
			if (ans < curr) {
				ans = curr;
				pos = {i - p1[i + j], j - p1[i + j]};
			}
		}
	}

	reverse(all(t));
	for (int i = 0; i < n; i++) {
		string s1 = s.substr(0, i);
		string s2 = s.substr(i, n - i);
		reverse(all(s1));
		string t1 = t;
		reverse(all(t1));
		vector<int> p1 = prefix_function(s1 + '#' + t);
		vector<int> p2 = prefix_function(s2 + '#' + t1);

		for (int j = 1; j <= m; j++) {
			int curr = p1[i + j] + p2[n + m - i - j];
			if (ans < curr) {
				ans = curr;
				pos = {i - p1[i + j], m - j - p2[n + m - i - j]};
			}
		}
	}
	cout << ans << '\n' << pos.fi << ' ' << pos.se;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int tt = 1;
	//cin >> tt;
	while (tt--) {
		solve();
		cout << '\n';
	}
	return 0;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	257 ms	424 KB	Output is correct
2	Correct	220 ms	448 KB	Output is correct
3	Correct	299 ms	340 KB	Output is correct
4	Correct	230 ms	428 KB	Output is correct
5	Correct	126 ms	444 KB	Output is correct
6	Correct	127 ms	340 KB	Output is correct
7	Correct	179 ms	444 KB	Output is correct
8	Correct	214 ms	464 KB	Output is correct
9	Correct	231 ms	468 KB	Output is correct