Đặt ~S_n = 1^2 + 2^2 + \ldots + n^2~. Xét các trường hợp sau:

• ~n \equiv 0\ (\text{mod}\ 4)~: ~S_n \equiv 0\ (\text{mod}\ 2)~.
• ~n \equiv 1\ (\text{mod}\ 4)~: ~S_n \equiv 1\ (\text{mod}\ 2)~.
• ~n \equiv 2\ (\text{mod}\ 4)~: ~S_n \equiv 1\ (\text{mod}\ 2)~.
• ~n \equiv 3\ (\text{mod}\ 4)~: ~S_n \equiv 0\ (\text{mod}\ 2)~.

Để có thể chia ~[1^2, 2^2, \ldots, n^2]~ thành hai tập có tổng bằng nhau, ~n \equiv 0~ hoặc ~n \equiv 3\ (\text{mod}\ 4)~

Với ~n = 3~ hoặc ~n = 4~, rõ ràng ta không thể chia tập S thành hai tập có tổng bằng nhau. Xét ~n \ge 7~:

• Với ~n = 7~: ~1^2 + 2^2 + 4^2 + 7^2 = 3^2 + 5^2 + 6^2~.
• Với ~n = 8~: ~1^2 + 4^2 + 6^2 + 7^2 = 2^2 + 3^2 + 5^2 + 8^2~.
• Với ~n = 11~: ~1^2 + 3^2 + 4^2 + 5^2 + 9^2 + 11^2 = 2^2 + 6^2 + 7^2 + 8^2 + 10^2~.
• Với ~n = 12~: ~1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2 + 7^2 + 8^2 + 11^2 = 9^2 + 10^2 + 12^2~.

Mặt khác, nếu ta có thể chia ~S_n~ thành hai tập bằng nhau, ta cũng có thể chia ~S_{n + 8}~ thành hai tập bằng nhau: ~(n - 7)^2 + (n - 4)^2 + (n - 2)^2 + (n - 1)^2 = (n - 6)^2 + (n - 5)^2 + (n - 3)^2 + n^2~.

Code mẫu

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

void solve() {
  int n;
  cin >> n;
  int nn = n;
  if (n % 4 != 0 && n % 4 != 3) {
    cout << "NO\n";
    return;
  }
  if (n < 7) {
    cout << "NO\n";
    return;
  }

  vector<int> a, b;
  if (n % 8 == 0) {
    a = vector<int>{1, 4, 6, 7};
    b = vector<int>{2, 3, 5, 8};
  }
  else if (n % 8 == 3) {
    a = vector<int>{1, 3, 4, 5, 9, 11};
    b = vector<int>{2, 6, 7, 8, 10};
  }
  else if (n % 8 == 4) {
    a = vector<int>{9, 10, 12};
    b = vector<int>{1, 2, 3, 4, 5, 6, 7, 8, 11};
  }
  else {
    a = vector<int>{1, 2, 4, 7};
    b = vector<int>{3, 5, 6};
  }
  while (n > 12) {
    for (int x : {n - 7, n - 4, n - 2, n - 1}) {
      a.push_back(x);
    }
    for (int x : {n - 6, n - 5, n - 3, n}) {
      b.push_back(x);
    }
    n -= 8;
  }

  vector<bool> ans(nn + 1);
  for (int x : a) {
    ans[x] = 0;
  }
  for (int x : b) {
    ans[x] = 1;
  }

  cout << "YES\n";
  for (int i = 1; i <= nn; ++i) {
    cout << ans[i] << " \n" [i == nn];
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}