Submission #1543096

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstdlib>
#include <set>

using namespace std;

const int MAXN = 2000 + 10;

int N;
char A[MAXN], B[MAXN];
int ToMove[MAXN], nToMove;
int One[MAXN * 3], nOne;
int Left[MAXN], Right[MAXN];

int dist(int from, int to)
{
	from = (from % N + N) % N;
	to = (to % N + N) % N;
	return min(abs(from - to), N - abs(from - to));
}

void Work()
{
	scanf("%s%s", A, B);
	if (strcmp(A, B) == 0)
	{
		printf("0\n");
		return;
	}
	N = strlen(A);
	nOne = 0;
	for (int i = 0; i < N; i ++)
		if (B[i] == '1')
		{
			One[nOne * 3 + 0] = i - N;
			One[nOne * 3 + 1] = i;
			One[nOne * 3 + 2] = i + N;
			nOne ++;
		}
	sort(One, One + nOne * 3);
	if (nOne == 0)
	{
		printf("-1\n");
		return;
	}

	int ans = 1000000000;
	for (int start = 0; start < N; start ++)
	{
		int ops = 0;
		nToMove = 0;
		for (int i = 0; i < N; i ++)
			if (A[(start + i) % N] != B[i])
			{
				ops ++;
				if (B[i] == '0')
					ToMove[nToMove ++] = (start + i) % N;
			}
		if (nToMove == 0)
		{
			ops += min(start, N - start);
			ans = min(ans, ops);
			continue;
		}
		for (int k = 0; k < nToMove; k ++)
		{
			int i = ToMove[k];
			Left[k] = i - (*(upper_bound(One, One + nOne * 3, i) - 1));
			Right[k] = (*lower_bound(One, One + nOne * 3, i)) - i;
		}
		
		vector < pair <int, int> > V;
		multiset <int> Set;
		V.clear();
		Set.clear();
		for (int k = 0; k < nToMove; k ++)
		{
			V.push_back(make_pair(Left[k], Right[k]));
			Set.insert(-Right[k]);
		}
		sort(V.begin(), V.end());
		int ansmv = 1000000000, l, r, curmv;;

		l = 0;
		r = -*Set.begin();
		curmv = min(l + l + r + dist(-r, start), r + r + l + dist(l, start));
		ansmv = min(ansmv, curmv);

		for (int k = 0; k < nToMove; k ++)
		{
			Set.erase(Set.find(-V[k].second));
			l = V[k].first;
			r = Set.empty() ? 0 : (-*Set.begin());
			curmv = min(l + l + r + dist(-r, start), r + r + l + dist(l, start));
			ansmv = min(ansmv, curmv);
		}

		ans = min(ans, ansmv + ops);
	}

	printf("%d\n", ans);
}

int main()
{
	Work();
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void Work()’:
./Main.cpp:29:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s%s", A, B);
                     ^

Judge Result