Tokitsukaze and Meeting (Codeforces 1677B)
Tags: Math, data structures

Tokitsukaze is arranging a meeting. There are $$$n$$$ rows and $$$m$$$ columns of seats in the meeting hall.There are exactly $$$n \cdot m$$$ students attending the meeting, including several naughty students and several serious students. The students are numerated from $$$1$$$ to $$$n\cdot m$$$. The students will enter the meeting hall in order. When the $$$i$$$-th student enters the meeting hall, he will sit in the $$$1$$$-st column of the $$$1$$$-st row, and the students who are already seated will move back one seat. Specifically, the student sitting in the $$$j$$$-th ($$$1\leq j \leq m-1$$$) column of the $$$i$$$-th row will move to the $$$(j+1)$$$-th column of the $$$i$$$-th row, and the student sitting in $$$m$$$-th column of the $$$i$$$-th row will move to the $$$1$$$-st column of the $$$(i+1)$$$-th row.For example, there is a meeting hall with $$$2$$$ rows and $$$2$$$ columns of seats shown as below:  There will be $$$4$$$ students entering the meeting hall in order, represented as a binary string "1100", of which '0' represents naughty students and '1' represents serious students. The changes of seats in the meeting hall are as follows:  Denote a row or a column good if and only if there is at least one serious student in this row or column. Please predict the number of good rows and columns just after the $$$i$$$-th student enters the meeting hall, for all $$$i$$$.

Input: The first contains a single positive integer $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — the number of test cases.For each test case, the first line contains two integers $$$n$$$, $$$m$$$ ($$$1 \leq n,m \leq 10^6$$$; $$$1 \leq n \cdot m \leq 10^6$$$), denoting there are $$$n$$$ rows and $$$m$$$ columns of seats in the meeting hall.The second line contains a binary string $$$s$$$ of length $$$n \cdot m$$$, consisting only of zeros and ones. If $$$s_i$$$ equal to '0' represents the $$$i$$$-th student is a naughty student, and $$$s_i$$$ equal to '1' represents the $$$i$$$-th student is a serious student.It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each test case, print a single line with $$$n \cdot m$$$ integers — the number of good rows and columns just after the $$$i$$$-th student enters the meeting hall.

Note: The first test case is shown in the statement.After the $$$1$$$-st student enters the meeting hall, there are $$$2$$$ good rows and columns: the $$$1$$$-st row and the $$$1$$$-st column.After the $$$2$$$-nd student enters the meeting hall, there are $$$3$$$ good rows and columns: the $$$1$$$-st row, the $$$1$$$-st column and the $$$2$$$-nd column.After the $$$3$$$-rd student enters the meeting hall, the $$$4$$$ rows and columns are all good.After the $$$4$$$-th student enters the meeting hall, there are $$$3$$$ good rows and columns: the $$$2$$$-nd row, the $$$1$$$-st column and the $$$2$$$-nd column.

Sample Inputs:
3
2 2
1100
4 2
11001101
2 4
11001101

Sample Outputs:
2 3 4 3
2 3 4 3 5 4 6 5
2 3 3 3 4 4 4 5

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
T = int(input())
for _ in range(T):
    (n, m) = map(int, input().split())
    S = input()
    (dp, dpbefore) = ([0] * m, [0] * m)
    cols = set()
    R = []
    good = 0
    for r in range(n):
        for c in range(m):
            i = r * m + c
            s = S[i]
            if s == '1':
                cols.add(c)
                good += 1
            if i - m >= 0 and S[i - m] == '1':
                good -= 1
            dp[c] = dpbefore[c] + (1 if good != 0 else 0)
            R.append(dp[c] + len(cols))
        (dp, dpbefore) = (dpbefore, dp)
    print(' '.join((str(r) for r in R)))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
ans = []
for _ in range(t):
    (n, m) = map(int, input().split())
    l = n * m
    s = list(input().rstrip())
    x = [0]
    for i in s:
        x.append(x[-1] + (i & 1))
    (ans0, cnt) = ([0] * l, [0] * l)
    ok = [0] * m
    c = 0
    for i in range(l):
        if s[i] & 1 and (not ok[i % m]):
            ok[i % m] = 1
            c += 1
        cnt[i] = c
        ans0[i] = min(x[i + 1] ^ x[max(0, i + 1 - m)], 1)
        if i >= m:
            ans0[i] += ans0[i - m]
    for i in range(l):
        ans0[i] += cnt[i]
    ans.append(' '.join(map(str, ans0)))
sys.stdout.write('\n'.join(ans))

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):
    (m, n) = map(int, input().split())
    s = input().decode('utf-8')[:m * n]
    accu = [0] * (m * n + 1)
    for i in range(m * n):
        accu[i] = accu[i - 1] + int(s[i])
    rows = [0] * (m * n)
    cols = [0] * (m * n)
    for i in range(n):
        if accu[i] > 0:
            rows[i] = 1
    for i in range(n, m * n):
        if accu[i] > accu[i - n]:
            rows[i] = rows[i - n] + 1
        else:
            rows[i] = rows[i - n]
    colshave = [False] * n
    for i in range(m * n):
        if s[i] == '1' and (not colshave[i % n]):
            cols[i] = cols[i - 1] + 1
            colshave[i % n] = True
        else:
            cols[i] = cols[i - 1]
    ans = [rows[i] + cols[i] for i in range(m * n)]
    print(*ans)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1