Submission #1543059

---

Source Code Expand

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

using namespace std;

char a[2001];
char b[2001];
int l[2000];
int r[2000];

int calc(vector<pair<int, int> > &v) {
    int ans = 1e9, m = 0, i;
    
    if (v.size() == 0) return 0;
    
    for (i = 0; i < v.size(); i++) {
        ans = min(ans, v[i].first + m);
        m = max(m, v[i].second);
    }
    
    ans = min(ans, m);
    
    return ans * 2;
}

int main() {
    int n, ans = 1e9, i, j;
    
    scanf("%s", a);
    scanf("%s", b);
    
    n = strlen(a);
    
    for (i = 0; i < n; i++) {
        if (b[i] == '1') break;
    }
    
    if (i == n) {
        int ans = 0;
        
        for (i = 0; i < n; i++) {
            if (a[i] == '1') ans = -1;
        }
        
        printf("%d\n", ans);
        
        return 0;
    }
    
    for (i = 1; i < n; i++) {
        if (b[i] == '1') {
            l[i] = 0;
        } else {
            l[i] = l[i - 1] + 1;
        }
    }
    
    if (b[0] == '0') {
        l[0] = l[n - 1] + 1;
        
        for (i = 1; i < n; i++) {
            if (b[i] == '1') break;
            
            l[i] = l[i - 1] + 1;
        }
    }
    
    for (i = n - 2; i >= 0; i--) {
        if (b[i] == '1') {
            r[i] = 0;
        } else {
            r[i] = r[i + 1] + 1;
        }
    }
    
    if (b[n - 1] == '0') {
        r[n - 1] = r[0] + 1;
        
        for (i = n - 2; i >= 0; i--) {
            if (b[i] == '1') break;
            
            r[i] = r[i + 1] + 1;
        }
    }
    
    for (i = 0; i < n; i++) {
        int c = i;
        vector <pair<int, int> > v;
        
        for (j = 0; j < n; j++) {
            int x = (j + i) % n;
            
            if (b[j] != a[x]) {
                c++;
                
                if (b[j] == '0' && l[x] > i) v.push_back(make_pair(l[j], r[x]));
            }
        }
        
        sort(v.begin(), v.end());
        reverse(v.begin(), v.end());
        
        c += calc(v);
        
        ans = min(ans, c);
    }
    
    for (i = 0; i < n; i++) {
        int c = i;
        vector <pair<int, int> > v;
        
        for (j = 0; j < n; j++) {
            int x = (j - i + n) % n;
            
            if (b[j] != a[x]) {
                c++;
                
                if (b[j] == '0' && r[x] > i) v.push_back(make_pair(l[x], r[j]));
            }
        }
        
        sort(v.begin(), v.end());
        reverse(v.begin(), v.end());
        
        c += calc(v);
        
        ans = min(ans, c);
    }
    
    printf("%d\n", ans);
    
    return 0;
}

Submission Info

Compile Error

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

Judge Result