oj.uz

Submission #508809

# Submission time Handle Problem Language Result Execution time Memory
508809 2022-01-13T20:01:32 Z dutch Round words (IZhO13_rowords) C++17
80 / 100
 1601 ms 59708 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;
	lo[0] = rt, hi[0] = rt + N - 1;

 	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 1 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 2 ms 972 KB Output isn't correct
6 Correct 168 ms 19016 KB Output is correct
7 Correct 750 ms 43444 KB Output is correct
8 Correct 969 ms 42880 KB Output is correct
9 Correct 1105 ms 42752 KB Output is correct
10 Correct 1045 ms 43060 KB Output is correct
11 Correct 1259 ms 47452 KB Output is correct
12 Correct 1273 ms 53044 KB Output is correct
13 Correct 1585 ms 52312 KB Output is correct
14 Incorrect 1357 ms 49136 KB Output isn't correct
15 Correct 1531 ms 54852 KB Output is correct
16 Correct 1258 ms 46248 KB Output is correct
17 Correct 1050 ms 46156 KB Output is correct
18 Incorrect 1601 ms 59708 KB Output isn't correct
19 Incorrect 1078 ms 43284 KB Output isn't correct
20 Correct 1400 ms 53228 KB Output is correct
21 Correct 512 ms 34388 KB Output is correct
22 Correct 823 ms 41752 KB Output is correct
23 Correct 995 ms 46400 KB Output is correct
24 Incorrect 1129 ms 48980 KB Output isn't correct
25 Correct 1425 ms 56844 KB Output is correct