Submission #5662962

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int MAXn = 2000 + 10;
typedef pair<bool, bool> pbb;
struct salarQ {
	int l , r;
	pair<pair<bool, bool> , int> ar[2 * MAXn];
	
	salarQ() {
		for (int i = 0; i < 2 * MAXn; i++)
			ar[i].first = pbb(0, 0);
		l = r =  MAXn;
	}
	
	void push_back(bool a) {
		ar[r++].first.first = a;
	}
	
	void shift_left() {
		swap(ar[l], ar[r]);
		l++;r++;
	}
	void shift_right() {
		l--;r--;
		swap(ar[l], ar[r]);
	}
	
	bool get(int a) {
		return ar[l+a].first.first;
	}
	
	void set(int a) {
		ar[l+a].first.second = true;
	}
	
	bool ca(int a) {
		return ar[l+a].first.second;
	}
	
	int min1(int a) {
		return ar[l+a].second;
	}
	
	void setmin1(int a, int b) {
		ar[l+a].second = b;
	}
};
salarQ Q, Q2;
string a, b;
int n, ans = 10 * MAXn;
void check(int ind, salarQ &k) {
	int cnt = 0, hp = 0;
	for (int i = 0; i < n; i++) {
		if (b[i] == '1')
			k.set(i);
	}
	for (int i = 0; i < n; i++)
		if (k.get(i) != b[i] - '0') {
			if (!k.ca(i))
				hp = max(k.min1(i), hp);
			cnt++;
		}
	ans = min(ans, cnt + ind + 2 * hp);
}

int main() {
	cin >> a >> b;
	bool flag = false;
	for (int i = 0; i < b.size(); i++)
		if (b[i] == '1')
			flag = true;
	if (!flag) {
		for (int i = 0; i < a.size(); i++)
			if (a[i] == '1')
				return cout << -1,0;
		return cout << 0,0;
	}
	n = a.size();
	for (int i = 0; i < n; i++) {
		Q.push_back(a[i]-'0');
		for (int j = 0; j < n; j++)
			if (b[(i-j+n) % n] == '1') {
				Q.setmin1(i, j);
				break;
			}
		Q2.push_back(a[i]-'0');
		for (int j = 0; j < n; j++)
			if (b[(i+j) % n] == '1') {
				Q2.setmin1(i, j);
				break;
			}
	}
	for (int i = 0; i < n; i++) {
		check(i, Q);
		Q.shift_right();
	}
	for (int i = 0; i < n; i++) {
		check(i, Q2);
		Q2.shift_left();
	}

	cout << ans;
}

Submission Info

Judge Result