Submission #3011755

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

int count1(string& s){
    int rec = 0;
    for(auto c : s){
        rec += (c == '1');
    }

    return rec;
}

int main(){
    int n; cin >> n;
    string s; cin >> s;
    set<string> used;
    queue<string> q;
    used.insert(s);
    q.push(s);
    int ans;
    while(1){

        string t = q.front();
        q.pop();
        //cout << t << endl;

        for(int i = 1; i <= n - 2; i++){

            if(t[i - 1] == '1' && t[i] == '0' && t[i + 1] == '1'){

                t[i - 1] = '0';
                t[i] = '1';
                t[i + 1] = '0';
                if(used.find(t) == used.end()){
                    used.insert(t);
                    q.push(t);
                }
                t[i - 1] = '1';
                t[i] = '0';
                t[i + 1] = '1';

            }
        }

        if(q.empty()){
            ans = count1(s) - count1(t);
            break;
        }
    }

    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result