Submission #1165326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165326		antonn	Lamps (JOI19_lamps)	C++20	100 / 100	588 ms	4476 KiB

lamp

#include <bits/stdc++.h> 


#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int inf = 1e9;

char apply(char c, vi ops) {
    for (auto x : ops) {
        if (x == 0) c = '0';
        if (x == 1) c = '1';
        if (x == 2) c ^= '0' ^ '1';
    }
    return c;
}

int cost(vi a, vi b) {
    // min cost to reach a from b
    int j = 0, ans = 0;
    for (int i = 0; i < a.size(); ++i) {
        int old = j;
        while (j < b.size() && a[i] != b[j]) ++j;
        if (j < b.size()) {
            ++j;
            continue;
        }
        j = old;
        ++ans;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n; string a, b; cin >> n >> a >> b;
    a = "#" + a, b = "#" + b;
    
    vector<vi> states;
    states.push_back({});
    states.push_back({0});
    states.push_back({1});
    states.push_back({2}); 
    
    states.push_back({0, 1}); 
    states.push_back({1, 0}); 
    states.push_back({0, 2}); 
    states.push_back({2, 0}); 
    states.push_back({1, 2}); 
    states.push_back({2, 1});
    states.push_back({2, 2});
    
    states.push_back({0, 1, 2});
    states.push_back({0, 2, 1});
    states.push_back({1, 0, 2});
    states.push_back({1, 2, 0});
    states.push_back({2, 0, 1});
    states.push_back({2, 1, 0});
    states.push_back({0, 2, 2});
    states.push_back({2, 0, 2});
    states.push_back({2, 2, 0});
    states.push_back({1, 2, 2});
    states.push_back({2, 1, 2});
    states.push_back({2, 2, 1});
    
    assert(states[0].empty());
    
    vector<vector<int>> f(states.size(), vector<int>(states.size()));
    for (int i = 0; i < states.size(); ++i) {
        for (int j = 0; j < states.size(); ++j) {
            f[i][j] = cost(states[i], states[j]);
        }
    }
    
    vector<int> dp((int) states.size(), inf);
    vector<int> ndp((int) states.size(), inf);
    dp[0] = 0;
    vector<int> prev_states; prev_states.push_back(0);
    for (int i = 1; i <= n; ++i) {
        vector<int> nw;
        for (int s = 0; s < states.size(); ++s) ndp[s] = inf;
        for (int s = 0; s < states.size(); ++s) {
            if (apply(a[i], states[s]) != b[i]) continue;
            
            for (int p : prev_states) {
                ckmin(ndp[s], dp[p] + f[s][p]);
            }
            if (ndp[s] != inf) nw.push_back(s);
        }
        swap(prev_states, nw);
        swap(dp, ndp);
    }
    
    int ans = inf;
    for (int s = 0; s < states.size(); ++s) ckmin(ans, dp[s]);
    cout << ans << "\n";
}

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