Submission #1083055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083055		Sharky	Lamps (JOI19_lamps)	C++17	4 / 100	179 ms	3924 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;
        }
        vector<bool> ok(4, 1);
        if (b[i] == '1') ok[0] = 0;
        if (b[i] == '0') ok[1] = 0;
        if (a[i] == b[i]) ok[2] = 0;
        if (a[i] != b[i]) ok[3] = 0;
        for (auto& arr : st) {
            int x = arr[0], y = arr[1], z = arr[2];
            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);
                else if (j != x && j != y && x < 3 && y < 3 && z == 3) ckmin(dp[cur][x][y][j], dp[prev][x][y][z] + 1);
            }
            if (x < 3 && y < 3 && z < 3 && ok[z]) ckmin(dp[cur][x][y][z], dp[prev][x][y][z]);
            else if (x < 3 && y < 3 && z == 3 && ok[y]) ckmin(dp[cur][x][y][z], dp[prev][x][y][z]);
            else if (x < 3 && y == 3 && z == 3 && ok[x]) ckmin(dp[cur][x][y][z], dp[prev][x][y][z]);
            else if (x == 3 && y == 3 && z == 3 && ok[3]) ckmin(dp[cur][x][y][z], dp[prev][x][y][z]);
            if (x < 3 && y < 3 && z < 3 && ok[y]) {
                ckmin(dp[cur][x][y][3], dp[prev][x][y][z]);
            } else if (x < 3 && y < 3 && z == 3 && ok[x]) {
                ckmin(dp[cur][x][3][z], dp[prev][x][y][z]);
            } else if (x < 3 && y == 3 && z == 3 && ok[3]) {
                ckmin(dp[cur][3][y][z], dp[prev][x][y][z]);
            }
        }
    }
    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';
}

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