답안 #508801

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
508801	2022-01-13T19:38:29 Z	dutch	원형 문자열 (IZhO13_rowords)	C++17	80 / 100	1145 ms	59700 KB

rowords

#include <bits/stdc++.h>
using namespace std;
 
const int Z = 2000, INF = 1e8;
 
string S, T;
int N, M, ans, d[Z*2][Z], p[Z*2][Z];
array<int, 2> _q[(int)1e7], *_l, *_r;
 
void dfs(int loR, int hiR, int *lo, int *hi) {
	if(loR > hiR) return;
 
	for(int j = 0; j < M; j++)
		for(int i = lo[j]; i <= hi[j]; i++) 
			d[i][j] = INF;
 
	int rt = (loR + hiR) / 2;
 
	 _r = _l = _q + (int)5e6;
	(*_r++) = {rt, d[rt][0] = 0};
 
	while(_l != _r) {
		auto [i, j] = (*_l++);
		for(int di : {0, 1}) {
			int x = i + di, y = j + !di;
			if(y == M || x > hi[y] || x < lo[y] || d[x][y] <= d[i][j] + 1) continue;
			d[x][y] = d[i][j] + 1;
			p[x][y] = di ? 1 : 2;
			*_r++ = {x, y};
		}
		int x = i + 1, y = j + 1;
		if(y == M || x > hi[y] || x < lo[y] || d[x][y] <= d[i][j] || S[i] != T[j]) continue;
		d[x][y] = d[i][j];
		p[x][y] = 3;
		*--_l = {x, y};
	}
 
	int mMin[M], mMax[M] = {};
	fill(mMin, mMin+M, N+N);
 
	int i = rt+N-1, j = M-1;
 
	assert((N + M - d[i][j] + 1) & 1);
	assert(d[i][j] != INF);
 
	ans = max(ans, (N + M - d[i][j]) / 2 - (S[i%N] != T[j]));
 
	while(1) {
		mMin[j] = min(mMin[j], i);
		mMax[j] = max(mMax[j], i);
		if(i == rt && !j) break;
		int k = p[i][j];
		if(k & 1) --i;
		if(k & 2) --j;
	}
 
	dfs(loR, rt - 1, lo, mMax);
	dfs(rt + 1, hiR, mMin, hi);
}
 
int main() {
	cin >> S >> T;
	N = size(S);
	M = size(T);
	S += S;
 
	for(int _ : {0, 1}) {
		if(_) reverse(begin(S), end(S));
		int lo[M] = {}, hi[M];
		fill(hi, hi + M, 2 * N - 1);
 
		dfs(0, N-1, lo, hi);
	}
	cout << ans;
}

Subtask #1

80.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	460 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	1 ms	640 KB	Output is correct
4	Correct	2 ms	1100 KB	Output is correct
5	Incorrect	2 ms	972 KB	Output isn't correct
6	Correct	142 ms	19032 KB	Output is correct
7	Correct	693 ms	43440 KB	Output is correct
8	Correct	879 ms	42780 KB	Output is correct
9	Correct	924 ms	42748 KB	Output is correct
10	Correct	949 ms	42936 KB	Output is correct
11	Correct	1115 ms	47448 KB	Output is correct
12	Correct	1145 ms	53048 KB	Output is correct
13	Correct	1119 ms	52316 KB	Output is correct
14	Incorrect	959 ms	49148 KB	Output isn't correct
15	Correct	1132 ms	54796 KB	Output is correct
16	Correct	966 ms	46288 KB	Output is correct
17	Correct	771 ms	46316 KB	Output is correct
18	Incorrect	1120 ms	59700 KB	Output isn't correct
19	Incorrect	759 ms	43188 KB	Output isn't correct
20	Correct	1039 ms	53180 KB	Output is correct
21	Correct	359 ms	34500 KB	Output is correct
22	Correct	539 ms	41636 KB	Output is correct
23	Correct	697 ms	46480 KB	Output is correct
24	Incorrect	742 ms	48936 KB	Output isn't correct
25	Correct	960 ms	56812 KB	Output is correct