Submission #542793

#	Time	Username	Problem	Language	Result	Execution time	Memory
542793		skittles1412	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	85 / 85	373 ms	106272 KiB

necklace

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

struct Solver {
	int n, m, i;
	string s, t;
	vector<int> g, ans;

	Solver(const string& s, const string& t)
		: n(sz(s)), m(sz(t)), i(n - 1), s(s), t(t), g(m + 1), ans(m + 1) {}

	void adv() {
		if (i < 0) {
			return;
		}
		for (int j = 0; j < m; j++) {
			if (s[i] == t[j]) {
				g[j] = g[j + 1] + 1;
			}
		}
		int opt[m + 1];
		memset(opt, 0x3f, sizeof(opt));
		for (int j = 0; j < m; j++) {
			int& o = opt[g[j] + j];
			o = min(o, j);
		}
		int o = 1e9;
		for (int j = m - 1; j >= 0; j--) {
			o = min(o, opt[j + 1]);
			ans[j] = max(0, j - o + 1);
		}
		i--;
	}
};

string reversed(string s) {
	reverse(begin(s), end(s));
	return s;
}

vector<vector<int>> comp(string s, string t) {
	int n = sz(s), m = sz(t);
	int g[n + 1][m + 1] {};
	for (int i = n - 1; i >= 0; i--) {
		for (int j = m - 1; j >= 0; j--) {
			if (s[i] == t[j]) {
				g[i][j] = g[i + 1][j + 1] + 1;
			}
		}
	}
	vector<vector<int>> ans(n, vector<int>(m));
	for (int i = 0; i < n; i++) {
		int opt[m + 1];
		memset(opt, 0x3f, sizeof(opt));
		for (int j = 0; j < m; j++) {
			int& o = opt[g[i][j] + j];
			o = min(o, j);
		}
		int o = 1e9;
		for (int j = m - 1; j >= 0; j--) {
			o = min(o, opt[j + 1]);
			ans[i][j] = max(0, j - o + 1);
		}
	}
	return ans;
}

tuple<int, int, int> solve(string s, string t) {
	int n = sz(s), m = sz(t);
	auto ca = comp(s, t), cb = comp(reversed(s), reversed(t));
	tuple<int, int, int> ans {};
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int p1 = ca[i][j], p2 = ((i && m - j - 2 >= 0) ? cb[n - i][m - j - 2] : 0);
			ans = max(ans, tuple<int, int, int> {p1 + p2, i - p2, j - p1 + 1});
		}
	}
	return ans;
}

void solve() {
	string s, t;
	cin >> s >> t;
	auto [x, a, b] = solve(s, t);
	reverse(begin(s), end(s));
	auto [x1, a1, b1] = solve(s, t);
	dbg(x, a, b, x1, a1, b1);
	if (x1 > x) {
		x = x1;
		a = sz(s) - a1 - x;
		b = b1;
	}
	cout << x << endl;
	cout << a << " " << b << endl;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40