Submission #1544747

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <utility>
#include <cstdlib>
#include <memory>
#include <queue>
#include <cassert>
#include <cmath>
#include <ctime>
#include <complex>
#include <bitset>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <numeric>

using namespace std;

#define ws ws_____________________
#define y1 y1_____________________
#define y0 y0_____________________
#define left left_________________
#define right right_______________
#define next next_________________
#define prev prev_________________
#define hash hash_________________

#define pb push_back
#define fst first
#define snd second
#define mp make_pair 
#define sz(C) ((int) (C).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define ford(i, n) for (int i = int(n) - 1; i >= 0; --i)
#define all(C) begin(C), end(C)

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef long double ld;
typedef complex<double> cd;

#ifdef LOCAL
#define eprintf(args...) fprintf(stderr, args), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define FILE_NAME "a"

const int MAXN = 2e3 + 10;

#define TEST 0

int n;
vi a;
vi b;

bool read() {
#if !TEST
	static char buf[MAXN];
	scanf("%s\n", buf);
	for (int i = 0; buf[i]; ++i) {
		a.pb(buf[i] - '0');
	}

	scanf("%s\n", buf);
	for (int i = 0; buf[i]; ++i) {
		b.pb(buf[i] - '0');
	}

	n = sz(a);
	assert(sz(b) == n);
#else
	n = 1 + rand() % 10;
	a.resize(n);
	b.resize(n);
	forn(i, n) {
		a[i] = rand() & 1;
		b[i] = rand() % 10 < 3;
	}
#endif
	return 1;
}

vi pref;

int sum_b(int l, int r) {
	assert(l <= r);
	assert(0 <= l);
	assert(r < n);
	return pref[r + 1] - pref[l];
}

bool check_left(int i, int l) {
	assert(l < n);
	if  (i - l < 0) {
		if  (sum_b(0, i) > 0) {
			return 1;
		}
		if  (sum_b(n - (l - i), n - 1) > 0) {
			return 1;
		}
		return 0;
	}
	return sum_b(i - l, i) > 0;
}

bool check_right(int i, int r) {
	assert(r < n);
	if  (i + r >= n) {
		if  (sum_b(i, n - 1) > 0) {
			return 1;
		} 
		if  (sum_b(0, r - (n - 1 - i) - 1) > 0) {
			return 1;
		}
		return 0;
	}
	return sum_b(i, i + r) > 0;
}

int solve() {
	int Sum_b = accumulate(all(b), 0);
	if  (Sum_b == 0) {
		int Sum_a = accumulate(all(a), 0);
		if  (Sum_a == 0) {
			return 0;
		}
		return -1;
	}

	// forn(i, n) {
	// 	printf("i=%d, min_l=%d, min_r=%d\n", i, min_l[i], min_r[i]);
	// }

	int ans = 10 * n;

	forn(iter, 2) {
		pref.assign(n + 1, 0);
		forn(i, n) {
			pref[i + 1] = pref[i] + b[i];
		}

		vi min_l(n);
		vi min_r(n);
		forn(i, n) {
			bool was = 0;
			for (int l = 0; l < n; ++l) {
				if  (check_left(i, l)) {
					min_l[i] = l;
					was = 1;
					break;
				}
			}
			assert(was);
			was = 0;
			for (int r = 0; r < n; ++r) {
				if  (check_right(i, r)) {
					min_r[i] = r;
					was = 1;
					break;
				}
			}
			assert(was);
		}

		forn(r, n) {
			int flipped = 0;
			set<pii> S;
			vvi to_erase(n);
			forn(i, n) {
				int j = (i + r) % n;
				if  (a[i] != b[j]) {
					++flipped;
					if  (!check_right(i, r)) {
						to_erase[min_r[i]].pb(i);
						S.insert(mp(min_l[i], i));
					}
				}
			}

			for (int nr = r; nr < n; ++nr) {
				for (int i : to_erase[nr]) {
					S.erase(mp(min_l[i], i));
				}
				int l = 0;
				if  (!S.empty()) {
					l = S.rbegin()->fst;
				}

				int cur = flipped + l * 2 + r + (nr - r) * 2;
				ans = min(ans, cur);
			}
		}

		reverse(all(a));
		reverse(all(b));
	}

	return ans;
}

bool brut_check_left(int i, int l) {
	forn(it, l + 1) {
		int j = (i - it % n + n) % n;
		if  (b[j]) {
			return 1;
		}
	}
	return 0;
}

bool brut_check_right(int i, int r) {
	forn(it, r + 1) {
		int j = (i + it % n) % n;
		if  (b[j]) {
			return 1;
		}
	}
	return 0;
}

int brut() {
	int best_l = -1;
	int best_r = -1;
	int ans = 10 * n;
	forn(l, n) forn(r, n) {
		int cur = 0;
		bool ok = 1;
		forn(i, n) {
			int j = (i + (r - l + n) % n) % n;
			if  (a[i] != b[j]) {
				++cur;
				if  (!brut_check_left(i, l) && !brut_check_right(i, r)) {
					ok = 0;
					break;
				}
			}
		}

		if  (!ok) {
			continue;
		}

		cur += l + r;
		if  (ans > cur) {
			best_l = l;
			best_r = r;
			ans = cur;
		}
	}

	printf("best_l = %d, best_r = %d\n", best_l, best_r);
	return ans >= 5 * n ? -1 : ans;
}

int main() {
#ifdef LOCAL
	freopen(FILE_NAME ".in", "r", stdin);
	// freopen(FILE_NAME ".out", "w", stdout);
#endif

#if TEST
	while (1) {
		read();

		int my = solve();

		int br = brut();

		if  (my == br) {
			printf("OK %d == %d\n", my, br);
			continue;
		}

		printf("my = %d, br = %d\n", my, br);

		printf("n = %d\n", n);
		forn(i, n) {
			printf("%d ", a[i]);
		}
		puts("");
		forn(i, n) {
			printf("%d ", b[i]);
		}
		puts("");
		return 0;
	}

#endif

	while (read()) {
		printf("%d\n", solve());

		break;
	}

#ifdef LOCAL
	cerr.precision(5);
	cerr << "Time: " << fixed << (double) clock() / CLOCKS_PER_SEC << endl;
#endif
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘bool read()’:
./Main.cpp:74:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s\n", buf);
                    ^
./Main.cpp:79:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s\n", buf);
                    ^

Judge Result