#1015729 (PyPy3) No.1475 時計の歯車Easy

• 問題: No.1475 時計の歯車Easy
• ユーザー: Navier_Boltzmann
• 提出日時: 2024-10-05 20:51:58
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 76 ms / 2,000 ms
• コード長: 14,452 bytes
• コンパイル時間: 769 ms
• コンパイル使用メモリ: 82,304 KB
• 実行使用メモリ: 65,536 KB
• 最終ジャッジ日時: 2024-10-05 20:52:28
• 合計ジャッジ時間: 5,077 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	59 ms; 65,536 KB
testcase_01	AC	59 ms; 65,408 KB
testcase_02	AC	60 ms; 65,024 KB
testcase_03	AC	61 ms; 64,896 KB
testcase_04	AC	62 ms; 64,768 KB
testcase_05	AC	62 ms; 64,896 KB
testcase_06	AC	54 ms; 65,024 KB
testcase_07	AC	54 ms; 65,024 KB
testcase_08	AC	57 ms; 65,024 KB
testcase_09	AC	58 ms; 65,024 KB
testcase_10	AC	56 ms; 65,152 KB
testcase_11	AC	56 ms; 65,152 KB
testcase_12	AC	56 ms; 65,152 KB
testcase_13	AC	59 ms; 64,640 KB
testcase_14	AC	63 ms; 64,896 KB
testcase_15	AC	63 ms; 65,024 KB
testcase_16	AC	61 ms; 64,768 KB
testcase_17	AC	62 ms; 64,640 KB
testcase_18	AC	54 ms; 64,768 KB
testcase_19	AC	55 ms; 64,896 KB
testcase_20	AC	55 ms; 64,640 KB
testcase_21	AC	55 ms; 65,024 KB
testcase_22	AC	60 ms; 64,640 KB
testcase_23	AC	59 ms; 64,896 KB
testcase_24	AC	55 ms; 64,640 KB
testcase_25	AC	55 ms; 65,024 KB
testcase_26	AC	56 ms; 64,640 KB
testcase_27	AC	55 ms; 64,640 KB
testcase_28	AC	56 ms; 65,152 KB
testcase_29	AC	55 ms; 65,152 KB
testcase_30	AC	53 ms; 64,768 KB
testcase_31	AC	54 ms; 64,896 KB
testcase_32	AC	55 ms; 65,024 KB
testcase_33	AC	56 ms; 64,896 KB
testcase_34	AC	57 ms; 65,024 KB
testcase_35	AC	57 ms; 65,024 KB
testcase_36	AC	55 ms; 64,896 KB
testcase_37	AC	55 ms; 64,896 KB
testcase_38	AC	57 ms; 64,640 KB
testcase_39	AC	56 ms; 65,024 KB
testcase_40	AC	76 ms; 64,768 KB
testcase_41	AC	56 ms; 65,280 KB
testcase_42	AC	56 ms; 64,896 KB
testcase_43	AC	55 ms; 65,152 KB
testcase_44	AC	55 ms; 65,408 KB
testcase_45	AC	57 ms; 65,024 KB

ソースコード

# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')

from collections import *
from functools import *
from heapq import *
from itertools import *
import sys, math,random
# input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**6)

def cle(a, D):
    """
    Counts the number of elements in D that are less than or equal to a.

    Parameters:
    a (int): The value to compare against.
    D (list): A sorted list of integers.

    Returns:
    int: The count of elements in D that are less than or equal to a.
    """
    y = len(D) - 1
    x = 0
    if D[x] > a:
        return 0

    if D[y] <= a:
        return y + 1

    while y - x > 1:
        mid = (y + x) // 2
        if D[mid] <= a:
            x = mid
        else:
            y = mid
    return y
def mergecount(A):
    """
    Counts the number of inversions in the array A using merge sort.

    Parameters:
    A (list): A list of integers.

    Returns:
    int: The number of inversions in the list.
    """
    cnt = 0
    n = len(A)
    if n > 1:
        A1 = A[: n >> 1]
        A2 = A[n >> 1 :]
        cnt += mergecount(A1)
        cnt += mergecount(A2)
        i1 = 0
        i2 = 0
        for i in range(n):
            if i2 == len(A2):
                A[i] = A1[i1]
                i1 += 1
            elif i1 == len(A1):
                A[i] = A2[i2]
                i2 += 1
            elif A1[i1] <= A2[i2]:
                A[i] = A1[i1]
                i1 += 1
            else:
                A[i] = A2[i2]
                i2 += 1
                cnt += n // 2 - i1
    return cnt
class cs_2d:
    """
    2D cumulative sum class.
    """

    def __init__(self, x):
        """
        Initializes the 2D cumulative sum array.

        Parameters:
        x (list of list of int): A 2D list of integers.
        """
        n = len(x)
        m = len(x[0])
        self.n = n
        self.m = m

        tmp = [0] * ((n + 1) * (m + 1))
        for i in range(n):
            for j in range(m):
                tmp[m * (i + 1) + j + 1] = (
                    tmp[m * (i + 1) + j] + tmp[m * i + j + 1] - tmp[m * i + j] + x[i][j]
                )

        self.S = tmp

    def query(self, ix, jx, iy, jy):
        """
        Queries the sum of the submatrix from (ix, iy) to (jx, jy).

        Parameters:
        ix (int): Starting row index.
        jx (int): Ending row index.
        iy (int): Starting column index.
        jy (int): Ending column index.

        Returns:
        int: The sum of the submatrix.
        """
        return (
            self.S[self.m * jx + jy]
            - self.S[self.m * jx + iy]
            - self.S[self.m * ix + jy]
            + self.S[self.m * ix + iy]
        )
class prime_factorize:
    """
    Class for prime factorization and related operations.
    """

    def __init__(self, M=10**6):
        """
        Initializes the sieve for prime factorization.

        Parameters:
        M (int): The maximum number to factorize.
        """
        self.sieve = [-1] * (M + 1)
        self.sieve[1] = 1
        self.p = [False] * (M + 1)
        self.mu = [1] * (M + 1)

        for i in range(2, M + 1):
            if self.sieve[i] == -1:
                self.p[i] = True

                i2 = i**2
                for j in range(i2, M + 1, i2):
                    self.mu[j] = 0

                for j in range(i, M + 1, i):
                    self.sieve[j] = i
                    self.mu[j] *= -1

    def factors(self, x):
        """
        Returns the prime factors of x.

        Parameters:
        x (int): The number to factorize.

        Returns:
        list: A list of prime factors of x.
        """
        tmp = []
        while self.sieve[x] != x:
            tmp.append(self.sieve[x])
            x //= self.sieve[x]
        tmp.append(self.sieve[x])
        return tmp

    def divisors(self, x):
        """
        Returns all divisors of x.

        Parameters:
        x (int): The number to find divisors for.

        Returns:
        list: A sorted list of all divisors of x.
        """
        C = Counter(self.factors(x))
        tmp = []
        for p in product(*[[pow(k, i) for i in range(v + 1)] for k, v in C.items()]):
            res = 1
            for pp in p:
                res *= pp
            tmp.append(res)
        tmp.sort()
        return tmp

    def is_prime(self, x):
        """
        Checks if x is a prime number.

        Parameters:
        x (int): The number to check.

        Returns:
        bool: True if x is prime, False otherwise.
        """
        return self.p[x]

    def mobius(self, x):
        """
        Returns the Möbius function value of x.

        Parameters:
        x (int): The number to find the Möbius function value for.

        Returns:
        int: The Möbius function value of x.
        """
        return self.mu[x]
class combination:
    """
    Class for computing combinations (nCr) modulo p.
    """

    def __init__(self, N, p):
        """
        Initializes the combination class.

        Parameters:
        N (int): The maximum value of n.
        p (int): The modulus.
        """
        self.fact = [1, 1]  # fact[n] = (n! mod p)
        self.factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
        self.inv = [0, 1]  # factinv calculation
        self.p = p

        for i in range(2, N + 1):
            self.fact.append((self.fact[-1] * i) % p)
            self.inv.append((-self.inv[p % i] * (p // i)) % p)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % p)

    def cmb(self, n, r):
        """
        Computes the combination (nCr) modulo p.

        Parameters:
        n (int): The total number of items.
        r (int): The number of items to choose.

        Returns:
        int: The value of nCr modulo p.
        """
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] * self.factinv[n - r] % self.p
def md(n):
    """
    Returns all divisors of n.

    Parameters:
    n (int): The number to find divisors for.

    Returns:
    list: A sorted list of all divisors of n.
    """
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
class DSU:
    """
    Disjoint Set Union (Union-Find) class.
    """

    def __init__(self, n):
        """
        Initializes the DSU.

        Parameters:
        n (int): The number of elements.
        """
        self._n = n
        self.parent_or_size = [-1] * n
        self.member = [[i] for i in range(n)]

    def merge(self, a, b):
        """
        Merges the sets containing a and b.

        Parameters:
        a (int): An element in the first set.
        b (int): An element in the second set.

        Returns:
        int: The leader of the merged set.
        """
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        x, y = self.leader(a), self.leader(b)
        if x == y:
            return x
        if -self.parent_or_size[x] < -self.parent_or_size[y]:
            x, y = y, x
        self.parent_or_size[x] += self.parent_or_size[y]
        for tmp in self.member[y]:
            self.member[x].append(tmp)
        self.parent_or_size[y] = x
        return x

    def members(self, a):
        """
        Returns the members of the set containing a.

        Parameters:
        a (int): An element in the set.

        Returns:
        list: A list of members in the set containing a.
        """
        return self.member[self.leader(a)]

    def same(self, a, b):
        """
        Checks if a and b are in the same set.

        Parameters:
        a (int): An element in the first set.
        b (int): An element in the second set.

        Returns:
        bool: True if a and b are in the same set, False otherwise.
        """
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        """
        Finds the leader of the set containing a.

        Parameters:
        a (int): An element in the set.

        Returns:
        int: The leader of the set containing a.
        """
        assert 0 <= a < self._n
        if self.parent_or_size[a] < 0:
            return a
        self.parent_or_size[a] = self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]

    def size(self, a):
        """
        Returns the size of the set containing a.

        Parameters:
        a (int): An element in the set.

        Returns:
        int: The size of the set containing a.
        """
        assert 0 <= a < self._n
        return -self.parent_or_size[self.leader(a)]

    def groups(self):
        """
        Returns all sets as a list of lists.

        Returns:
        list: A list of lists, where each list contains the members of a set.
        """
        leader_buf = [self.leader(i) for i in range(self._n)]
        result = [[] for _ in range(self._n)]
        for i in range(self._n):
            result[leader_buf[i]].append(i)
        return [r for r in result if r != []]
class SegTree:
    """
    Segment Tree class.
    """

    def __init__(self, init_val, segfunc, ide_ele):
        """
        Initializes the Segment Tree.

        Parameters:
        init_val (list): The initial values for the leaves of the tree.
        segfunc (function): The function to use for segment operations.
        ide_ele (any): The identity element for the segment function.
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # Set the initial values to the leaves
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # Build the tree
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        Updates the k-th value to x.

        Parameters:
        k (int): The index to update (0-indexed).
        x (any): The new value.
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            tk = k >> 1
            self.tree[tk] = self.segfunc(self.tree[tk << 1], self.tree[(tk << 1) + 1])
            k >>= 1

    def get(self, x):
        return self.tree[x + self.num]

    def query(self, l, r):
        """
        Queries the segment function result for the range [l, r).

        Parameters:
        l (int): The start index (0-indexed).
        r (int): The end index (0-indexed).

        Returns:
        any: The result of the segment function for the range [l, r).
        """
        res_l = self.ide_ele
        res_r = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res_l = self.segfunc(res_l, self.tree[l])
                l += 1
            if r & 1:
                res_r = self.segfunc(self.tree[r - 1], res_r)
            l >>= 1
            r >>= 1
        res = self.segfunc(res_l, res_r)
        return res
def dijkstra(s, e):
    INF = 1 << 60
    N = len(e)
    dist = [INF] * N
    dist[s] = 0
    h = []
    heappush(h, s)
    while h:
        nw, v = divmod(heappop(h), N)
        if dist[v] != nw:
            continue
        for iv, ic in e[v]:
            nc = ic + nw
            if nc < dist[iv]:
                dist[iv] = nc
                heappush(h, nc * N + iv)
    return dist
class RSQandRAQ():
    """区間加算、区間取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    query: 区間[l, r)の和を求める
    l, rは0-indexed
    """

    def __init__(self, n):
        self.n = n
        self.bit0 = [0] * (n + 1)
        self.bit1 = [0] * (n + 1)

    def _add(self, bit, i, val):
        i = i + 1
        while i <= self.n:
            bit[i] += val
            i += i & -i

    def _get(self, bit, i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(self.bit0, l, -val * l)
        self._add(self.bit0, r,  val * r)
        self._add(self.bit1, l,  val)
        self._add(self.bit1, r, -val)

    def query(self, l, r):
        """区間[l, r)の和を求める"""
        return self._get(self.bit0, r) + r * self._get(self.bit1, r) \
            - self._get(self.bit0, l) - l * self._get(self.bit1, l)
class Dinic:
    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None
 
    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])
 
    def bfs(self, s):
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth
 
    def dfs(self, v, t, flow):
        if v == t:
            return flow
        links_v = self.links[v]
        for i in range(self.progress[v], len(links_v)):
            self.progress[v] = i
            cap, to, rev = link = links_v[i]
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0
 
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, float('inf'))
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, float('inf'))

N = int(input())
for _ in range(N):
    _,*X = list(map(int,input().split()))
    X.sort(reverse=True)
    print(*X)