답안 #508803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
508803	2022-01-13T19:39:31 Z	dutch	원형 문자열 (IZhO13_rowords)	C++17	80 / 100	1985 ms	46456 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];
 
void dfs(int loR, int hiR, const int *lo, const int *hi) {
	if(loR > hiR) return;
 
	for(int j = 0; j < M; j++) {
		assert(lo[j] <= hi[j]);
		for(int i = lo[j]; i <= hi[j]; i++) 
			d[i][j] = INF;
	}
 
	int rt = (loR + hiR) / 2;
	deque<array<int, 2>> q;
	q.push_back({rt, d[rt][0] = 0});
 
	while(!empty(q)) {
		auto [i, j] = q.front();
		q.pop_front();
		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] || x < lo[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;
			if(w) q.push_back({x, y});
			else q.push_front({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

80.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	332 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	972 KB	Output is correct
5	Incorrect	2 ms	972 KB	Output isn't correct
6	Correct	192 ms	17848 KB	Output is correct
7	Correct	1010 ms	31692 KB	Output is correct
8	Correct	1228 ms	31712 KB	Output is correct
9	Correct	1372 ms	31748 KB	Output is correct
10	Correct	1431 ms	31816 KB	Output is correct
11	Correct	1573 ms	34836 KB	Output is correct
12	Correct	1643 ms	38072 KB	Output is correct
13	Correct	1906 ms	38068 KB	Output is correct
14	Incorrect	1683 ms	36312 KB	Output isn't correct
15	Correct	1985 ms	39220 KB	Output is correct
16	Correct	1552 ms	34164 KB	Output is correct
17	Correct	1309 ms	36328 KB	Output is correct
18	Incorrect	1982 ms	44732 KB	Output isn't correct
19	Incorrect	1330 ms	31712 KB	Output isn't correct
20	Correct	1733 ms	39980 KB	Output is correct
21	Correct	589 ms	31432 KB	Output is correct
22	Correct	886 ms	35972 KB	Output is correct
23	Correct	1151 ms	38604 KB	Output is correct
24	Incorrect	1251 ms	40824 KB	Output isn't correct
25	Correct	1637 ms	46456 KB	Output is correct