oj.uz

Submission #133148

# Submission time Handle Problem Language Result Execution time Memory
133148 2019-07-20T07:59:29 Z E869120 Necklace (Subtask 4) (BOI19_necklace4) C++14
15 / 15
 512 ms 1972 KB 
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;

const int BACKET = 55;

int N, M, pa_long[60][3009], pa_short[60][3009];
int EA[6009], EB[6009];
int prevs[6009], dp[6009];

tuple<int, int, int> solve(string S, string T) {
	N = S.size(); M = T.size();
	for (int i = 0; i < M; i++) prevs[i] = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			dp[j] = 0;
			if (S[i] == T[j]) dp[j] = 1;
			if (i >= 1 && j >= 1 && S[i] == T[j]) {
				dp[j] = prevs[j - 1] + 1;
			}
		}
		for (int j = 0; j < M; j++) prevs[j] = dp[j];
		if (i % BACKET == 0) {
			for (int j = 0; j < M; j++) pa_long[i / BACKET][j] = prevs[j];
		}
	}

	int maxn = 0; pair<int, int> maxid = make_pair(-1, -1);
	for (int i = 0; i <= M; i++) prevs[i] = 0;

	for (int i = N; i >= 0; i--) {
		// Step 1 : 更新処理 (pa)
		if (i == N || (i - 1) % BACKET == BACKET - 1) {
			int c = ((i - 1) / BACKET) * BACKET;
			for (int j = 0; j < M; j++) pa_short[0][j] = pa_long[c / BACKET][j];

			for (int j = 1; j < BACKET; j++) {
				if (c + j >= N) break;
				for (int k = 0; k < M; k++) {
					pa_short[j][k] = 0;
					if (S[c + j] == T[k]) pa_short[j][k] = 1;
					if (c + j >= 1 && k >= 1 && S[c + j] == T[k]) {
						pa_short[j][k] = pa_short[j - 1][k - 1] + 1;
					}
				}
			}
		}

		// Step 2 : 更新処理 (pb)
		if (i < N) {
			for (int j = 0; j < M; j++) {
				dp[j] = 0;
				if (S[i] == T[j]) dp[j] = 1;
				if (i < N - 1 && j < M - 1 && S[i] == T[j]) {
					dp[j] = prevs[j + 1] + 1;
				}
			}
			for (int j = 0; j < M; j++) { prevs[j] = dp[j]; }
		}

		// Step 2 : S における境界が i の場合の計算
		vector<int> A, B;
		for (int j = 0; j < M; j++) {
			if (i == N) A.push_back(0);
			else A.push_back(prevs[j]);
		}
		for (int j = 0; j < M; j++) {
			if (i == 0) B.push_back(0);
			else B.push_back(pa_short[(i - 1) % BACKET][j]);
		}
		for (int j = 0; j <= 6000; j++) { EA[j] = (1 << 29); EB[j] = -(1 << 29); }
		for (int j = 0; j < N; j++) {
			EA[A[j] + j] = min(EA[A[j] + j], j);
			EB[max(0, -B[j] + j + 1)] = max(EB[max(0, -B[j] + j + 1)], j);
		}
		
		// ret1 には条件を満たす最も左のインデックスを記録
		int ret1 = -(1 << 29);
		for (int j = 0; j <= 6000; j++) {
			ret1 = max(ret1, EB[j]);
			int cr = ret1, cl = EA[j];
			if (maxn < cr - cl + 1) {
				maxn = cr - cl + 1;
				maxid = make_pair(i - B[cr], cl);
			}
		}
	}
	return make_tuple(maxn, maxid.first, maxid.second);
}

int main() {
	string A1, B1, B2; cin >> A1 >> B1; B2 = B1; reverse(B2.begin(), B2.end());
	tuple<int, int, int> v1 = solve(A1, B1);
	tuple<int, int, int> v2 = solve(A1, B2);

	cout << max(get<0>(v1), get<0>(v2)) << endl;
	if (get<0>(v1) > get<0>(v2)) cout << get<1>(v1) << " " << get<2>(v1) << endl;
	if (get<0>(v1) <= get<0>(v2)) cout << get<1>(v2) << " " << M - (get<2>(v2) + get<0>(v2)) << endl;
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 1884 KB Output is correct
2 Correct 491 ms 1912 KB Output is correct
3 Correct 512 ms 1812 KB Output is correct
4 Correct 458 ms 1784 KB Output is correct
5 Correct 451 ms 1916 KB Output is correct
6 Correct 487 ms 1972 KB Output is correct
7 Correct 478 ms 1872 KB Output is correct
8 Correct 470 ms 1784 KB Output is correct
9 Correct 480 ms 1916 KB Output is correct