本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-16 19:37:34

考虑将 $a$ 和 $b$ 拼起来其实就是 $a \times 10^k + b$，$k$ 是多少不重要，因为在模 $3$ 的意义下，$10^k$ 恒等于 $1$。

所以原式就变成了 $(a_i + a_j)^2 + a_i \times a_j$。

然后由于在模 $3$ 意义下，$a_i$ 只有 $3$ 钟取值。

于是把他们一一列举出来：

我们发现对于 $Z=0$，那么只要保证所有的 $0$ 都在一组内即可。

设 $cnt_i$ 表示 $i$ 的出现次数。

那么只要 $cnt_0 \le \frac n2$ 即可。

否则对于 $Z=2$，只要让 $1,2$ 在同一组即可。

也就是 $cnt_1 + cnt_2 \le \frac n2$。

又由于 $cnt_0 + cnt_1 + cnt_2 = n$，所以上面那两个式子至少有一个成立，所以不会无解。

#include <bits\/stdc++.h>

using namespace std;

int n;
int a[100010];
bool st[100010];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] % 3 == 0)
            st[i] = true, ++cnt;
    }
    
    if (cnt > n \/ 2) {
        memset(st, false, sizeof(st));
        cnt = 0;

        for (int i = 1; i <= n; ++i)
            if (a[i] % 3 == 1 || a[i] % 3 == 2) {
                ++cnt;
                st[i] = true;
            }

        for (int i = 1; i <= n; ++i) if (!st[i] && cnt < n \/ 2) {
            ++cnt;
            st[i] = true;
        }
    
        puts("2");
        for (int i = 1; i <= n; ++i) printf("%d", st[i]);
        return 0;
    }

    for (int i = 1; i <= n; ++i)
        if (!st[i] && cnt < n \/ 2) {
            ++cnt;
            st[i] = true;
        }
    
    puts("0");
    for (int i = 1; i <= n; ++i) printf("%d", st[i]);

    return 0;
}