leetcode-go/written-exam/kickstart-2019-D/no1/main.cc

#include <algorithm>
#include <cstring>
#include <cstdio>

using std::max;

#define N 100000
#define Q 100000

bool A[N];
int P[Q];
bool V[Q];
int dp[2][N + 1];

bool int2bool(int i) {
    int b = 0;
    while (0 < i) {
        b += i & 1;
        i >>= 1;
    }
    return b & 1;
}

int main() {
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; t++) {
        int n, q;
        scanf("%d %d", &n, &q);
        for (int i = 0, j; i < n; i++) {
            scanf("%d", &j);
            A[i] = int2bool(j);
        }
        for (int i = 0, j; i < q; i++) {
            scanf("%d %d", &P[i], &j);
            V[i] = int2bool(j);
        }
        printf("Case #%d:", t);
        for (int i = 0; i < q; i++) {
            A[P[i]] = V[i];
            memset(dp, 0, sizeof(dp));
            for (int j = 1; j <= n; j++) {
                if (A[j - 1]) { // Odd
                    dp[1][j] = dp[0][j - 1] + 1;
                    dp[0][j] = dp[1][j - 1] != 0 ? dp[1][j - 1] + 1 : 0;
                } else { // Even
                    dp[1][j] = max(0, dp[1][j - 1] + 1);
                    dp[0][j] = max(1, dp[0][j - 1] + 1);
                }
            }
            int l = 0;
            for (int j = 1; j <= n; j++) l = max(l, dp[0][j]);
            printf(" %d", l);
        }
        printf("\n");
    }
    return 0;
}