답안 #508797

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
508797	2022-01-13T19:28:16 Z	dutch	원형 문자열 (IZhO13_rowords)	C++17	68 / 100	2000 ms	59632 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] || 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] || 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

68.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	460 KB	Output is correct
2	Correct	0 ms	460 KB	Output is correct
3	Correct	1 ms	588 KB	Output is correct
4	Correct	2 ms	1100 KB	Output is correct
5	Incorrect	1 ms	972 KB	Output isn't correct
6	Correct	154 ms	19040 KB	Output is correct
7	Correct	548 ms	43440 KB	Output is correct
8	Correct	897 ms	42776 KB	Output is correct
9	Correct	1333 ms	42748 KB	Output is correct
10	Correct	1567 ms	43052 KB	Output is correct
11	Correct	1856 ms	47456 KB	Output is correct
12	Correct	890 ms	52972 KB	Output is correct
13	Execution timed out	2079 ms	52380 KB	Time limit exceeded
14	Execution timed out	2058 ms	49136 KB	Time limit exceeded
15	Execution timed out	2066 ms	54872 KB	Time limit exceeded
16	Correct	1370 ms	46212 KB	Output is correct
17	Correct	1561 ms	46188 KB	Output is correct
18	Execution timed out	2085 ms	59632 KB	Time limit exceeded
19	Incorrect	1573 ms	43164 KB	Output isn't correct
20	Execution timed out	2041 ms	53184 KB	Time limit exceeded
21	Correct	599 ms	34416 KB	Output is correct
22	Correct	1033 ms	41640 KB	Output is correct
23	Correct	1417 ms	46480 KB	Output is correct
24	Incorrect	1480 ms	48976 KB	Output isn't correct
25	Correct	1927 ms	56852 KB	Output is correct