結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
52,096 KB
testcase_01 AC 42 ms
51,968 KB
testcase_02 AC 42 ms
51,840 KB
testcase_03 AC 41 ms
52,352 KB
testcase_04 WA -
testcase_05 AC 48 ms
58,240 KB
testcase_06 WA -
testcase_07 AC 47 ms
57,984 KB
testcase_08 WA -
testcase_09 AC 42 ms
52,480 KB
testcase_10 WA -
testcase_11 AC 47 ms
58,240 KB
testcase_12 WA -
testcase_13 AC 43 ms
52,480 KB
testcase_14 WA -
testcase_15 AC 42 ms
51,840 KB
testcase_16 WA -
testcase_17 AC 143 ms
96,640 KB
testcase_18 WA -
testcase_19 AC 132 ms
94,560 KB
testcase_20 WA -
testcase_21 AC 123 ms
91,648 KB
testcase_22 WA -
testcase_23 AC 158 ms
102,912 KB
testcase_24 WA -
testcase_25 AC 132 ms
94,208 KB
testcase_26 WA -
testcase_27 AC 169 ms
107,040 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