Submission #376163

#	Time	Username	Problem	Language	Result	Execution time	Memory
376163		wiwiho	Lamps (JOI19_lamps)	C++14	4 / 100	30 ms	14512 KiB

lamp

#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, l, r;
vector<bool> del;

bool check(int id){
    if(del[id]) return false;
    if(v[id] != 1) return false;
    if(l[id] != -1 && del[l[id]]) return false;
    if(r[id] != -1 && del[r[id]]) return false;
    return !(l[id] != -1 && v[l[id]] != 3 && v[l[id]] != 5 && r[id] != -1 && v[r[id]] != 3 && v[r[id]] != 6);
}

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();
    del.resize(m);
    l.resize(m, -1);
    r.resize(m, -1);
    for(int i = 0; i < m; i++){
        if(i) l[i] = i - 1;
        if(i < m - 1) r[i] = i + 1;
    }

    queue<int> q;
    for(int i = 0; i < m; i++){
        if(check(i)){
            q.push(i);
            del[i] = true;
        }
    }

    while(!q.empty()){
        int now = q.front();
        q.pop();
        ans++;
        if(l[now] != -1) r[l[now]] = r[now];
        if(r[now] != -1) l[r[now]] = l[now];
        if(l[now] != -1 && check(l[now])){
            del[l[now]] = true;
            q.push(l[now]);
        }
        if(r[now] != -1 && check(r[now])){
            del[r[now]] = true;
            q.push(r[now]);
        }
    }
    //printv(v, cerr);
    //printv(del, cerr);

    bool tmp = false;
    for(int i = 0; i < m; i++){
        if(del[i]) continue;
        if(v[i] == 1){
            ans++;
            tmp = true;
        }
        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;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 4 / 4
• Subtask 4: 0 / 49