Submission #508795

#	Time	Username	Problem	Language	Result	Execution time	Memory
508795		dutch	Round words (IZhO13_rowords)	C++17	52 / 100	2102 ms	59676 KiB

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];
array<int, 2> _q[(int)1e7], *_l, *_r;

#define init() _r = _l = _q + (int)5e6

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;

	init();
	(*_r++) = {rt, d[rt][0] = 0};

	while(_l != _r) {
		auto [i, j] = (*_l++);
		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] || 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;

			(w ? *_r++ : *--_l) = {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: 52 / 100