Multiple Testcases (Codeforces 1342D)
Tags: Greedy, two pointers

So you decided to hold a contest on Codeforces. You prepared the problems: statements, solutions, checkers, validators, tests... Suddenly, your coordinator asks you to change all your tests to multiple testcases in the easiest problem!Initially, each test in that problem is just an array. The maximum size of an array is $$$k$$$. For simplicity, the contents of arrays don't matter. You have $$$n$$$ tests — the $$$i$$$-th test is an array of size $$$m_i$$$ ($$$1 \le m_i \le k$$$).Your coordinator asks you to distribute all of your arrays into multiple testcases. Each testcase can include multiple arrays. However, each testcase should include no more than $$$c_1$$$ arrays of size greater than or equal to $$$1$$$ ($$$\ge 1$$$), no more than $$$c_2$$$ arrays of size greater than or equal to $$$2$$$, $$$\dots$$$, no more than $$$c_k$$$ arrays of size greater than or equal to $$$k$$$. Also, $$$c_1 \ge c_2 \ge \dots \ge c_k$$$.So now your goal is to create the new testcases in such a way that:   each of the initial arrays appears in exactly one testcase;  for each testcase the given conditions hold;  the number of testcases is minimum possible. Print the minimum possible number of testcases you can achieve and the sizes of arrays included in each testcase.

Input: The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 2 \cdot 10^5$$$) — the number of initial tests and the limit for the size of each array.The second line contains $$$n$$$ integers $$$m_1, m_2, \dots, m_n$$$ ($$$1 \le m_i \le k$$$) — the sizes of the arrays in the original tests.The third line contains $$$k$$$ integers $$$c_1, c_2, \dots, c_k$$$ ($$$n \ge c_1 \ge c_2 \ge \dots \ge c_k \ge 1$$$); $$$c_i$$$ is the maximum number of arrays of size greater than or equal to $$$i$$$ you can have in a single testcase.

Output: In the first line print a single integer $$$ans$$$ ($$$1 \le ans \le n$$$) — the minimum number of testcases you can achieve.Each of the next $$$ans$$$ lines should contain the description of a testcase in the following format:$$$t$$$ $$$a_1$$$ $$$a_2$$$ $$$\dots$$$ $$$a_{t}$$$ ($$$1 \le t\le n$$$) — the testcase includes $$$t$$$ arrays, $$$a_i$$$ is the size of the $$$i$$$-th array in that testcase.Each of the initial arrays should appear in exactly one testcase. In particular, it implies that the sum of $$$t$$$ over all $$$ans$$$ testcases should be equal to $$$n$$$.Note that the answer always exists due to $$$c_k \ge 1$$$ (and therefore $$$c_1 \ge 1$$$).If there are multiple answers, you can output any one of them.

Note: In the first example there is no way to distribute the tests into less than $$$3$$$ testcases. The given answer satisfies the conditions: each of the testcases includes no more than $$$4$$$ arrays of size greater than or equal to $$$1$$$ and no more than $$$1$$$ array of sizes greater than or equal to $$$2$$$ and $$$3$$$.Note that there are multiple valid answers for this test. For example, testcases with sizes $$$[[2], [1, 2], [3]]$$$ would also be correct.However, testcases with sizes $$$[[1, 2], [2, 3]]$$$ would be incorrect because there are $$$2$$$ arrays of size greater than or equal to $$$2$$$ in the second testcase.Note the difference between the third and the fourth examples. You can include up to $$$5$$$ arrays of size greater than or equal to $$$1$$$ in the third example, so you can put all arrays into a single testcase. And you can have only up to $$$1$$$ array in the fourth example. Thus, every array should be included in a separate testcase.

Sample Inputs:
4 3
1 2 2 3
4 1 1

6 10
5 8 1 10 8 7
6 6 4 4 3 2 2 2 1 1

5 1
1 1 1 1 1
5

5 1
1 1 1 1 1
1

Sample Outputs:
3
1 2
2 1 3
1 2

2
3 8 5 7
3 10 8 1

1
5 1 1 1 1 1

5
1 1
1 1
1 1
1 1
1 1

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, k) = readInts()
    (m, c) = (readList(), readList())
    cnt = [0] * (k + 1)
    for i in range(n):
        cnt[m[i]] += 1
    ps = [0] * (k + 1)
    ps[k] = cnt[k]
    for i in range(k - 1, 0, -1):
        ps[i] = cnt[i] + ps[i + 1]
    b = max([(ps[i + 1] + c[i] - 1) // c[i] for i in range(k)])
    print(b)
    ans = [[] for _ in range(b)]
    j = 0
    for i in range(k, 0, -1):
        while cnt[i]:
            ans[j].append(str(i))
            cnt[i] -= 1
            j += 1
            j %= b
    for arr in ans:
        print(len(arr), ' '.join(arr))
    return
solve()

Solution (Python):
import heapq
import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
m = list(map(int, input().split()))
c = [0] + list(map(int, input().split()))
h = []
inf = 1919810
heapq.heappush(h, (inf, -1))
m.sort(reverse=True)
ans = 0
x = []
for i in m:
    if h[0][0] >= c[i]:
        ans += 1
        x.append([0])
        (c0, j) = (0, ans)
    else:
        (c0, j) = heapq.heappop(h)
    c0 += 1
    x[j - 1].append(i)
    heapq.heappush(h, (c0, j))
for i in range(ans):
    x[i][0] = len(x[i]) - 1
    x[i] = ' '.join(map(str, x[i]))
print(ans)
print('\n'.join(x))

Solution (Python):
MOD = 10 ** 9 + 7

def main():
    for _ in inputt(1):
        (n, k) = inputi()
        (M, C) = inputl(2)
        M = sorted(M)
        mc = Counter(M)
        mck = sorted(mc, reverse=True)
        ma = 0
        t = 0
        for k in mck:
            t += mc[k]
            ma = max(ma, ceil(t / C[k - 1]))
        print(ma)
        for i in range(ma):
            m = M[i:n:ma]
            print(len(m), *m)
from math import *
from heapq import *
from itertools import *
from functools import reduce, lru_cache, partial
from collections import Counter, defaultdict
import re, copy, operator, cmath
import sys, io, os, builtins
sys.setrecursionlimit(1000)
BUFSIZE = 8192

class FastIO(io.IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = io.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(io.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')

def print(*args, **kwargs):
    if args:
        sys.stdout.write(str(args[0]))
        split = kwargs.pop('split', ' ')
        for arg in args[1:]:
            sys.stdout.write(split)
            sys.stdout.write(str(arg))
    sys.stdout.write(kwargs.pop('end', '\n'))

def debug(*args, **kwargs):
    print('debug', *args, **kwargs)
    sys.stdout.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip()
inputt = lambda t=0: range(t) if t else range(int(input()))
inputs = lambda : input().split()
inputi = lambda : map(int, inputs())
inputl = lambda t=0, k=lambda : list(inputi()): [k() for _ in range(t)] if t else list(k())

def len(a):
    if isinstance(a, range):
        return -((a.start - a.stop) // a.step)
    return builtins.len(a)

def bisect_left(a, x, key=None, lo=0, hi=None):
    if lo < 0:
        lo = 0
    if hi == None:
        hi = len(a)
    if key == None:
        key = do_nothing
    while lo < hi:
        mid = (lo + hi) // 2
        if key(a[mid]) < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

def bisect_right(a, x, key=None, lo=0, hi=None):
    if lo < 0:
        lo = 0
    if hi == None:
        hi = len(a)
    if key == None:
        key = do_nothing
    while lo < hi:
        mid = (lo + hi) // 2
        if x < key(a[mid]):
            hi = mid
        else:
            lo = mid + 1
    return lo

def insort_left(a, x, key=None, lo=0, hi=None):
    lo = bisect_left(a, x, key, lo, hi)
    a.insert(lo, x)

def insort_right(a, x, key=None, lo=0, hi=None):
    lo = bisect_right(a, x, key, lo, hi)
    a.insert(lo, x)
do_nothing = lambda x: x
bisect = bisect_right
insort = insort_right

def index(a, x, default=None, key=None, lo=0, hi=None):
    if lo < 0:
        lo = 0
    if hi == None:
        hi = len(a)
    if key == None:
        key = do_nothing
    i = bisect_left(a, x, key, lo, hi)
    if lo <= i < hi and key(a[i]) == x:
        return a[i]
    if default != None:
        return default
    raise ValueError

def find_lt(a, x, default=None, key=None, lo=0, hi=None):
    if lo < 0:
        lo = 0
    if hi == None:
        hi = len(a)
    i = bisect_left(a, x, key, lo, hi)
    if lo < i <= hi:
        return a[i - 1]
    if default != None:
        return default
    raise ValueError

def find_le(a, x, default=None, key=None, lo=0, hi=None):
    if lo < 0:
        lo = 0
    if hi == None:
        hi = len(a)
    i = bisect_right(a, x, key, lo, hi)
    if lo < i <= hi:
        return a[i - 1]
    if default != None:
        return default
    raise ValueError

def find_gt(a, x, default=None, key=None, lo=0, hi=None):
    if lo < 0:
        lo = 0
    if hi == None:
        hi = len(a)
    i = bisect_right(a, x, key, lo, hi)
    if lo <= i < hi:
        return a[i]
    if default != None:
        return default
    raise ValueError

def find_ge(a, x, default=None, key=None, lo=0, hi=None):
    if lo < 0:
        lo = 0
    if hi == None:
        hi = len(a)
    i = bisect_left(a, x, key, lo, hi)
    if lo <= i < hi:
        return a[i]
    if default != None:
        return default
    raise ValueError

class Tree:

    def __init__(n):
        self._n = n
        self._conn = [[] for _ in range(n)]
        self._list = [0] * n

    def connect(a, b):
        pass

class Sieve:

    def __init__(self):
        self._n = 6
        self._list = [2, 3, 5, 7, 11, 13]

    def extend(self, n):
        pass
sieve = Sieve()

def isprime(n):
    pass

def prime(n):
    pass

def factorint(n):
    factordict = defaultdict(int)
    for i in sieve:
        if n <= i * i:
            break
        while not n % i:
            factordict[i] += 1
            n //= i
    if n != 1:
        factordict[n] += 1
    return factordict
if __name__ == '__main__':
    main()