Submission #1083136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083136		Sharky	Lamps (JOI19_lamps)	C++17	100 / 100	275 ms	4388 KiB

lamp

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

const int N = 1e6 + 10;
const int inf = 1e9;

int n, dp[2][4][4][4];
char a[N], b[N];

void ckmin(int &x, int y) {
    x = min(x, y);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++) {
                for (int l = 0; l < 4; l++) {
                    dp[i][j][k][l] = inf;
                }
            }
        }
    }
    dp[0][3][3][3] = 0;
    vector<array<int, 3>> st;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++) {
                if (i == 3 && j < 3) continue;
                if (j == 3 && k < 3) continue;
                if (i != 3 && j != 3 && i == j) continue;
                if (i != 3 && k != 3 && i == k) continue;
                if (j != 3 && k != 3 && j == k) continue;
                st.push_back({i, j, k});
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        int cur = i&1, prev = 1 - cur;
        for (auto& arr : st) {
            int x = arr[0], y = arr[1], z = arr[2];
            dp[cur][x][y][z] = inf;
        }
        for (auto& arr : st) {
            int x = arr[0], y = arr[1], z = arr[2];
            if (dp[prev][x][y][z] >= inf) continue;
            for (int j = 0; j < 3; j++) {
                // if (!ok[j]) continue;
                if (x == 3) ckmin(dp[cur][j][y][z], dp[prev][x][y][z] + 1);
                else if (j != x && x < 3 && y == 3) {
                    ckmin(dp[cur][x][j][z], dp[prev][x][y][z] + 1);
                    ckmin(dp[cur][j][x][z], dp[prev][x][y][z] + 1);
                }
                else if (j != x && j != y && x < 3 && y < 3 && z == 3) {
                    ckmin(dp[cur][x][y][j], dp[prev][x][y][z] + 1);
                    ckmin(dp[cur][x][j][y], dp[prev][x][y][z] + 1);
                    ckmin(dp[cur][j][x][y], dp[prev][x][y][z] + 1);
                }
            }
            ckmin(dp[cur][3][3][3], dp[prev][x][y][z]);
            ckmin(dp[cur][x][3][3], dp[prev][x][y][z]);
            ckmin(dp[cur][y][3][3], dp[prev][x][y][z]);
            ckmin(dp[cur][z][3][3], dp[prev][x][y][z]);
            ckmin(dp[cur][x][y][3], dp[prev][x][y][z]);
            ckmin(dp[cur][x][z][3], dp[prev][x][y][z]);
            ckmin(dp[cur][y][z][3], dp[prev][x][y][z]);
            ckmin(dp[cur][x][y][z], dp[prev][x][y][z]);
        }
        for (auto& arr : st) {
            char o = a[i];
            for (int j = 0; j < 3; j++) {
                int cmd = arr[j];
                if (cmd == 3) continue;
                if (cmd == 0) o = '0';
                else if (cmd == 1) o = '1';
                else if (o == '1') o = '0';
                else o = '1';
            }
            if (o != b[i]) dp[cur][arr[0]][arr[1]][arr[2]] = inf;
            // cout << i << " " << arr[0] << " " << arr[1] << " " << arr[2] << " " << dp[cur][arr[0]][arr[1]][arr[2]] << '\n';
        }
    }
    int ans = inf;
    for (auto& arr : st) {
        int i = arr[0], j = arr[1], k = arr[2];
        ans = min(ans, dp[n & 1][i][j][k]);
    }
    cout << ans << '\n';
}

// 110010

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