結果

問題 No.1097 Remainder Operation
ユーザー StanMarsh
提出日時 2024-01-05 17:06:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 150 ms / 2,000 ms
コード長 3,543 bytes
コンパイル時間 255 ms
コンパイル使用メモリ 82,212 KB
実行使用メモリ 116,060 KB
最終ジャッジ日時 2024-09-27 19:08:04
合計ジャッジ時間 5,644 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class CycleGetter():
def __init__(self,start,max_time):
"""
:param max_time:
:param start:
:return front: cycle
cycle: cycle
end: cycle
cnt: cycle
"""
p = start
front, cycle, end = [], [], []
max_time+=1
cnt = 0
visit = {p:0}
L, R =max_time,-1
P = [p]
for i in range(1,max_time):
p = lift(p)
if p in visit:
"""
(L, R) = (, )
[6,2,3,4,0,1,2] ⇒ (L, R) = (1, 6)
"""
L, R = visit[p], i
period = R-L
break
visit[p] = i
P.append(p)
front = P[:L]
if L != max_time:
cycle, end = P[L:R],P[L:L+(max_time-L)%period]
cnt =(max_time-L)//period
self.front,self.cycle,self.end,self.cnt = front, cycle, end, cnt
def apply(self,time):
"""
:param time: time
:return:
"""
if time<len(self.front):
return self.front[time]
else:
time-=len(self.front)
time%=len(self.cycle)
return self.cycle[time]
def set_sum(self):
"""
 [0,r) 
"""
def merge(x,y):
return x+A[y]
self.front_sum=[0]
for a in self.front:
self.front_sum.append(merge(self.front_sum[-1],a))
self.cycle_sum=[0]
for a in self.cycle:
self.cycle_sum.append(merge(self.cycle_sum[-1],a))
def sum(self,r):
"""
 [0,r) 
"""
res=0
if r<=len(self.front):
res+=self.front_sum[r]
else:
r-=len(self.front)
p,q=r//len(self.cycle),r%len(self.cycle)
res+=self.front_sum[-1]
res+=self.cycle_sum[-1]*p+self.cycle_sum[q]
return res
def __getitem__(self, i):
return self.apply(i)
def __iter__(self):
for i in range(max_time):
yield self.apply(i)
def __str__(self):
res=[]
for a in self:
res.append(str(a))
return " ".join(res)
################################################################################
def example():
global input
example = iter(
"""
2
314159 141421
1
271828
"""
.strip().split("\n"))
input = lambda: next(example)
################################################################################
import sys
input=sys.stdin.readline
# example()
N=int(input())
A=list(map(int, input().split()))
#######################################
def lift(x):
""" """
return (x+A[x%N])%N
start, max_time = 0, 10**13
CG=CycleGetter(start, max_time)
"""
"""
front,cycle,end,cnt = CG.front, CG.cycle, CG.end, CG.cnt
#######################################
CG.set_sum()
Q=int(input())
for _ in range(Q):
K=int(input())
print(CG.sum(K))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0