結果

問題 No.1219 Mancala Combo
ユーザー osm ibtosm ibt
提出日時 2020-09-09 12:21:13
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,525 bytes
コンパイル時間 699 ms
コンパイル使用メモリ 87,268 KB
実行使用メモリ 108,924 KB
最終ジャッジ日時 2023-08-21 07:41:36
合計ジャッジ時間 6,076 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 68 ms
71,316 KB
testcase_01 AC 67 ms
71,400 KB
testcase_02 AC 67 ms
71,264 KB
testcase_03 AC 68 ms
71,128 KB
testcase_04 WA -
testcase_05 AC 73 ms
75,776 KB
testcase_06 WA -
testcase_07 AC 71 ms
75,376 KB
testcase_08 WA -
testcase_09 AC 67 ms
71,212 KB
testcase_10 WA -
testcase_11 AC 73 ms
75,348 KB
testcase_12 WA -
testcase_13 AC 71 ms
71,400 KB
testcase_14 WA -
testcase_15 AC 68 ms
71,200 KB
testcase_16 WA -
testcase_17 AC 152 ms
97,976 KB
testcase_18 WA -
testcase_19 AC 145 ms
95,524 KB
testcase_20 WA -
testcase_21 AC 135 ms
92,984 KB
testcase_22 WA -
testcase_23 AC 167 ms
104,116 KB
testcase_24 WA -
testcase_25 AC 138 ms
95,272 KB
testcase_26 WA -
testcase_27 AC 173 ms
107,884 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