oj.uz

Submission #542793

# Submission time Handle Problem Language Result Execution time Memory
542793 2022-03-28T05:38:31 Z skittles1412 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 373 ms 106272 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 2132 KB Output is correct
7 Correct 7 ms 2132 KB Output is correct
8 Correct 6 ms 1872 KB Output is correct
9 Correct 7 ms 2072 KB Output is correct
10 Correct 7 ms 2152 KB Output is correct
11 Correct 7 ms 2160 KB Output is correct
12 Correct 6 ms 2004 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 2132 KB Output is correct
7 Correct 7 ms 2132 KB Output is correct
8 Correct 6 ms 1872 KB Output is correct
9 Correct 7 ms 2072 KB Output is correct
10 Correct 7 ms 2152 KB Output is correct
11 Correct 7 ms 2160 KB Output is correct
12 Correct 6 ms 2004 KB Output is correct
13 Correct 370 ms 106272 KB Output is correct
14 Correct 357 ms 106272 KB Output is correct
15 Correct 362 ms 100092 KB Output is correct
16 Correct 336 ms 104464 KB Output is correct
17 Correct 359 ms 102568 KB Output is correct
18 Correct 350 ms 105560 KB Output is correct
19 Correct 373 ms 105240 KB Output is correct
20 Correct 342 ms 102240 KB Output is correct
21 Correct 363 ms 103472 KB Output is correct