New School (Codeforces 1621E)
Tags: Greedy, binary search

You have decided to open a new school. You have already found $$$n$$$ teachers and $$$m$$$ groups of students. The $$$i$$$-th group of students consists of $$$k_i \geq 2$$$ students. You know age of each teacher and each student. The ages of teachers are $$$a_1, a_2, \ldots, a_n$$$ and the ages of students of the $$$i$$$-th group are $$$b_{i, 1}, b_{i, 2}, \ldots, b_{i, k_i}$$$.To start lessons you should assign the teacher to each group of students. Such assignment should satisfy the following requirements:  To each group exactly one teacher assigned.  To each teacher at most $$$1$$$ group of students assigned.  The average of students' ages in each group doesn't exceed the age of the teacher assigned to this group. The average of set $$$x_1, x_2, \ldots, x_k$$$ of $$$k$$$ integers is $$$\frac{x_1 + x_2 + \ldots + x_k}{k}$$$.Recently you have heard that one of the students will refuse to study in your school. After this, the size of one group will decrease by $$$1$$$ while all other groups will remain unchanged.You don't know who will refuse to study. For each student determine if you can start lessons in case of his refusal.Note, that it is not guaranteed that it is possible to start lessons before any refusal.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq m \leq n \leq 10^5$$$) — the number of teachers and the number of groups of students.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$) — the ages of teachers.The next $$$2m$$$ lines contains descriptions of groups. The first line of description of group contains a single integer $$$k_i$$$ ($$$2 \leq k_i \leq 10^5$$$) — the number of students in this group. The second line of description of group contains $$$k_i$$$ integers $$$b_{i, 1}, b_{i, 2}, \ldots, b_{i, k_i}$$$ ($$$1 \leq b_{i, j} \leq 10^5$$$) — the ages of students of this group.It is guaranteed that the total sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$ and that the total sum of $$$k_1 + k_2 + \ldots + k_m$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$

Output: For each test case output string of symbols $$$0$$$ and $$$1$$$ of length $$$k_1 + k_2 + \ldots + k_m$$$. The $$$i$$$-th symbol of this string should be equals $$$1$$$ if it is possible to start lessons in case of the $$$i$$$-th student refuse and it should be equals $$$0$$$ otherwise.Students are numbered by integers from $$$1$$$ to $$$k_1 + k_2 + \ldots + k_m$$$ in the order they appear in the input. Thus, students of the $$$1$$$-st group are numbered by integers $$$1$$$, $$$2$$$, $$$\ldots$$$, $$$k_1$$$, students of the $$$2$$$-nd group are numbered by integers $$$k_1 + 1$$$, $$$k_1 + 2$$$, $$$\ldots$$$, $$$k_1 + k_2$$$ and so on.

Note: In the first test case there is one group of students with average age $$$\frac{25+16+37}{3}=26$$$ and one teacher with age $$$30$$$. There exists only one assignment that allows to start lessons.If the student with age $$$16$$$ will refuse to study, the average age of students in this group will become $$$\frac{25+37}{2}=31$$$ so there won't be any assignment that allows to start lessons.In the second test case it is impossible to start lessons initially. However, if the $$$3$$$-rd student with age $$$111$$$ will refuse to study, the average ages of groups will become $$$\frac{4 + 5}{2}=4.5$$$ and $$$\frac{11+11}{2} = 11$$$ correspondingly. Then it is possible to assing the first group to the first teacher and the second group to the third teacher.

Sample Inputs:
2
1 1
30
3
25 16 37
4 2
9 12 12 6
2
4 5
3
111 11 11

Sample Outputs:
101
00100

Solution (Python):
twoPows = []
bb = 1
while bb < 100005:
    twoPows.append(bb)
    bb *= 2
twoPows.reverse()

def roundUp(num, den):
    return (num + den - 1) // den

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        (n, m) = readIntArr()
        a = readIntArr()
        b = []
        prevVals = []
        newVals = []
        for __ in range(m):
            k = int(input())
            temp = readIntArr()
            total = sum(temp)
            avg = roundUp(total, k)
            b.append(avg)
            for x in temp:
                prevVals.append(avg)
                newVals.append(roundUp(total - x, k - 1))
        for additionalVal in (-1, -1, 100005, 100005):
            a.append(additionalVal)
            b.append(additionalVal)
            n += 1
            m += 1
        a.sort(reverse=True)
        b.sort(reverse=True)
        p = []
        pl = []
        pr = []
        for i in range(m):
            if a[i] >= b[i]:
                p.append(0)
            else:
                p.append(1)
            if i + 1 < m:
                if a[i] >= b[i + 1]:
                    pl.append(0)
                else:
                    pl.append(1)
            if i - 1 >= 0:
                if a[i] >= b[i - 1]:
                    pr.append(0)
                else:
                    pr.append(1)
        for i in range(1, m - 1):
            p[i] += p[i - 1]
            pl[i] += pl[i - 1]
            pr[i] += pr[i - 1]
        p[m - 1] += p[m - 2]

        def q(l, r):
            if l == 0:
                return p[r]
            return p[r] - p[l - 1]

        def ql(l, r):
            if l == 0:
                return pl[r]
            return pl[r] - pl[l - 1]

        def qr(l, r):
            if l == 0:
                return pr[r]
            return pr[r] - pr[l - 1]
        ans = []
        for i in range(len(prevVals)):
            prevVal = prevVals[i]
            newVal = newVals[i]
            oldPos = newPos = -1
            for bb in twoPows:
                if oldPos + bb < m and b[oldPos + bb] >= prevVal:
                    oldPos += bb
                if newPos + bb < m and a[newPos + bb] >= newVal:
                    newPos += bb
            if oldPos < newPos:
                res = q(0, oldPos - 1) + ql(oldPos, newPos - 1) + q(newPos + 1, m - 1)
            else:
                res = q(0, newPos - 1) + qr(newPos, oldPos - 1) + q(oldPos + 1, m - 1)
            if res == 0:
                ans.append('1')
            else:
                ans.append('0')
        allans.append(''.join(ans))
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ansArr):
    print('! {}'.format(' '.join([str(x) for x in ansArr])))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
import heapq
import bisect
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())
    a = list(map(int, input().split()))
    heapq.heapify(a)
    for _ in range(n - m):
        heapq.heappop(a)
    a.sort()
    x = []
    u = []
    v = []
    sk = 0
    for i in range(m):
        k = int(input())
        b = list(map(int, input().split()))
        s = sum(b) - 1
        x.append((s // k, i))
        u.append((s, k))
        v.append(b)
        sk += k
    x.sort()
    y = []
    k = 0
    z = [0] * m
    for (i, j) in x:
        y.append(i)
        z[j] = k
        k += 1
    c = []
    for j in range(-1, 2):
        c0 = [0]
        for i in range(m):
            if not 0 <= i + j < m:
                c0.append(c0[-1] + 1)
            else:
                c0.append(c0[-1] + 1 if y[i] < a[i + j] else c0[-1])
        c.append(c0)
    (c0, c1, c2) = c
    ans0 = []
    for i in range(m):
        r = z[i]
        (s, k) = u[i]
        b = v[i]
        for j in range(k):
            x = (s - b[j]) // (k - 1)
            l = bisect.bisect_left(y, x)
            if l <= r:
                ans1 = '1' if x < a[l] else '0'
                if c1[l] ^ l or c1[m] - c1[r + 1] ^ m - r - 1:
                    ans1 = '0'
                if c2[r] - c2[l] ^ r - l:
                    ans1 = '0'
            else:
                ans1 = '1' if x < a[l - 1] else '0'
                if c1[r] ^ r or c1[m] - c1[l] ^ m - l:
                    ans1 = '0'
                if c0[l] - c0[r + 1] ^ l - r - 1:
                    ans1 = '0'
            ans0.append(ans1)
    ans.append(''.join(ans0))
sys.stdout.write('\n'.join(ans))

Solution (Python):
from sys import stdin, stdout
t = int(stdin.readline())
for _ in range(t):
    (n, m) = [int(x) for x in stdin.readline().split()]
    teachers = [int(x) for x in stdin.readline().split()]
    groups = []
    student_index = 0
    for i in range(m):
        size = int(stdin.readline())
        students = [int(x) for x in stdin.readline().split()]
        groups.append([sum(students) / size, []])
        for j in range(size):
            groups[-1][1].append((students[j], student_index))
            student_index += 1
    teachers.sort(reverse=True)
    teachers = teachers[:m]
    groups.sort(reverse=True)
    fail_match = []
    for i in range(m):
        if teachers[i] < groups[i][0]:
            fail_match.append(i)
    if len(fail_match) == 0:
        next_cannot = []
        current = -1
        for i in range(m - 1):
            next_cannot.append(current)
            if groups[i][0] > teachers[i + 1]:
                current = i
        next_cannot.append(current)
        answer = ['0'] * student_index
        for i in range(m):
            threshold = teachers[next_cannot[i] + 1]
            average = groups[i][0]
            size = len(groups[i][1])
            for (age, id) in groups[i][1]:
                if (average * size - age) / (size - 1) <= threshold:
                    answer[id] = '1'
        stdout.write(''.join(answer) + '\n')
    else:
        answer = ['0'] * student_index
        shift_up_fail = []
        for fail_index in fail_match:
            if fail_index == 0:
                shift_up_fail.append(fail_index)
            elif teachers[fail_index - 1] < groups[fail_index][0]:
                shift_up_fail.append(fail_index)
        if len(shift_up_fail) == 0:
            threshold = teachers[fail_match[-1]]
            for i in range(fail_match[0] + 1):
                average = groups[i][0]
                size = len(groups[i][1])
                for (age, id) in groups[i][1]:
                    if (average * size - age) / (size - 1) <= threshold:
                        answer[id] = '1'
        elif len(shift_up_fail) == 1:
            i = shift_up_fail[0]
            threshold = teachers[fail_match[-1]]
            average = groups[i][0]
            size = len(groups[i][1])
            for (age, id) in groups[i][1]:
                if (average * size - age) / (size - 1) <= threshold:
                    answer[id] = '1'
        stdout.write(''.join(answer) + '\n')