Submission #3422026

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int Max_N(2050);

int N, Ans, Lst[Max_N], Nxt[Max_N];
char A[Max_N], B[Max_N];

bool all_0(char S[Max_N])
{
	for (int i = 1;i <= N;++i)
		if (S[i] != '0')
			return false;
	return true;
}

struct node
{
	int x, y;
	void give(int _x, int _y)
	{
		x = _x, y = _y;
	}
	inline bool operator<(const node &b) const
	{
		return x < b.x;
	}
};
int M, Suf[Max_N];
node V[Max_N];

int work()
{
	if (M == 0)
		return 0;
	sort(V + 1, V + 1 + M);
	Suf[M + 1] = 0;
	for (int i = M;i >= 1;--i)
		Suf[i] = max(Suf[i + 1], V[i].y);
	int Ans(min(V[M].x, Suf[1]));
	for (int i = 1;i <= M - 1;++i)
		Ans = min(Ans, V[i].x + Suf[i + 1]);
	return Ans;
}

int main()
{
	scanf("%s", A + 1), N = strlen(A + 1);
	scanf("%s", B + 1);
	if (all_0(B))
	{
		printf("%d", all_0(A) ? 0 : -1);
		return 0;
	}
	for (int s = 1;s <= N;++s)
		if (B[s] == '1')
		{
			for (int i = s;i <= N;++i)
				Lst[i] = (B[i] == '1' ? 0 : Lst[i - 1] + 1);
			Lst[0] = Lst[N];
			for (int i = 1;i <= s - 1;++i)
				Lst[i] = (B[i] == '1' ? 0 : Lst[i - 1] + 1);
			for (int i = s;i >= 1;--i)
				Nxt[i] = (B[i] == '1' ? 0 : Nxt[i + 1] + 1);
			Nxt[N + 1] = Nxt[1];
			for (int i = N;i >= s + 1;--i)
				Nxt[i] = (B[i] == '1' ? 0 : Nxt[i + 1] + 1);
			break;
		}
	Ans = 0X3F3F3F3F;
	for (int l = 0;l <= N - 1;++l)
	{
		M = 0;
		for (int i = 1, j;i <= N;++i)
		{
			j = i - l;
			if (j <= 0)
				j += N;
			if (A[i] != B[j])
				V[++M].give(max(Lst[i] - l, 0), Nxt[i]);
		}
		Ans = min(Ans, l + work() * 2 + M);
	}
	for (int r = 1;r <= N - 1;++r)
	{
		M = 0;
		for (int i = 1, j;i <= N;++i)
		{
			j = i + r;
			if (j > N)
				j -= N;
			if (A[i] != B[j])
				V[++M].give(max(Nxt[i] - r, 0), Lst[i]);
		}
		Ans = min(Ans, r + work() * 2 + M);
	}
	printf("%d", Ans);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:51:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", A + 1), N = strlen(A + 1);
                                       ^
./Main.cpp:52:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", B + 1);
                    ^

Judge Result