#1008136 (PyPy3) No.2870 Dice Making

提出ソース
結果

問題	No.2870 Dice Making
ユーザー	kainade
提出日時	2024-09-07 14:26:10
言語	PyPy3 (7.3.15)
結果	AC
実行時間	69 ms / 2,000 ms
コード長	22,549 bytes
コンパイル時間	688 ms
コンパイル使用メモリ	82,552 KB
実行使用メモリ	74,000 KB
最終ジャッジ日時	2024-09-07 14:26:14
合計ジャッジ時間	3,483 ms
ジャッジサーバーID （参考情報）	judge4 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	66 ms 74,000 KB
testcase_01	AC	67 ms 73,536 KB
testcase_02	AC	67 ms 73,804 KB
testcase_03	AC	69 ms 73,944 KB
testcase_04	AC	66 ms 72,900 KB
testcase_05	AC	69 ms 73,152 KB
testcase_06	AC	68 ms 73,000 KB
testcase_07	AC	66 ms 73,440 KB
testcase_08	AC	67 ms 73,360 KB
testcase_09	AC	65 ms 73,604 KB
testcase_10	AC	66 ms 73,016 KB
testcase_11	AC	65 ms 72,880 KB
testcase_12	AC	67 ms 72,664 KB
testcase_13	AC	64 ms 72,816 KB
testcase_14	AC	64 ms 72,608 KB
testcase_15	AC	65 ms 73,804 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
def main():
    N,K=MI()
    if N%K:
        print(-1)
    else:
        r=N//K
        ans=[1]*r + [2]*(N-r)
        print(*ans)






# user config
############
DEBUG_MODE=1
############


# import
import sys
import itertools
import bisect
import math
from collections import *
from functools import cache
from heapq import *

# alias
DD = defaultdict
BSL = bisect.bisect_left
BSR = bisect.bisect_right

# config
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

# input
def II(): return int(input())
def IS(): return input()[:-1]
def MI(): return map(int,input().split())
def LM(): return list(MI())
def LL(n): return [LM() for _ in range(n)]
def MI_1(): return map(lambda x:int(x)-1,input().split())
def LM_1(): return list(MI_1())
def LL_1(n): return [LM_1() for _ in range(n)]
def ALPHABET_TO_NUM(string, upper=False): return list(map(lambda elm:ord(elm)-ord("A") if upper else ord(elm)-ord("a"), string))


# functions
def DB(*args,**kwargs):
    global DEBUG_MODE
    if not DEBUG_MODE:
        return
    if args:
        print(*args)
        return
    for name, value in kwargs.items():
        print(f"{name} : {value}")

def bit_count(num):
    length = num.bit_length()
    res = 0
    for i in range(length):
        if num >> i & 1:
            res += 1
    return res

def popcount64(n):
    # 63桁まで高速に動く.64桁まで正常に動く.
    c=(n&0x5555555555555555)+((n>>1)&0x5555555555555555)
    c=(c&0x3333333333333333)+((c>>2)&0x3333333333333333)
    c=(c&0x0f0f0f0f0f0f0f0f)+((c>>4)&0x0f0f0f0f0f0f0f0f)
    c=(c&0x00ff00ff00ff00ff)+((c>>8)&0x00ff00ff00ff00ff)
    c=(c&0x0000ffff0000ffff)+((c>>16)&0x0000ffff0000ffff)
    c=(c&0x00000000ffffffff)+((c>>32)&0x00000000ffffffff)
    return c

def argmax(*args):
    if len(args) == 1 and hasattr(args[0], '__iter__'):
        lst = args[0]
    else:
        lst = args
    return lst.index(max(lst))

def argmin(*args):
    if len(args) == 1 and hasattr(args[0], '__iter__'):
        lst = args[0]
    else:
        lst = args
    return lst.index(min(lst))

def prefix_op(lst, op=lambda x,y:x+y, e=0):
    N = len(lst)
    res = [e]*(N+1)
    for i in range(N):
        res[i+1] = op(res[i], lst[i])
    return res

def suffix_op(lst, op=lambda x,y:x+y, e=0):
    N = len(lst)
    res = [e]*(N+1)
    for i in range(N):
        res[N-1-i] = op(lst[N-1-i], res[N-i])
    return res

def sigma_LinearFunc(coeff1, coeff0, left, right, MOD=None):
    """
    coeff1*x + coeff0
    の x = [left, right] の和を求める.
    MODで計算したい場合、区間の引数をMOD取った上で代入しても良い.
    そのとき、left > right となってもよい. 
    """
    if MOD:
        # MODが素数でない場合にも対応するように、和公式を適応後に剰余を計算.
        return ((coeff0%MOD*((right-left+1)%MOD)%MOD) + (coeff1%MOD*((left+right)*(right-left+1)//2%MOD)%MOD))%MOD
    return coeff0*(right-left+1) + coeff1*(left+right)*(right-left+1)//2

def find_divisors(n):
    divs_small, divs_big = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            divs_small.append(i)
            divs_big.append(n // i)
        i += 1
    if divs_big[-1] == divs_small[-1]:
        divs_big.pop()
    for e in reversed(divs_big):
        divs_small.append(e)
    return divs_small

def prime_factorization(n):
    n_intact = n
    ret = []
    i = 2
    while i * i <= n_intact:
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                n //= i
                cnt += 1
            ret.append((i,cnt))
        i += 1
    if n != 1: ret.append((n,1))
    return ret



""" 矩形の二次元配列を扱う諸関数 """
def copy_table(table):
    H,W = len(table), len(table[0])
    res = []
    for i in range(H):
        res.append([])
        for j in range(W):
            res[-1].append(table[i][j])
    return res

def sum_table(table, MOD=None):
    H,W = len(table), len(table[0])
    res = 0
    for i in range(H):
        for j in range(W):
            res += table[i][j]
        if MOD:
            res %= MOD
    return res

def transpose_table(table):
    H,W = len(table), len(table[0])
    res = [[None]*H for _ in range(W)]
    for i in range(H):
        for j in range(W):
            res[j][i] = table[i][j]
    return res

def convert_table_to_bit(table, letter1="#", rev=False):
    H,W = len(table), len(table[0])
    res = []
    for h in range(H):
        rowBit = 0
        for w in range(W):
            if rev:
                if table[h][w] == letter1:
                    rowBit += 2**w
            else:
                if table[h][W-w-1] == letter1:
                    rowBit += 2**w
        res.append(rowBit)
    return res

def rotate_table_cc(S): return list(zip(*S))[::-1]
def rotate_table_c(S): return list(zip(*S[::-1]))


def mul_matrix(A, B, mod):
    N = len(A)
    K = len(A[0])
    M = len(B[0])

    res = [[0 for _ in range(M)] for _ in range(N)]

    for i in range(N) :
        for j in range(K) :
            for k in range(M) :
                res[i][k] += A[i][j] * B[j][k] 
                res[i][k] %= mod
    return res

def pow_matrix(mat, exp, mod):
    N = len(mat)
    res = [[1 if i == j else 0 for i in range(N)] for j in range(N)]
    while exp > 0 :
        if exp%2 == 1 :
            res = mul_matrix(res, mat, mod)
        mat = mul_matrix(mat, mat, mod)
        exp //= 2
    return res

def compress(lst):
    D = {e:i for i,e in enumerate(sorted(set(lst)))}
    return [D[e] for e in lst]

def highDimCompress(lst):
    #(x,y)の配列や,(x,y,z)の配列が与えられたとき,軸ごとに座圧する.
    return list(zip(*list(map(compress,list(zip(*lst))))))



#classes

# https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.py
from bisect import bisect_left, bisect_right
from typing import Generic, Iterable, Iterator, List, Tuple, TypeVar, Optional
T = TypeVar('T')
class SortedSet(Generic[T]):
    BUCKET_RATIO = 16
    SPLIT_RATIO = 24
    
    def __init__(self, a: Iterable[T] = []) -> None:
        "Make a new SortedSet from iterable. / O(N) if sorted and unique / O(N log N)"
        a = list(a)
        n = self.size = len(a)
        if any(a[i] > a[i + 1] for i in range(n - 1)):
            a.sort()
        if any(a[i] >= a[i + 1] for i in range(n - 1)):
            a, b = [], a
            for x in b:
                if not a or a[-1] != x:
                    a.append(x)
        bucket_size = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO)))
        self.a = [a[n * i // bucket_size : n * (i + 1) // bucket_size] for i in range(bucket_size)]

    def __iter__(self) -> Iterator[T]:
        for i in self.a:
            for j in i: yield j

    def __reversed__(self) -> Iterator[T]:
        for i in reversed(self.a):
            for j in reversed(i): yield j
    
    def __eq__(self, other) -> bool:
        return list(self) == list(other)
    
    def __len__(self) -> int:
        return self.size
    
    def __repr__(self) -> str:
        return "SortedSet" + str(self.a)
    
    def __str__(self) -> str:
        s = str(list(self))
        return "{" + s[1 : len(s) - 1] + "}"

    def _position(self, x: T) -> Tuple[List[T], int, int]:
        "return the bucket, index of the bucket and position in which x should be. self must not be empty."
        for i, a in enumerate(self.a):
            if x <= a[-1]: break
        return (a, i, bisect_left(a, x))

    def __contains__(self, x: T) -> bool:
        if self.size == 0: return False
        a, _, i = self._position(x)
        return i != len(a) and a[i] == x

    def add(self, x: T) -> bool:
        "Add an element and return True if added. / O(√N)"
        if self.size == 0:
            self.a = [[x]]
            self.size = 1
            return True
        a, b, i = self._position(x)
        if i != len(a) and a[i] == x: return False
        a.insert(i, x)
        self.size += 1
        if len(a) > len(self.a) * self.SPLIT_RATIO:
            mid = len(a) >> 1
            self.a[b:b+1] = [a[:mid], a[mid:]]
        return True
    
    def _pop(self, a: List[T], b: int, i: int) -> T:
        ans = a.pop(i)
        self.size -= 1
        if not a: del self.a[b]
        return ans

    def discard(self, x: T) -> bool:
        "Remove an element and return True if removed. / O(√N)"
        if self.size == 0: return False
        a, b, i = self._position(x)
        if i == len(a) or a[i] != x: return False
        self._pop(a, b, i)
        return True
    
    def lt(self, x: T) -> Optional[T]:
        "Find the largest element < x, or None if it doesn't exist."
        for a in reversed(self.a):
            if a[0] < x:
                return a[bisect_left(a, x) - 1]

    def le(self, x: T) -> Optional[T]:
        "Find the largest element <= x, or None if it doesn't exist."
        for a in reversed(self.a):
            if a[0] <= x:
                return a[bisect_right(a, x) - 1]

    def gt(self, x: T) -> Optional[T]:
        "Find the smallest element > x, or None if it doesn't exist."
        for a in self.a:
            if a[-1] > x:
                return a[bisect_right(a, x)]

    def ge(self, x: T) -> Optional[T]:
        "Find the smallest element >= x, or None if it doesn't exist."
        for a in self.a:
            if a[-1] >= x:
                return a[bisect_left(a, x)]
    
    def __getitem__(self, i: int) -> T:
        "Return the i-th element."
        if i < 0:
            for a in reversed(self.a):
                i += len(a)
                if i >= 0: return a[i]
        else:
            for a in self.a:
                if i < len(a): return a[i]
                i -= len(a)
        raise IndexError
    
    def pop(self, i: int = -1) -> T:
        "Pop and return the i-th element."
        if i < 0:
            for b, a in enumerate(reversed(self.a)):
                i += len(a)
                if i >= 0: return self._pop(a, ~b, i)
        else:
            for b, a in enumerate(self.a):
                if i < len(a): return self._pop(a, b, i)
                i -= len(a)
        raise IndexError
    
    def index(self, x: T) -> int:
        "Count the number of elements < x."
        ans = 0
        for a in self.a:
            if a[-1] >= x:
                return ans + bisect_left(a, x)
            ans += len(a)
        return ans

    def index_right(self, x: T) -> int:
        "Count the number of elements <= x."
        ans = 0
        for a in self.a:
            if a[-1] > x:
                return ans + bisect_right(a, x)
            ans += len(a)
        return ans


    """
    (num, cnt)を要素としたSSを管理してMultiset化したいとき用.
    """
    def exist(self, x):
        ret = self.gt((x,0))
        if ret is None:
            return False
        elif ret[0] == x:
            return True
        else:
            return False

    def increment(self, x):
        if not self.exist(x):
            self.add((x,1))
        else:
            num, cnt = self.gt((x,0))
            self.discard((x,cnt))
            self.add((x,cnt+1))


    def decrement(self, x):
        if not self.exist(x):
            return
        num, cnt = self.gt((x,0))
        if cnt == 1:
            self.discard((x,cnt))
        else:
            self.discard((x,cnt))
            self.add((x,cnt-1))

    def multi_add(self, x, y):
        if not self.exist(x):
            self.add((x,y))
        else:
            num, cnt = self.gt((x,0))
            self.discard((x,cnt))
            self.add((x,cnt+y))

    def multi_sub(self, x, y):
        if not self.exist(x):
            return
        num, cnt = self.gt((x,0))
        if cnt <= y:
            self.discard((x,cnt))
        else:
            self.discard((x,cnt))
            self.add((x,cnt-y))


# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
T = TypeVar('T')
class SortedMultiset(Generic[T]):
    BUCKET_RATIO = 16
    SPLIT_RATIO = 24
    
    def __init__(self, a: Iterable[T] = []) -> None:
        "Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)"
        a = list(a)
        n = self.size = len(a)
        if any(a[i] > a[i + 1] for i in range(n - 1)):
            a.sort()
        num_bucket = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO)))
        self.a = [a[n * i // num_bucket : n * (i + 1) // num_bucket] for i in range(num_bucket)]

    def __iter__(self) -> Iterator[T]:
        for i in self.a:
            for j in i: yield j

    def __reversed__(self) -> Iterator[T]:
        for i in reversed(self.a):
            for j in reversed(i): yield j
    
    def __eq__(self, other) -> bool:
        return list(self) == list(other)
    
    def __len__(self) -> int:
        return self.size
    
    def __repr__(self) -> str:
        return "SortedMultiset" + str(self.a)
    
    def __str__(self) -> str:
        s = str(list(self))
        return "{" + s[1 : len(s) - 1] + "}"

    def _position(self, x: T) -> Tuple[List[T], int, int]:
        "return the bucket, index of the bucket and position in which x should be. self must not be empty."
        for i, a in enumerate(self.a):
            if x <= a[-1]: break
        return (a, i, bisect_left(a, x))

    def __contains__(self, x: T) -> bool:
        if self.size == 0: return False
        a, _, i = self._position(x)
        return i != len(a) and a[i] == x

    def count(self, x: T) -> int:
        "Count the number of x."
        return self.index_right(x) - self.index(x)

    def add(self, x: T) -> None:
        "Add an element. / O(√N)"
        if self.size == 0:
            self.a = [[x]]
            self.size = 1
            return
        a, b, i = self._position(x)
        a.insert(i, x)
        self.size += 1
        if len(a) > len(self.a) * self.SPLIT_RATIO:
            mid = len(a) >> 1
            self.a[b:b+1] = [a[:mid], a[mid:]]
    
    def _pop(self, a: List[T], b: int, i: int) -> T:
        ans = a.pop(i)
        self.size -= 1
        if not a: del self.a[b]
        return ans

    def discard(self, x: T) -> bool:
        "Remove an element and return True if removed. / O(√N)"
        if self.size == 0: return False
        a, b, i = self._position(x)
        if i == len(a) or a[i] != x: return False
        self._pop(a, b, i)
        return True

    def lt(self, x: T) -> Optional[T]:
        "Find the largest element < x, or None if it doesn't exist."
        for a in reversed(self.a):
            if a[0] < x:
                return a[bisect_left(a, x) - 1]

    def le(self, x: T) -> Optional[T]:
        "Find the largest element <= x, or None if it doesn't exist."
        for a in reversed(self.a):
            if a[0] <= x:
                return a[bisect_right(a, x) - 1]

    def gt(self, x: T) -> Optional[T]:
        "Find the smallest element > x, or None if it doesn't exist."
        for a in self.a:
            if a[-1] > x:
                return a[bisect_right(a, x)]

    def ge(self, x: T) -> Optional[T]:
        "Find the smallest element >= x, or None if it doesn't exist."
        for a in self.a:
            if a[-1] >= x:
                return a[bisect_left(a, x)]
    
    def __getitem__(self, i: int) -> T:
        "Return the i-th element."
        if i < 0:
            for a in reversed(self.a):
                i += len(a)
                if i >= 0: return a[i]
        else:
            for a in self.a:
                if i < len(a): return a[i]
                i -= len(a)
        raise IndexError
    
    def pop(self, i: int = -1) -> T:
        "Pop and return the i-th element."
        if i < 0:
            for b, a in enumerate(reversed(self.a)):
                i += len(a)
                if i >= 0: return self._pop(a, ~b, i)
        else:
            for b, a in enumerate(self.a):
                if i < len(a): return self._pop(a, b, i)
                i -= len(a)
        raise IndexError

    def index(self, x: T) -> int:
        "Count the number of elements < x."
        ans = 0
        for a in self.a:
            if a[-1] >= x:
                return ans + bisect_left(a, x)
            ans += len(a)
        return ans

    def index_right(self, x: T) -> int:
        "Count the number of elements <= x."
        ans = 0
        for a in self.a:
            if a[-1] > x:
                return ans + bisect_right(a, x)
            ans += len(a)
        return ans


class Comb:
    def __init__(self,table_len,mod):
        """
        modが素数の場合しか使用できない.
        table_len に指定した数まで法modでのコンビネーションの計算が可能になる.
        """
        self.fac = [1,1]
        self.inv = [1,1]
        self.finv = [1,1]
        self.mod = mod
        for i in range(2,table_len+1):
            self.fac.append(self.fac[i-1]*i%mod)
            self.inv.append(-self.inv[mod%i]*(mod//i)%mod)
            self.finv.append(self.finv[i-1]*self.inv[i]%mod)

    def comb(self,a,b):
        return self.fac[a]*self.finv[b]*self.finv[a-b]%self.mod


class GridBFS:

    def __init__(self, table):
        #二次元配列や文字列の配列を受け取る.
        self.table = table
        self.H = len(table)
        self.W = len(table[0])
        self.wall = "#"

    def find(self, c):
        #table から引数の文字を探しインデックスを返す. 無い時、None.
        for h in range(self.H):
            for w in range(self.W):
                if self.table[h][w] == c:
                    return (h,w)
        return None

    def set_wall_string(self, string): 
        #壁として扱う文字を "#!^" の様に文字列リテラルで格納. 初期値は、"#"
        self.wall = string

    def island(self, transition = [[-1,0],[0,1],[1,0],[0,-1]]):
        H, W = self.H, self.W
        self.island_id = [[-1]*W for _ in range(H)]
        self.island_size = [[-1]*W for _ in range(W)]

        crr_id = 0
        id2size = dict()
        for sh in range(H):
            for sw in range(W):
                if self.table[sh][sw] in self.wall:
                    continue
                if self.island_id[sh][sw] != -1:
                    continue
                deq = deque()
                deq.append((sh,sw))
                crr_size = 1
                self.island_id[sh][sw] = crr_id
                while deq:
                    h,w = deq.popleft()
                    for dh, dw in transition:
                        nh, nw = h+dh, w+dw
                        if (not 0<=nh<H) or (not 0<=nw<W):
                            continue
                        if self.table[nh][nw] in self.wall:
                            continue
                        if self.island_id[nh][nw] == -1:
                            self.island_id[nh][nw] = crr_id
                            deq.append((nh, nw))
                            crr_size += 1

                id2size[crr_id] = crr_size
                crr_id += 1

        for h in range(H):
            for w in range(W):
                if self.table[h][w] in self.wall:
                    continue
                self.island_size[h][w] = id2size[self.island_id[h][w]]

        return self.island_id, self.island_size


    def distance(self, start, goal=None, transition = [[-1,0],[0,1],[1,0],[0,-1]]):
        #goal指定したら、goalまでの最短距離を、指定しなければdist配列を返す. 到達不可能は -1.
        #二次元配列上での遷移方法を transition で指定できる. 初期値は上下左右.
        H, W, tab, wall = self.H, self.W, self.table, self.wall

        INF = 1<<60

        deq = deque()
        deq.append(start)
        dist = [[INF]*W for _ in range(H)]
        dist[start[0]][start[1]] = 0

        if start == goal:
            return 0

        while deq:
            h,w = deq.popleft()
            for dh, dw in transition:
                nh = h+dh
                nw = w+dw
                # gridの範囲外.
                if (not 0<=nh<H) or (not 0<=nw<W):
                    continue

                # wallに設定されている文字なら.
                if tab[nh][nw] in wall:
                    continue

                new_dist = dist[h][w] + 1

                #goalが引数で与えられていてgoalに達したら終了.
                if goal and (nh,nw)==goal:
                    return new_dist
                
                if dist[nh][nw] > new_dist:
                    dist[nh][nw] = new_dist
                    deq.append((nh,nw))

        # goalが設定されていていまだreturnされていないなら,
        # goalに到達できなかったということ.
        if goal:
            return -1

        return dist


class nth_root:
    def __init__(self):
        self.ngs = [-1, -1, 4294967296, 2642246, 65536, 7132, 1626, 566, 256, 139, 85, 57, 41, 31, 24, 20, 16, 14, 12, 11, 10, 9, 8, 7, 7, 6, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
        """ pre-calculated by this code """
        # self.ngs = [-1,-1]
        # for n in range(2,64):
        #     ok,ng=2**33,0
        #     while abs(ok-ng)>1:
        #         mid=ok+ng>>1
        #         if mid**n>=2**64:
        #             ok=mid
        #         else:
        #             ng=mid
        #     self.ngs.append(ok)

    """ xが64bitに収まる時高速. そうでないときも動作するが速度の保証無し. """
    def calc(self, x, n, is_x_within_64bit=True):
        if x<=1 or n==1: return x
        if is_x_within_64bit:
            if n>=64: return 1
            ng = self.ngs[n]
        else:
            ng = x

        ok = 0
        while abs(ok-ng)>1:
            mid = ok+ng>>1
            if mid**n <= x:
                ok = mid
            else:
                ng = mid
        return ok

# well-used const
global DIRECTION_4, DIRECTION_8, DIRECTION_DIAGONAL, DIRECTION_URDL_TABLE, DIRECTION_URDL_COORD_PLANE, MOD, INF, LOWER_ALP, UPPER_ALP, ALL_ALP

# clockwise from top.
DIRECTION_4 = [[-1,0],[0,1],[1,0],[0,-1]] 
DIRECTION_8 = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]]
DIRECTION_DIAGONAL = [[-1,1],[1,1],[1,-1],[-1,-1]]
DIRECTION_URDL_TABLE = {'U':(-1,0), 'R':(0,1), 'D':(1,0), 'L':(0,-1)}
DIRECTION_URDL_COORD_PLANE = {'U':(0,1), 'R':(1,0), 'D':(0,-1), 'L':(-1,0)}

MOD = 998244353
INF = 1<<60
LOWER_ALP = "abcdefghijklmnopqrstuvwxyz"
UPPER_ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
ALL_ALP = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

main()
yukicoder

結果

テストケース

ソースコード
