#1006892 (PyPy3) No.2821 A[i] ← 2A[j] - A[i]

提出ソース

結果

問題	No.2821 A[i] ← 2A[j] - A[i]
ユーザー	Mao-beta
提出日時	2024-09-02 16:47:34
言語	PyPy3 (7.3.15)
結果	AC
実行時間	204 ms / 1,500 ms
コード長	5,148 bytes
コンパイル時間	273 ms
コンパイル使用メモリ	82,560 KB
実行使用メモリ	138,152 KB
最終ジャッジ日時	2024-09-02 16:47:42
合計ジャッジ時間	8,411 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	63 ms 70,024 KB
testcase_01	AC	187 ms 131,496 KB
testcase_02	AC	204 ms 138,152 KB
testcase_03	AC	204 ms 136,768 KB
testcase_04	AC	154 ms 114,020 KB
testcase_05	AC	161 ms 114,472 KB
testcase_06	AC	127 ms 100,268 KB
testcase_07	AC	134 ms 97,064 KB
testcase_08	AC	151 ms 107,664 KB
testcase_09	AC	98 ms 84,692 KB
testcase_10	AC	145 ms 86,000 KB
testcase_11	AC	108 ms 85,424 KB
testcase_12	AC	108 ms 85,324 KB
testcase_13	AC	108 ms 85,368 KB
testcase_14	AC	111 ms 88,420 KB
testcase_15	AC	118 ms 90,704 KB
testcase_16	AC	102 ms 83,744 KB
testcase_17	AC	113 ms 86,952 KB
testcase_18	AC	121 ms 91,372 KB
testcase_19	AC	108 ms 78,664 KB
testcase_20	AC	93 ms 79,148 KB
testcase_21	AC	76 ms 74,268 KB
testcase_22	AC	76 ms 75,384 KB
testcase_23	AC	87 ms 78,428 KB
testcase_24	AC	66 ms 69,384 KB
testcase_25	AC	66 ms 68,912 KB
testcase_26	AC	69 ms 70,956 KB
testcase_27	AC	70 ms 71,040 KB
testcase_28	AC	70 ms 72,012 KB
testcase_29	AC	70 ms 71,936 KB
testcase_30	AC	66 ms 69,564 KB
testcase_31	AC	64 ms 68,720 KB
testcase_32	AC	96 ms 71,656 KB
testcase_33	AC	69 ms 71,820 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import sys
import math
import bisect
from heapq import heapify, heappop, heappush
from collections import deque, defaultdict, Counter
from functools import lru_cache
from itertools import accumulate, combinations, permutations

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD99 = 998244353

input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()
SMI = lambda: input().split()
SLI = lambda: list(SMI())
EI = lambda m: [NLI() for _ in range(m)]


# https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.py
# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
import math
from bisect import bisect_left, bisect_right, insort
from typing import Generic, Iterable, Iterator, TypeVar, Union, List

T = TypeVar('T')

class SortedMultiset(Generic[T]):
    BUCKET_RATIO = 50
    REBUILD_RATIO = 170

    def _build(self, a=None) -> None:
        "Evenly divide `a` into buckets."
        if a is None: a = list(self)
        size = self.size = len(a)
        bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))
        self.a = [a[size * i // bucket_size: size * (i + 1) // bucket_size] for i in range(bucket_size)]

    def __init__(self, a: Iterable[T] = []) -> None:
        "Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)"
        a = list(a)
        if not all(a[i] <= a[i + 1] for i in range(len(a) - 1)):
            a = sorted(a)
        self._build(a)

    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 __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 _find_bucket(self, x: T) -> List[T]:
        "Find the bucket which should contain x. self must not be empty."
        for a in self.a:
            if x <= a[-1]: return a
        return a

    def __contains__(self, x: T) -> bool:
        if self.size == 0: return False
        a = self._find_bucket(x)
        i = bisect_left(a, 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 = self._find_bucket(x)
        insort(a, x)
        self.size += 1
        if len(a) > len(self.a) * self.REBUILD_RATIO:
            self._build()

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

    def lt(self, x: T) -> Union[T, None]:
        "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) -> Union[T, None]:
        "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) -> Union[T, None]:
        "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) -> Union[T, None]:
        "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, x: int) -> T:
        "Return the x-th element, or IndexError if it doesn't exist."
        if x < 0: x += self.size
        if x < 0: raise IndexError
        for a in self.a:
            if x < len(a): return a[x]
            x -= 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


def main():
    N = NI()
    A = NLI()
    if N == 1:
        print(0)
        return
    if N == 2:
        print(0)
        print(abs(A[1]-A[0]))
        return

    print(0)
    print(abs(A[1] - A[0]))
    g = abs(A[1]-A[0])
    for a in A[2:]:
        g = math.gcd(g, abs(A[0]-a))
        print(g)


if __name__ == "__main__":
    main()

yukicoder

結果

テストケース

ソースコード