Submission #1165033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165033		antonn	Lamps (JOI19_lamps)	C++20	0 / 100	1097 ms	29936 KiB

lamp

#include <bits/stdc++.h> // e gresit exemplu mjur

#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 N = 1e6 + 7;

int dp[3][N], f[N], g[N], pref[N], noxor[N], suff[N], cnt[N];

string apply(string s, array<int, 3> a) {
    for (int i = a[0]; i <= a[1]; ++i) {
        if (a[2] == 0) s[i] = '0';
        if (a[2] == 1) s[i] = '1';
        if (a[2] == 2) s[i] ^= '0' ^ '1';
    }
    return s;
}

string apply(string s, array<int, 3> a, array<int, 3> b, array<int, 3> c, array<int, 3> d, array<int, 3> e) {
    apply(s, a);
    apply(s, b);
    apply(s, c);
    apply(s, d);
    apply(s, e);
    return s;
} 

int n; 
string a, b; 
vector<int> sol;

void bkt(int pos = 0) {
    if (pos == n) {
        string s = "";
        int ops = 0;
        for (int i = 0; i < n; ++i) {
            if (i == 0 || sol[i] != sol[i - 1]) ++ops;
            
            if (sol[i] == 0) ops += '0';
            if (sol[i] == 1) ops += '1';
            if (sol[i] == 2) ops += a[i + 1];
        }
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (a[i] != b[i]) {
                ++cnt;
            } else {
                if (cnt != 0) ++ops;
                cnt = 0;
            }
        }
        if (cnt != 0) ++ops;
        if (ops == 5) {
            for (int j : sol) cout << j << " ";
            cout << "\n";
            exit(0);
        }
        return;
    }
    for (int i = 0; i < 3; ++i) {
        sol.push_back(i);
        bkt(pos + 1);
        sol.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> n >> a >> b;
    a = "#" + a, b = "#" + b;
    f[0] = 2;
    for (int i = 1; i <= n; ++i) {
        char c;
        if (a[i] == b[i]) c = b[i] ^ '0' ^ '1';
        if (a[i] != b[i]) c = '?';
        if (c == '0') f[i] = 0;
        if (c == '1') f[i] = 1;
        if (c == '?') f[i] = 2;
        g[i] = b[i] - '0';
    }
    noxor[1] = 1;
    for (int i = 2; i <= n; ++i) noxor[i] = noxor[i - 1] + (g[i - 1] != g[i]);
    
    pref[1] = 1;
    for (int i = 2; i <= n; ++i) pref[i] = pref[i - 1] + (f[i - 1] != f[i]);
    
    for (int i = 0; i < 3; ++i) for (int j = 0; j < N; ++j) dp[i][j] = 1e9;
    dp[f[0]][0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) { // xorez
            for (int x = 0; x < 3; ++x) {
                int cost = 0;
                cost += dp[x][j - 1]; 
                cost += 1 + pref[i] - pref[j];
                cost -= (f[j] == x);
                ckmin(dp[f[i]][i], cost + 1);
            }
        }
        for (int j = 1; j <= i; ++j) { // nu xorez
            for (int x = 0; x < 3; ++x) {
                int cost = 0;
                cost += dp[x][j - 1];
                cost += 1 + noxor[i] - noxor[j];
                cost -= (x == g[j]);
                ckmin(dp[g[i]][i], cost);
            }
        }
        if (a[i] == b[i]) {
            for (int x = 0; x < 3; ++x) ckmin(dp[2][i], dp[x][i - 1]);
        }
    }
    
    cnt[1] = 0;
    for (int i = 2; i <= n; ++i) cnt[i] = cnt[i - 1] + (b[i] != b[i - 1]);
    for (int i = n; i >= 1; --i) suff[i] = 1e9;
    suff[n] = 1;
    for (int i = n - 1; i >= 1; --i) {
        if (a[i] == b[i]) suff[i] = suff[i + 1];
        for (int j = i; j <= n; ++j) {
            if (cnt[j] == cnt[i]) ckmin(suff[i], suff[j + 1] + 1);
        }
    }
    int ans = 1e9;
    for (int i = 0; i <= n; ++i) for (int x = 0; x < 3; ++x) ckmin(ans, dp[x][i] + suff[i + 1]);
    cout << ans << "\n";
    
    // bkt();
}
/**
18
001100010010000110
110110001000100101
110100010010000110

**/

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