結果
問題 | No.1097 Remainder Operation |
ユーザー |
![]() |
提出日時 | 2024-07-17 15:16:24 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,291 bytes |
コンパイル時間 | 535 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 213,664 KB |
最終ジャッジ日時 | 2024-07-17 15:16:32 |
合計ジャッジ時間 | 7,851 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 TLE * 1 -- * 10 |
ソースコード
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):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]return N,self.f(retu,self.lst[N])def 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-1)r=perm[r]ans=r+c*Nprint(ans)