oj.uz

Submission #508801

# Submission time Handle Problem Language Result Execution time Memory
508801 2022-01-13T19:38:29 Z dutch Round words (IZhO13_rowords) C++17
80 / 100
 1145 ms 59700 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] || 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

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