CF1725H Hot Black Hot White

思路

首先转化原式为：

$$(a_i + a_j) \times (a_i + a_j + 1) \equiv z \pmod 3$$

考虑对 $a_i \bmod 3,a_j \bmod 3$ 进行分讨：

$a_i/a_j$	$0$	$1$	$2$
$0$	$0$	$1$	$1$
$1$	$1$	$2$	$2$
$2$	$1$	$2$	$2$

发现，只有当 $a_i = a_j = 0$ 时，原式为 $0$。于是记 $a$ 中 $0$ 的数量为 $x$。

如果 $x \geq \frac{n}{2}$，令 $z = 2$，将 $\frac{n}{2}$ 的 $0$ 放在一组，其余放在另一组。

否则，令 $z = 0$，将所有 $0$ 都丢入同一组，其余随便分即可。

Code

#include <bits/stdc++.h>
#define re register

using namespace std;

const int N = 1e5 + 10;
int n,num;
int arr[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

int main(){
    n = read();
    for (re int i = 1;i <= n;i++){
        arr[i] = read() % 3; num += (!arr[i]);
    }
    if (num * 2 >= n){
        int cnt = 0;
        puts("2");
        for (re int i = 1;i <= n;i++){
            if (!arr[i]){
                if (cnt < n / 2) putchar('0');
                else putchar('1');
                cnt++;
            }
            else putchar('1');
        }
    }
    else{
        int cnt = 0;
        puts("0");
        for (re int i = 1;i <= n;i++){
            if (!arr[i]) putchar('0');
            else{
                if (cnt + num < n / 2) putchar('0');
                else putchar('1');
                cnt++;
            }
        }
    }
    return 0;
}