oj.uz

Submission #508797

# Submission time Handle Problem Language Result Execution time Memory
508797 2022-01-13T19:28:16 Z dutch Round words (IZhO13_rowords) C++17
68 / 100
 2000 ms 59632 KB 
#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

# Verdict Execution time Memory 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