The answer is the number of $$$1$$$s modulo $$$2$$$.

We can get that by adding '-' before the $$$\text{2nd}, \text{4th}, \cdots, 2k\text{-th}$$$ $$$1$$$, and '+' before the $$$\text{3rd}, \text{5th}, \cdots, 2k+1\text{-th}$$$ $$$1$$$.

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

char c[1005];
int main() {
  int t;
  scanf("%d", &t);
  int n;
  while (t--) {
    scanf("%d", &n);
    scanf("%s", c + 1);
    int u = 0;
    for (int i = 1; i <= n; ++i) {
      bool fl = (c[i] == '1') && u;
      u ^= (c[i] - '0');
      if (i != 1) putchar(fl ? '-' : '+');
    }
    putchar('\n');
  }
}

First, We can divide $$$n$$$ cells into $$$\left\lceil\frac{n}{k}\right\rceil$$$ segments that except the last segment, all segments have length $$$k$$$. Then in each segment, the colors in it are pairwise different. It's easy to find any $$$a_i$$$ should be smaller than or equal to $$$\left\lceil\frac{n}{k}\right\rceil$$$.

Then we can count the number of $$$a_i$$$ which is equal to $$$\left\lceil\frac{n}{k}\right\rceil$$$. This number must be smaller than or equal to $$$n \bmod k$$$, which is the length of the last segment.

All $$$a$$$ that satisfies the conditions above is valid. We can construct a coloring using the method below:

First, we pick out all colors $$$i$$$ that $$$a_i=\left\lceil\frac{n}{k}\right\rceil$$$, then we use color $$$i$$$ to color the $$$j$$$-th cell in each segment.

Then we pick out all colors $$$i$$$ that $$$a_i<\left\lceil\frac{n}{k}\right\rceil-1$$$ and use these colors to color the rest of cells with cyclic order(i.e. color $$$j$$$-th cell of the first segment, of second the segment ... of the $$$\left\lceil\frac{n}{k}\right\rceil$$$ segment, and let $$$j++$$$. when one color is used up, we begin to use the next color)

At last, we pick out all colors $$$i$$$ that $$$a_i=\left\lceil\frac{n}{k}\right\rceil-1$$$, and color them with the cyclic order.

This method will always give a valid construction.

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

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    int fl = 0;
    for (int i = 1; i <= m; ++i) {
      int a;
      scanf("%d", &a);
      if (a == (n + k - 1) / k) ++fl;
      if (a > (n + k - 1) / k) fl = 1 << 30;
    }
    puts(fl <= (n - 1) % k + 1 ? "YES" : "NO");
  }
}

We define $$$f_i$$$ to mean that the maximum $$$x$$$ satisfies $$$s_{i-x+1}=s_{i-x+2}=...=s_{i}$$$.

It can be proved that for $$$x$$$ players, $$$f_{x-1}$$$ players are bound to lose and the rest have a chance to win. So the answer to the first $$$i$$$ battles is $$$ans_i=i-f_i+1$$$.

Next, we prove this conclusion. Suppose there are $$$n$$$ players and $$$n-1$$$ battles, and $$$s_{n-1}=1$$$, and there are $$$x$$$ consecutive $$$1$$$ at the end. If $$$x=n-1$$$, then obviously only the $$$n$$$-th player can win. Otherwise, $$$s_{n-1-x}$$$ must be 0. Consider the following facts:

1. Players $$$1$$$ to $$$x$$$ have no chance to win. If the player $$$i$$$ ($$$1\le i\le x$$$) can win, he must defeat the player whose temperature value is lower than him in the last $$$x$$$ battles. However, in total, only the $$$i-1$$$ player's temperature value is lower than his. Because $$$i-1<x$$$, the $$$i$$$-th player cannot win.

2. Players from $$$x+1$$$ to $$$n$$$ have a chance to win. For the player $$$i$$$ ($$$x+1\le i\le n$$$), we can construct: in the first $$$n-2-x$$$ battles, we let all players whose temperature value in $$$[x+1,n]$$$ except the player $$$i$$$ fight so that only one player will remain. In the $$$(n-1-x)$$$-th battle, we let the remaining player fight with the player $$$1$$$. Since $$$s_{n-1-x}=0$$$, the player $$$1$$$ will win. Then there are only the first $$$x$$$ players and the player $$$i$$$ in the remaining $$$x$$$ battles, so the player $$$i$$$ can win.

For $$$s_{n-1}=0$$$, the situation is similar and it will not be repeated here.

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

const int N = 300005;
int T, n, ps[2];
char a[N];

void solve() {
  scanf("%d %s", &n, a + 1);
  ps[0] = ps[1] = 0;
  for (int i = 1; i < n; ++i) {
    ps[a[i] - 48] = i;
    if (a[i] == '0')
      printf("%d ", ps[1] + 1);
    else
      printf("%d ", ps[0] + 1);
  }
  putchar('\n');
}
int main() {
  scanf("%d", &T);
  while (T--) solve();
  return 0;
}

#include <bits/stdc++.h>

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, m;
    scanf("%d %d", &n, &m);
    std::vector<std::vector<int>> A(n, std::vector<int>(m, 0));
    std::vector<int> sum(n, 0);
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        scanf("%d", &A[i][j]);
        sum[i] += A[i][j];
      }
    }
    int tot = 0;
    for (int i = 0; i < n; ++i) tot += sum[i];
    if (tot % n) {
      puts("-1");
      continue;
    }
    tot /= n;
    std::vector<std::tuple<int, int, int>> ans;
    std::vector<int> Vg, Vl;
    Vg.reserve(n), Vl.reserve(n);
    for (int j = 0; j < m; ++j) {
      for (int i = 0; i < n; ++i) {
        if (sum[i] > tot && A[i][j]) Vg.push_back(i);
        if (sum[i] < tot && !A[i][j]) Vl.push_back(i);
      }
      for (int i = 0; i < (int)std::min(Vl.size(), Vg.size()); ++i) {
        ++sum[Vl[i]], --sum[Vg[i]];
        ans.emplace_back(Vl[i], Vg[i], j);
      }
      Vl.clear(), Vg.clear();
    }
    printf("%d\n", (int)ans.size());
    for (auto [i, j, k] : ans) printf("%d %d %d\n", i + 1, j + 1, k + 1);
  }
  return 0;
}

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

const int N = 1e6 + 5;
int t[N * 2], nxt[N * 2], cnt, h[N];
int n, d;
void add(int x, int y) {
  t[++cnt] = y;
  nxt[cnt] = h[x];
  h[x] = cnt;
}
int a[N], b[N];
bool f[2][N];
void dfs1(int x, int fa, int dis) {
  a[dis] = x;
  if (dis > d)
    b[x] = a[dis - d];
  else
    b[x] = 1;
  for (int i = h[x]; i; i = nxt[i]) {
    if (t[i] == fa) continue;
    dfs1(t[i], x, dis + 1);
  }
}
void dfs2(int x, int fa, int tp) {
  bool u = 0;
  for (int i = h[x]; i; i = nxt[i]) {
    if (t[i] == fa) continue;
    dfs2(t[i], x, tp);
    u |= f[tp][t[i]];
  }
  f[tp][x] |= u;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> d;
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    add(x, y), add(y, x);
  }
  dfs1(1, 0, 1);
  for (int i = 0; i <= 1; i++) {
    int num;
    cin >> num;
    for (int j = 1; j <= num; j++) {
      int x;
      cin >> x;
      f[i][x] = 1, f[i ^ 1][b[x]] = 1;
    }
  }
  for (int i = 0; i <= 1; i++) dfs2(1, 0, i);
  int ans = 0;
  for (int i = 0; i <= 1; i++)
    for (int j = 2; j <= n; j++)
      if (f[i][j]) ans += 2;
  cout << ans;
  return 0;
}

Let $$$X=\max x$$$.

Think about what 'Repeat' is doing. Assuming the total damage is $$$x$$$ ($$$x$$$ is easy to calculate because it will be multiplied by $$$2$$$ after each 'Repeat' and be added after each 'Attack'). After repeating, each pig with a current HP of $$$w$$$ ($$$w > x$$$) will clone a pig with an HP of $$$w-x$$$.

Why? 'Repeat' will do what you just did again, so each original pig will certainly create a pig the same as it, and it will be attacked by $$$x$$$, so it can be considered that a pig with $$$w-x$$$ HP has been cloned.

Next, the problem is to maintain a multiset $$$S$$$, which supports: adding a number, subtracting $$$x$$$ for all numbers, and inserting each number after subtracting $$$x$$$. Find the number of elements in the final multiset.

$$$x$$$ in 'Repeat' after the first 'Attack' will multiply by $$$2$$$ every time, so it will exceed $$$X$$$ in $$$O(\log X)$$$ times. That is, only $$$O(\log X)$$$ 'Repeat' operations are effective. So we can maintain $$$S$$$ violently. Every time we 'Repeat', we take out all the numbers, then subtract and insert them again. If you use std::map to maintain it, the time complexity is $$$O((n+X)\log ^2X)$$$. It can pass F1. You can also use some ways to make the time complexity $$$O((n+X)\log X)$$$.