Colorful Constructive (Codeforces 1893D)
Tags: Greedy, data structures

You have $$$n$$$ colored cubes, the $$$i$$$-th cube has color $$$a_i$$$.You need to distribute all the cubes on shelves. There are a total of $$$m$$$ shelves, the $$$i$$$-th shelf can hold $$$s_i$$$ cubes. Also, $$$s_1 + s_2 + \ldots + s_m = n$$$.Suppose on a shelf of size $$$k$$$ there are cubes of colors $$$c_1, c_2, \ldots, c_k$$$, in this order. Then we define the colorfulness of the shelf as the minimum distance between two different cubes of the same color on the shelf. If all the cubes on the shelf have different colors, then the colorfulness is considered to be equal to the size of the shelf, that is, the number $$$k$$$.More formally, the colorfulness of $$$c_1, c_2, \ldots, c_k$$$ is defined as follows: If all the colors $$$c_1, c_2, \ldots, c_k$$$ are different, the colorfulness is considered to be $$$k$$$. Otherwise, the colorfulness is considered to be the smallest integer $$$x \geq 1$$$ such that there exists an index $$$i$$$ $$$(1 \le i \le k - x)$$$ such that $$$c_i = c_{i+x}$$$.For each shelf, you are given the minimum required colorfulness, that is, you are given numbers $$$d_1, d_2, \ldots, d_m$$$, which mean that shelf $$$i$$$ must have a colorfulness $$$\geq d_i$$$ for all $$$i$$$.Distribute the available cubes among the shelves to ensure the required colorfulness, or report that it is impossible.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — the number of test cases. The description of the test cases follows.The first line of each test case contains two integers $$$n, m$$$ $$$(1 \leq m \leq n \leq 2 \cdot 10^5)$$$ — the number of cubes and the number of shelves to distribute them to.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq n)$$$ — the colors of the cubes.The third line of each test case contains $$$m$$$ integers $$$s_1, s_2, \ldots, s_m$$$ $$$(1 \leq s_i \leq n)$$$ — the sizes of the shelves. It's guaranteed, that $$$s_1 + \ldots + s_m = n$$$.The fourth line of each test case contains $$$m$$$ integers $$$d_1, d_2, \ldots, d_m$$$ $$$(1 \leq d_i \leq s_i)$$$ — the minimum required colorfulness of the shelves.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, if it is impossible to distribute the cubes on the shelves satisfying all the requirements, output a single number $$$-1$$$. Otherwise, output $$$m$$$ lines, where the $$$i$$$-th line should contain $$$s_i$$$ numbers representing the colors of the cubes on the $$$i$$$-th shelf, in the appropriate order.


Sample Inputs:
6
10 3
1 1 1 1 2 2 2 3 3 4
6 2 2
4 1 1
8 2
7 7 7 7 8 8 8 8
4 4
2 2
5 1
5 4 3 2 1
5
3
7 3
1 2 2 2 2 3 4
1 2 4
1 2 4
12 7
6 6 6 6 6 6 6 6 6 7 8 9
2 2 2 2 2 1 1
1 2 2 2 1 1 1
20 2
11 20 15 6 8 18 12 16 8 20 10 12 3 12 20 11 15 8 17 17
8 12
3 5

Sample Outputs:
1 3 4 2 1 3 
1 1 
2 2 
8 7 8 7 
8 7 8 7 
2 4 5 3 1 
-1
6 6 
7 6 
8 6 
9 6 
6 6 
6 
6 
12 17 20 15 8 20 16 11 
15 20 17 12 10 8 3 18 12 11 8 6

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush
import sys
import io
import os
MOD = 998244353
inf = 1 << 60

def solve():
    (N, M) = read_int_tuple()
    A = read_int_list()
    cnt = defaultdict(int)
    for x in A:
        cnt[x] += 1
    (S, D) = (read_int_list(), read_int_list())
    hp = []
    for (x, c) in cnt.items():
        heappush(hp, (-c, x))
    res = [[-1] * s for s in S]
    for (cur, s, d) in zip(res, S, D):
        for i in range(0, s, d):
            cc = min(d, s - i)
            for j in range(cc):
                if not hp:
                    print(-1)
                    return
                cur[i + j] = heappop(hp)[1]
            for j in range(cc):
                x = cur[i + j]
                cnt[x] -= 1
                if cnt[x]:
                    heappush(hp, (-cnt[x], x))
    for row in res:
        print(*row)

def main():
    if 'AW' in os.environ.get('COMPUTERNAME', ''):
        test_no = 1
        f = open(os.path.dirname(__file__) + f'\\in{test_no}.txt', 'r')
        global input
        input = lambda : f.readline().rstrip('\r\n')
    T = read_int()
    for t in range(T):
        solve()
BUFSIZE = 8192

class FastIO(io.IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = 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):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

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

def read_ints_minus_one():
    return [int(x) - 1 for x in input().split()]

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

def read_encode_str(d=97):
    return [ord(x) - d for x in input()]

def read_graph(n: int, m: int, d=1):
    g = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = map(int, input().split())
        g[u - d].append(v - d)
        g[v - d].append(u - d)
    return g

def read_grid(m: int):
    return [input() for _ in range(m)]

def read_int():
    return int(input())
read_str = input
if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush
import sys
import io
import os
MOD = 998244353
inf = 1 << 60

def solve():
    (N, M) = read_int_tuple()
    A = read_int_list()
    cnt = defaultdict(int)
    for x in A:
        cnt[x] += 1
    (S, D) = (read_int_list(), read_int_list())
    hp = []
    for (x, c) in cnt.items():
        heappush(hp, (-c, x))
    res = [[-1] * s for s in S]
    for (cur, s, d) in zip(res, S, D):
        for i in range(0, s, d):
            cc = min(d, s - i)
            tmp = []
            for j in range(cc):
                if not hp:
                    print(-1)
                    return
                cur[i + j] = x = heappop(hp)[1]
                cnt[x] -= 1
                if cnt[x]:
                    tmp.append((-cnt[x], x))
            for tt in tmp:
                heappush(hp, tt)
    for row in res:
        print(*row)

def main():
    if 'AW' in os.environ.get('COMPUTERNAME', ''):
        test_no = 1
        f = open(os.path.dirname(__file__) + f'\\in{test_no}.txt', 'r')
        global input
        input = lambda : f.readline().rstrip('\r\n')
    T = read_int()
    for t in range(T):
        solve()
BUFSIZE = 8192

class FastIO(io.IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = 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):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

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

def read_ints_minus_one():
    return [int(x) - 1 for x in input().split()]

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

def read_encode_str(d=97):
    return [ord(x) - d for x in input()]

def read_graph(n: int, m: int, d=1):
    g = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = map(int, input().split())
        g[u - d].append(v - d)
        g[v - d].append(u - d)
    return g

def read_grid(m: int):
    return [input() for _ in range(m)]

def read_int():
    return int(input())
read_str = input
if __name__ == '__main__':
    main()

Solution (Python):
import os, sys
from io import BytesIO, IOBase
from typing import *
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')
import heapq

def main():
    (n, m) = map(int, input().split())
    a = list(map(int, input().split()))
    s = list(map(int, input().split()))
    d = list(map(int, input().split()))
    cnt = [0] * (n + 1)
    maxheap = []
    for num in a:
        cnt[num] += 1
    for (i, c) in enumerate(cnt):
        if c == 0:
            continue
        heapq.heappush(maxheap, (-c, i))
    ans = [[0] * s[i] for i in range(m)]
    for i in range(m):
        for j in range(s[i]):
            if j >= d[i] and cnt[ans[i][j - d[i]]] > 0:
                heapq.heappush(maxheap, (-cnt[ans[i][j - d[i]]], ans[i][j - d[i]]))
            if len(maxheap) == 0:
                return print(-1)
            (_, num) = heapq.heappop(maxheap)
            ans[i][j] = num
            cnt[num] -= 1
        for j in range(s[i], s[i] + d[i]):
            if cnt[ans[i][j - d[i]]] > 0:
                heapq.heappush(maxheap, (-cnt[ans[i][j - d[i]]], ans[i][j - d[i]]))
    for i in range(m):
        print(*ans[i])
if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        main()