Submission #376165

#TimeUsernameProblemLanguageResultExecution timeMemory
376165wiwihoLamps (JOI19_lamps)C++14
4 / 100
17 ms6964 KiB
#include <bits/stdc++.h>

#define eb emplace_back
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

int gettype(vector<int>& now){
    int n = now.size();
    int diff = 0;
    for(int i = 0; i < n; i++){
        if(now[i] == 1) diff++;
    }
    if(diff == 0) return 3;
    else if(diff == n) return 2;
    int l = 0, r = 0;
    for(int i = 0; i < n && now[i] == 1; i++) l++;
    for(int i = n - 1; i >= 0 && now[i] == 1; i--) r++;
    if(l + r != diff) return 4;
    if(r == 0) return 5;
    if(l == 0) return 6;
    return 1;
}

vector<int> v;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    string a, b;
    cin >> n >> a >> b;
    a += ' ';
    b += ' ';

    vector<int> now;
    char lst = 0;
    int ans = 0;
    for(int i = 0; i <= n; i++){
        if(i != 0 && b[i] != lst && !now.empty()){
            int t = gettype(now);
            now.clear();
            if(t == 4) ans++;
            else v.eb(t);
        }
        lst = b[i];
        now.eb(a[i] != b[i]);
    }
    int m = v.size();
    //printv(v, cerr);
    //printv(del, cerr);

    bool tmp = false;
    for(int i = 0; i < m; i++){
        if(v[i] == 1){
            ans++;
        }
        if(v[i] == 2){
            tmp = true;
        }
        if(v[i] == 3){
            if(tmp) ans++;
            tmp = false;
        }
        if(v[i] == 5){
            ans++;
            tmp = false;
        }
        if(v[i] == 6){
            if(tmp) ans++;
            tmp = true;
        }
    }
    if(tmp) ans++;

    cout << ans << "\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...