結果

問題 No.2025 Select $k$-th Submultiset
コンテスト
ユーザー hahho
提出日時 2022-07-24 07:47:35
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,954 bytes
コンパイル時間 356 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 97,920 KB
最終ジャッジ日時 2024-07-05 23:49:13
合計ジャッジ時間 6,186 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys


class Array2dView:
    def __init__(self, arr, i_indices, j_indices):
        self.arr = arr
        self.i_indices = i_indices
        self.j_indices = j_indices
        self.n = len(i_indices)
        self.m = len(j_indices)

    def _get_view(self, i, j):
        i = self.i_indices[i]
        j = self.j_indices[j]
        return Array2dView(self.arr, i, j)

    def get_ind(self, i, j):
        return self.i_indices[i] + self.j_indices[j]

    def __getitem__(self, index):
        i, j = index
        try:
            return self.arr[self.get_ind(i, j)]
        except TypeError:
            return self._get_view(i, j)

    def __setitem__(self, index, value):
        i, j = index
        try:
            self.arr[self.get_ind(i, j)] = value
        except TypeError:
            x = self._get_view(i, j)
            for i in x.i_indices:
                for j in x.j_indices:
                    self.arr[i + j] = value

    def __iter__(self):
        for i in self.i_indices:
            for j in self.j_indices:
                yield self.arr[i + j]

    def __reversed__(self):
        for i in reversed(self.i_indices):
            for j in reversed(self.j_indices):
                yield self.arr[i + j]

    def __str__(self):
        m = max(len(str(v)) for v in self)
        res = [''] * len(self.i_indices)
        row = [''] * (len(self.j_indices) + 2)
        for ri, i in enumerate(self.i_indices):
            if ri == 0:
                row[0] = '['
            else:
                row[0] = ' '
            if ri == len(self.i_indices) - 1:
                row[-1] = ']\n'
            for rj, j in enumerate(self.j_indices):
                row[rj + 1] = f'{str(self.arr[i + j]):>{m + 1}}'
            res[ri] = ''.join(row)
        return '\n'.join(res)

    def copy(self):
        return Array2d(len(self.i_indices), len(self.j_indices), list(self))


class Array2d:
    def __init__(self, n, m, arr):
        self.n = n
        self.m = m
        self.arr = arr

    @classmethod
    def full(cls, n, m, fill_value):
        return cls(n, m, [fill_value] * (n * m))

    @classmethod
    def from_list(cls, lst):
        n, m = len(lst), len(lst[0])
        arr = [lst[0]] * (n * m)
        k = 0
        for row in lst:
            for v in row:
                arr[k] = v
                k += 1
        return cls(n, m, arr)

    def _get_view(self, i, j):
        i = tuple(range(0, self.n * self.m, self.m))[i]
        j = tuple(range(self.m))[j]
        return Array2dView(self.arr, i, j)

    def get_ind(self, i, j):
        return i * self.m + j

    def __getitem__(self, index):
        try:
            return self.arr[self.get_ind(*index)]
        except TypeError:
            return self._get_view(*index)

    def __setitem__(self, index, value):
        try:
            self.arr[self.get_ind(*index)] = value
        except TypeError:
            x = self._get_view(*index)
            for i in x.i_indices:
                for j in x.j_indices:
                    self.arr[i + j] = value

    def __iter__(self):
        return iter(self.arr)

    def __reversed__(self):
        return reversed(self.arr)

    def __str__(self):
        m = max(len(str(v)) for v in self)
        res = [''] * self.n
        row = [''] * (self.m + 2)
        for i in range(self.n):
            if i == 0:
                row[0] = '['
            else:
                row[0] = ' '
            if i == self.n - 1:
                row[-1] = ']\n'
            for j in range(self.m):
                row[j + 1] = f'{str(self.arr[i * self.m + j]):>{m + 1}}'
            res[i] = ''.join(row)
        return '\n'.join(res)

    def __eq__(self, other):
        return self.arr == other.arr

    def copy(self):
        return self.__class__(self.n, self.m, self.arr[:])

    @property
    def t(self):
        arr = [self.arr[0]] * (len(self.arr))
        x = 0
        for i in range(self.n):
            for j in range(self.m):
                arr[j * self.n + i] = self.arr[x]
                x += 1
        return self.__class__(self.m, self.n, arr)


read = sys.stdin.buffer.read


def max2(x, y):
    return x if x > y else y


mm = map(int, read().split())

n, l = next(mm), next(mm)
c = [v for i, v in zip(range(n), mm)]

# dp[i][j] := c[i:]を使って長さj未満の部分列を作る場合の通り数
dp = Array2d.full(n + 1, l + 2, 0)
for i in range(1, l + 2):
    dp[n, i] = 1

for i in reversed(range(n)):
    for j in range(1, l + 2):
        dp[i, j] = dp[i + 1, j] - dp[i + 1, max2(j - c[i] - 1, 0)] + dp[i, j - 1]
m = next(mm)

for _ in range(m):
    k = next(mm) - 1
    if k >= dp[0, l + 1] - dp[0, l]:
        print(-1)
        continue
    res = [0] * n
    r = l + 1
    for i in range(n):
        offset = dp[i + 1, max2(r - c[i] - 1, 0)]
        while dp[i + 1, r - 1] - offset > k:
            r -= 1
            res[i] += 1
        k -= dp[i + 1, r - 1] - offset
    print(*res)
0