結果
問題 | No.1097 Remainder Operation |
ユーザー |
![]() |
提出日時 | 2024-07-17 15:19:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,053 ms / 2,000 ms |
コード長 | 2,334 bytes |
コンパイル時間 | 461 ms |
コンパイル使用メモリ | 82,704 KB |
実行使用メモリ | 157,696 KB |
最終ジャッジ日時 | 2024-07-17 15:20:01 |
合計ジャッジ時間 | 13,527 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
class Path_Doubling:def __init__(self,N,permutation,lst=None,f=None,e=None):self.N=Nself.permutation=permutationself.lst=lstself.f=fself.e=edef Build_Next(self,K=None):if K==None:K=self.Nself.k=K.bit_length()self.permutation_doubling=[[None]*self.N for k in range(self.k)]for n in range(self.N):self.permutation_doubling[0][n]=self.permutation[n]if self.lst!=None:self.doubling=[[self.e]*self.N for k in range(self.k)]for n in range(self.N):self.doubling[0][n]=self.lst[n]for k in range(1,self.k):for n in range(self.N):if self.permutation_doubling[k-1][n]!=None:self.permutation_doubling[k][n]=self.permutation_doubling[k-1][self.permutation_doubling[k-1][n]]if self.f!=None:self.doubling[k][n]=self.f(self.doubling[k-1][n],self.doubling[k-1][self.permutation_doubling[k-1][n]])def Permutation_Doubling(self,N,K):if K<0 or 1<<self.k<=K:return Nonefor k in range(self.k):if K>>k&1 and N!=None:N=self.permutation_doubling[k][N]return Ndef Doubling(self,N,K,edge=False):if K<0:return self.eretu=self.efor k in range(self.k):if K>>k&1:if self.permutation_doubling[k][N]==None:return Noneretu=self.f(retu,self.doubling[k][N])N=self.permutation_doubling[k][N]if not edge:retu=self.f(retu,self.lst[N])return N,retudef Bisect(self,x,is_ok):if not is_ok(x):return -1,NoneK=0for k in range(self.k-1,-1,-1):if is_ok(self.permutation_doubling[k][x]):K|=1<<kx=self.permutation_doubling[k][x]return K,xN=int(input())A=list(map(int,input().split()))perm=[None]*Ncnt=[None]*Nfor x in range(N):perm[x]=(x+A[x%N])%Ncnt[x]=(x+A[x%N])//NQ=int(input())PD=Path_Doubling(N,perm,cnt,lambda c0,c1:c0+c1,0)PD.Build_Next(10**12)for q in range(Q):K=int(input())r,c=PD.Doubling(0,K,True)ans=r+c*Nprint(ans)