Submission #1543600

---

Source Code Expand

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
static_assert(sizeof(long) >= 8, "sizeof(long) >= 8");
int eval(int s, int cl, int cr) {
    // fprintf(stderr, "%d %d %d %d\n", s, cl, cr, abs(s) + max(0, cr - max(0, s)) * 2 + max(0, cl - max(0, -s)) * 2);
    return max(0, cr - max(0, s)) * 2 + max(0, cl - max(0, -s)) * 2;
}
// static_assert(eval(-10, 5, 5) == 20);
// static_assert(eval(10, 5, 5) == 20);
// static_assert(eval(10, 0, 11) == 12);
// static_assert(eval(-10, 11, 0) == 12);
char a[6000], b[6000];
int ll[6000], lr[6000];
pair<int, int> c[2000];
int main() {
    scanf("%s%s", a, b);
    int n = strlen(a);
    if (strcmp(a, b) == 0) {
        puts("0");
        return 0;
    }
    if (!strchr(b, '1')) {
        puts("-1");
        return 0;
    }
    copy_n(a, n, a + n);
    copy_n(a, n, a + 2 * n);
    copy_n(b, n, b + n);
    copy_n(b, n, b + 2 * n);
    for (int i = 1; i < 2 * n; i++)
        ll[i] = b[i] == '1' ? 0 : ll[i - 1] + 1;
    for (int i = 3 * n - 2; i >= n; i--)
        lr[i] = b[i] == '1' ? 0 : lr[i + 1] + 1;
    int ans = 2 * n;
    for (int s = -n; s <= n; s++) {
        int cur = abs(s), m = 0;
        for (int i = n; i < 2 * n; i++)
            if (a[i] != b[i + s]) {
                cur++;
                if (a[i] == '1')
                    c[m++] = make_pair(ll[i], lr[i]);
            }

        if (m) {
            sort(c, c + m);
            int cur1 = eval(s, c[m - 1].first, 0);
            for (int i = m - 1, cr = 0; i >= 0; i--) {
                cr = max(cr, c[i].second);
                cur1 = min(cur1, eval(s, i ? c[i - 1].first : 0, cr));
            }
            cur += cur1;
        }
        ans = min(ans, cur);
    }
    printf("%d\n", ans);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:20:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s%s", a, b);
                        ^

Judge Result