oj.uz

Submission #508808

# Submission time Handle Problem Language Result Execution time Memory
508808 2022-01-13T19:56:10 Z dutch Round words (IZhO13_rowords) C++17
80 / 100
 1461 ms 59712 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[4*Z*Z], *qL, *qR;
 
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;

 	qR = qL = _q + 2*Z*Z;
	(*qR++) = {rt, d[rt][0] = 0};
 
	while(qL != qR) {
		auto [i, j] = (*qL++);
		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] != T[j]) continue;
 
			d[x][y] = d[i][j] + w;
			p[x][y] = di + 2 * dj;
 
			(w ? *qR++ : *--qL) = {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);
	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 / 2;
}

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory 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 1 ms 972 KB Output isn't correct
6 Correct 136 ms 19020 KB Output is correct
7 Correct 700 ms 43448 KB Output is correct
8 Correct 927 ms 42780 KB Output is correct
9 Correct 1044 ms 42752 KB Output is correct
10 Correct 1014 ms 43088 KB Output is correct
11 Correct 1126 ms 47500 KB Output is correct
12 Correct 1251 ms 53056 KB Output is correct
13 Correct 1401 ms 52312 KB Output is correct
14 Incorrect 1225 ms 49132 KB Output isn't correct
15 Correct 1449 ms 54928 KB Output is correct
16 Correct 1150 ms 46340 KB Output is correct
17 Correct 959 ms 46204 KB Output is correct
18 Incorrect 1461 ms 59712 KB Output isn't correct
19 Incorrect 972 ms 43156 KB Output isn't correct
20 Correct 1311 ms 53216 KB Output is correct
21 Correct 430 ms 34372 KB Output is correct
22 Correct 661 ms 41640 KB Output is correct
23 Correct 855 ms 46424 KB Output is correct
24 Incorrect 973 ms 48984 KB Output isn't correct
25 Correct 1203 ms 56852 KB Output is correct