Submission #3425313

---

Source Code Expand

#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "vector"
#include "string"
#include "map"
#include "algorithm"
#include "functional"
#include "set"
#include "numeric"

using namespace std;

const long long int MOD = 1000000007;

int N, M, K, H, W, L, R;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	string s, t;
	cin >> s >> t;
	bool a = false, b = false;
	for (auto i : s)if (i == '1')a = true;
	for (auto i : t)if (i == '1')b = true;
	if (!a && !b) {
		cout << 0 << endl;
		return 0;
	}
	if (!b) {
		cout << -1 << endl;
		return 0;
	}
	N = s.size();
	vector<int>l(N, MOD);
	vector<int>r(N, MOD);
	L = 0;
	R = -1;
	for (int i = 0; i < N; i++) {
		if (t[i] == '1') {
			if (R == -1)R = i;
			for (int j = L; j <= i; j++) {
				r[j] = i - j;
			}
			L = i + 1;
		}
	}
	for (int i = 0; i < N; i++) {
		if (r[i] == MOD)r[i] = R + N - i;
	}
	R = N - 1;
	L = -1;
	for (int i = N - 1; i >= 0; i--) {
		if (t[i] == '1') {
			if (L == -1)L = i;
			for (int j = R; j >= i; j--) {
				l[j] = j - i;
			}
			R = i - 1;
		}
	}
	for (int i = 0; i < N; i++) {
		if (l[i] == MOD)l[i] = i + N - L;
	}
	int ans = MOD;
	vector<vector<int>>lbox(N);
	for (int i = 0; i < N; i++)lbox[l[i]].push_back(r[i]);
	for (int i = 0; i < N; i++) {
		set<int>st;
		vector<vector<int>>llbox(N);
		int cnt = 0;
		for (int j = 0; j < N; j++) {
			if (t[j] != s[(i + j) % N]) {
				cnt++;
				llbox[l[(i+j)%N]].push_back((i+j)%N);
			}
		}
		for (int j = N - 1; j > 0; j--) {
			//cout << i << " " << j << " " << st.size() << endl;
			int box = j;
			if (st.empty()) {
				box += min(N - abs(i - j), abs(i - j));
				ans = min(ans, box+cnt);
				for (auto k : llbox[j])st.insert(-r[k]);
				//cout <<"a "<< i << " " << j << " " << ans << endl;
				continue;
			}
			auto it = st.upper_bound(j - N);
			if (it == st.end()) {
				box += min(N - abs(i - j), abs(i - j));
				ans = min(ans, box+cnt);
				for (auto k : llbox[j])st.insert(-r[k]);
				//cout <<"b "<< i << " " << j << " " << ans << endl;
			}
			box -= *it;
			//cout << i << " " << j << " " << box << endl;
			ans = min(ans, cnt+ box - *it + min(N - abs(i - j), abs(i - j)));
			ans = min(ans, cnt+ box + j + min(N - abs(i - (N + *it)), abs(i - (N + *it))));
			//cout <<"c "<< i << " " << j << " " << ans << endl;
			for (auto k : llbox[j])st.insert(-r[k]);
		}
		if (st.empty()) {
			ans = min(ans, cnt + min(N - i, i));
		//	cout << i << " 0 " << ans << endl;
			continue;
		}
		auto it = st.upper_bound(-N);
		ans = min(ans, cnt - *it + min(N - abs(i - (N + *it)), abs(i - (N + *it))));
		//cout << i << " 0 " << ans << endl;
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result