답안 #508795

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

#define init() _r = _l = _q + (int)5e6

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;

	init();
	(*_r++) = {rt, d[rt][0] = 0};

	while(_l != _r) {
		auto [i, j] = (*_l++);
		for(int di : {0, 1}) for(int dj : {0, 1}) {
			int x = i + di, y = j + dj, w = di ^ dj;
			if(y == M || x > hi[y] || d[x][y] <= d[i][j] + w) continue;
			if(di && dj && S[i % N] != T[j]) continue;

			d[x][y] = d[i][j] + w;
			p[x][y] = di + 2 * dj;

			(w ? *_r++ : *--_l) = {x, y};
		}
	}

	int mMin[M], mMax[M] = {};
	fill(mMin, mMin+M, N+N);

	int i = rt+N-1, j = M-1;

	assert(lo[M-1] <= i && i <= hi[M-1]);
	ans = max(ans, N-1 + M-1 - 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);

	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 / 2;
}

Subtask #1

52.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 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	3 ms	972 KB	Output isn't correct
6	Correct	212 ms	19028 KB	Output is correct
7	Correct	709 ms	43436 KB	Output is correct
8	Correct	1308 ms	42660 KB	Output is correct
9	Correct	1881 ms	42744 KB	Output is correct
10	Execution timed out	2037 ms	43068 KB	Time limit exceeded
11	Execution timed out	2091 ms	47440 KB	Time limit exceeded
12	Correct	1258 ms	53048 KB	Output is correct
13	Execution timed out	2101 ms	52236 KB	Time limit exceeded
14	Execution timed out	2082 ms	49136 KB	Time limit exceeded
15	Execution timed out	2102 ms	54724 KB	Time limit exceeded
16	Correct	1901 ms	46344 KB	Output is correct
17	Execution timed out	2081 ms	46160 KB	Time limit exceeded
18	Execution timed out	2077 ms	59676 KB	Time limit exceeded
19	Execution timed out	2083 ms	43064 KB	Time limit exceeded
20	Execution timed out	2087 ms	53176 KB	Time limit exceeded
21	Correct	829 ms	34344 KB	Output is correct
22	Correct	1431 ms	41760 KB	Output is correct
23	Correct	1858 ms	46412 KB	Output is correct
24	Execution timed out	2028 ms	49092 KB	Time limit exceeded
25	Execution timed out	2080 ms	56840 KB	Time limit exceeded