結果

問題 No.1219 Mancala Combo
ユーザー osm ibtosm ibt
提出日時 2020-09-09 12:21:13
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,525 bytes
コンパイル時間 464 ms
コンパイル使用メモリ 82,156 KB
実行使用メモリ 107,696 KB
最終ジャッジ日時 2024-12-14 17:04:26
合計ジャッジ時間 4,551 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
53,016 KB
testcase_01 AC 39 ms
51,940 KB
testcase_02 AC 42 ms
52,736 KB
testcase_03 AC 38 ms
51,940 KB
testcase_04 WA -
testcase_05 AC 44 ms
58,716 KB
testcase_06 WA -
testcase_07 AC 45 ms
59,376 KB
testcase_08 WA -
testcase_09 AC 39 ms
53,492 KB
testcase_10 WA -
testcase_11 AC 47 ms
59,440 KB
testcase_12 WA -
testcase_13 AC 44 ms
53,656 KB
testcase_14 WA -
testcase_15 AC 42 ms
52,712 KB
testcase_16 WA -
testcase_17 AC 125 ms
96,772 KB
testcase_18 WA -
testcase_19 AC 120 ms
93,908 KB
testcase_20 WA -
testcase_21 AC 111 ms
91,944 KB
testcase_22 WA -
testcase_23 AC 142 ms
102,700 KB
testcase_24 WA -
testcase_25 AC 117 ms
94,312 KB
testcase_26 WA -
testcase_27 AC 154 ms
106,812 KB
testcase_28 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin python3
# -*- coding: utf-8 -*-

# Binary Indexed Tree
# 1-indexed
# sum(r)        :閉区間 [0,r) の合計を取得する
# [8] a0 ・ a1  ・ a2 ・ a3 ・ a4 ・ a5 ・ a6 ・ a7
# [4] a0 ・ a1  ・ a2 ・ a3
# [2] a0 ・ a1               [6] a4 ・ a5
# [1] a0       [3] a2        [5] a4        [7] a6

#                   [1000]
#           [0100]
#   [0010]                [0110]
# [0001]    [0011]      [0111]      [1111]

class BinaryIndexedTree:
    # 初期化処理
    def __init__(self, size):
        self.size = size
        self.dat = [0]*(size+1)

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.dat[i] += x
            i += i & -i # 更新すべき位置

    def sum(self, r):
        r += 1
        ret = 0
        while r>0:
            ret += self.dat[r]
            r -= r & -r # 加算すべき位置
        return ret

    def init(self, a):
        for i, x in enumerate(a):
            self.add(i, x)

    def initrng(self, a):
        self.add(0, a[0])
        for i in range(1,n):
            self.add(i, a[i]-a[i-1])

n = int(input())
a = list(map(int, input().split()))
### 区間に対する更新
bit = BinaryIndexedTree(n+1)
bit.initrng(a)
for j in range(n, 0, -1):
    for i in range(j):
        x = bit.sum(i)
        if x>i+1:
            print('No')
            exit()
        if x==i+1:
            bit.add(0,1)
            bit.add(i,-i-2)
            bit.add(i+1,i+1)
#            ret = [bit.sum(i) for i in range(n)]
print('Yes')
0