#810350 (PyPy3) No.515 典型LCP

提出ソース
結果

問題	No.515 典型LCP
ユーザー	vwxyz
提出日時	2022-10-23 19:26:06
言語	PyPy3 (7.3.15)
結果	WA
実行時間	-
コード長	14,734 bytes
コンパイル時間	719 ms
コンパイル使用メモリ	82,172 KB
実行使用メモリ	119,668 KB
最終ジャッジ日時	2024-07-02 10:00:51
合計ジャッジ時間	6,151 ms
ジャッジサーバーID （参考情報）	judge5 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
import time
from collections import Counter,deque,defaultdict
from functools import lru_cache,reduce
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
    if heap and item < heap[0]:
        item, heap[0] = heap[0], item
        heapq._siftup_max(heap, 0)
    return item
from math import gcd as GCD
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines
write=sys.stdout.write

def SA_IS(lst,compressed=False):
    N=len(lst)
    if not compressed:
        decomp=sorted(list(set(lst)))
        comp={x:i for i,x in enumerate(decomp)}
        lst=[comp[s]+1 for s in lst]+[0]
    else:
        lst=[s+1 for s in lst]+[0]

    def induced_sort(N,lst,type,LMS,bucket_count,sorted_LMS_index=None):
        buckets_left=[[] for b in range(bucket_count)]
        buckets_right=[[] for b in range(bucket_count)]
        if sorted_LMS_index==None:
            for i in LMS:
                buckets_right[lst[i]].append(i)
        else:
            for i in sorted_LMS_index[::-1]:
                buckets_right[lst[LMS[i]]].append(LMS[i])
        for b in range(bucket_count):
            for i in buckets_left[b]:
                if i and type[i-1]=="L":
                    buckets_left[lst[i-1]].append(i-1)
            for i in buckets_right[b][::-1]:
                if i and type[i-1]=="L":
                    buckets_left[lst[i-1]].append(i-1)
            buckets_right[b]=[]
        for b in range(bucket_count-1,-1,-1):
            for i in buckets_right[b]:
                if i and type[i-1]=="S":
                    buckets_right[lst[i-1]].append(i-1)
            for i in buckets_left[b][::-1]:
                if i and type[i-1]=="S":
                    buckets_right[lst[i-1]].append(i-1)
        suffix_array=[N]
        for b in range(1,bucket_count):
            suffix_array+=buckets_left[b]+buckets_right[b][::-1]
        return suffix_array
    
    stack=[]
    while N>=1:
        type=[None]*(N+1)
        type[N]="S"
        for i in range(N-1,-1,-1):
            if lst[i]<lst[i+1]:
                type[i]="S"
            elif lst[i]>lst[i+1]:
                type[i]="L"
            else:
                type[i]=type[i+1]
        LMS=[i for i in range(1,N) if type[i-1]=="L" and type[i]=="S"]+[N]
        bucket_count=max(lst)+1
        stack.append((N,lst,type,LMS,bucket_count))
        suffix_array=induced_sort(N,lst,type,LMS,bucket_count)
        LMS_substring=[None]*(N+1)
        for i in range(len(LMS)-1):
            LMS_substring[LMS[i]]=lst[LMS[i]:LMS[i+1]]
        LMS_substring[N]=lst[N:N+1]
        num=0
        prev=[0]
        for i in suffix_array:
            if LMS_substring[i]!=None:
                if prev!=LMS_substring[i]:
                    prev=LMS_substring[i]
                    num+=1
                LMS_substring[i]=num
        lst=[LMS_substring[i] for i in LMS]
        N=len(lst)-1
    sorted_LMS_index=[0]
    for N,lst,type,LMS,bucket_count in stack[::-1]:
        suffix_array=induced_sort(N,lst,type,LMS,bucket_count,sorted_LMS_index)
        sorted_LMS_index=suffix_array
    suffix_array=suffix_array[1:]
    return suffix_array

class Rolling_Hash:
    def __init__(self,lst,base,mod):
        assert math.gcd(base,mod)==1
        self.len=len(lst)
        self.base=base
        self.mod=mod
        self.rolling_hash=[None]*(self.len+1)
        self.rolling_hash[0]=0
        x=1
        for i in range(1,self.len+1):
            self.rolling_hash[i]=self.rolling_hash[i-1]+x*lst[i-1]
            self.rolling_hash[i]%=self.mod
            x*=self.base
            x%=self.mod
        x=MOD(self.mod).Pow(x,-1)
        self.base_reverse=[None]*(self.len+1)
        self.base_reverse[self.len]=x
        for i in range(self.len-1,-1,-1):
            self.base_reverse[i]=self.base_reverse[i+1]*self.base%self.mod

    def __getitem__(self,i):
        if type(i)==int:
            a,b=i,i+1
        else:
            a,b=i.start,i.stop
            if a==None or a<-self.len:
                a=0
            elif self.len<=a:
                a=self.len
            elif a<0:
                a+=self.len
            if b==None or self.len<=b:
                b=self.len
            elif b<-self.len:
                b=0
            elif b<0:
                b+=self.len
        return (self.rolling_hash[b]-self.rolling_hash[a])*self.base_reverse[a]%self.mod

    def __len__(self):
        return self.len

def Extended_Euclid(n,m):
    stack=[]
    while m:
        stack.append((n,m))
        n,m=m,n%m
    if n>=0:
        x,y=1,0
    else:
        x,y=-1,0
    for i in range(len(stack)-1,-1,-1):
        n,m=stack[i]
        x,y=y,x-(n//m)*y
    return x,y

class MOD:
    def __init__(self,p,e=None):
        self.p=p
        self.e=e
        if self.e==None:
            self.mod=self.p
        else:
            self.mod=self.p**self.e

    def Pow(self,a,n):
        a%=self.mod
        if n>=0:
            return pow(a,n,self.mod)
        else:
            assert math.gcd(a,self.mod)==1
            x=Extended_Euclid(a,self.mod)[0]
            return pow(x,-n,self.mod)

    def Build_Fact(self,N):
        assert N>=0
        self.factorial=[1]
        if self.e==None:
            for i in range(1,N+1):
                self.factorial.append(self.factorial[-1]*i%self.mod)
        else:
            self.cnt=[0]*(N+1)
            for i in range(1,N+1):
                self.cnt[i]=self.cnt[i-1]
                ii=i
                while ii%self.p==0:
                    ii//=self.p
                    self.cnt[i]+=1
                self.factorial.append(self.factorial[-1]*ii%self.mod)
        self.factorial_inve=[None]*(N+1)
        self.factorial_inve[-1]=self.Pow(self.factorial[-1],-1)
        for i in range(N-1,-1,-1):
            ii=i+1
            while ii%self.p==0:
                ii//=self.p
            self.factorial_inve[i]=(self.factorial_inve[i+1]*ii)%self.mod

    def Fact(self,N):
        if N<0:
            return 0
        retu=self.factorial[N]
        if self.e!=None and self.cnt[N]:
            retu*=pow(self.p,self.cnt[N],self.mod)%self.mod
            retu%=self.mod
        return retu

    def Fact_Inve(self,N):
        if self.e!=None and self.cnt[N]:
            return None
        return self.factorial_inve[N]

    def Comb(self,N,K,divisible_count=False):
        if K<0 or K>N:
            return 0
        retu=self.factorial[N]*self.factorial_inve[K]%self.mod*self.factorial_inve[N-K]%self.mod
        if self.e!=None:
            cnt=self.cnt[N]-self.cnt[N-K]-self.cnt[K]
            if divisible_count:
                return retu,cnt
            else:
                retu*=pow(self.p,cnt,self.mod)
                retu%=self.mod
        return retu

def Bisect_Int(ok,ng,is_ok):
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if is_ok(mid):
            ok=mid
        else:
            ng=mid
    return ok

class Segment_Tree:
    def __init__(self,N,f,e,lst=None,dynamic=False):
        self.f=f
        self.e=e
        self.N=N
        if dynamic:
            self.segment_tree=defaultdict(lambda:self.e)
        else:
            if lst==None:
                self.segment_tree=[self.e]*2*self.N
            else:
                assert len(lst)<=self.N
                self.segment_tree=[self.e]*self.N+[x for x in lst]+[self.e]*(N-len(lst))
                for i in range(self.N-1,0,-1):
                    self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])

    def __getitem__(self,i):
        if type(i)==int:
            if -self.N<=i<0:
                return self.segment_tree[i+self.N*2]
            elif 0<=i<self.N:
                return self.segment_tree[i+self.N]
            else:
                raise IndexError("list index out of range")
        else:
            a,b,c=i.start,i.stop,i.step
            if a==None:
                a=self.N
            else:
                a+=self.N
            if b==None:
                b=self.N*2
            else:
                b+=self.N
            return self.segment_tree[slice(a,b,c)]

    def __setitem__(self,i,x):
        if -self.N<=i<0:
            i+=self.N*2
        elif 0<=i<self.N:
            i+=self.N
        else:
            raise IndexError("list index out of range")
        self.segment_tree[i]=x
        while i>1:
            i>>= 1
            self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])

    def Build(self,lst):
        for i,x in enumerate(lst,self.N):
            self.segment_tree[i]=x
        for i in range(self.N-1,0,-1):
            self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])

    def Fold(self,L=None,R=None):
        if L==None:
            L=self.N
        else:
            L+=self.N
        if R==None:
            R=self.N*2
        else:
            R+=self.N
        vL=self.e
        vR=self.e
        while L<R:
            if L&1:
                vL=self.f(vL,self.segment_tree[L])
                L+=1
            if R&1:
                R-=1
                vR=self.f(self.segment_tree[R],vR)
            L>>=1
            R>>=1
        return self.f(vL,vR)

    def Fold_Index(self,L=None,R=None):
        if L==None:
            L=self.N
        else:
            L+=self.N
        if R==None:
            R=self.N*2
        else:
            R+=self.N
        if L==R:
            return None
        x=self.Fold(L-self.N,R-self.N)
        while L<R:
            if L&1:
                if self.segment_tree[L]==x:
                    i=L
                    break
                L+=1
            if R&1:
                R-=1
                if self.segment_tree[R]==x:
                    i=R
                    break
            L>>=1
            R>>=1
        while i<self.N:
            if self.segment_tree[i]==self.segment_tree[i<<1]:
                i<<=1
            else:
                i<<=1
                i|=1
        i-=self.N
        return i

    def Bisect_Right(self,L=None,f=None):
        if L==self.N:
            return self.N
        if L==None:
            L=0
        L+=self.N
        vl=self.e
        vr=self.e
        l,r=L,self.N*2
        while l<r:
            if l&1:
                vl=self.f(vl,self.segment_tree[l])
                l+=1
            if r&1:
                r-=1
                vr=self.f(self.segment_tree[r],vr)
            l>>=1
            r>>=1
        if f(self.f(vl,vr)):
            return self.N
        v=self.e
        while True:
            while L%2==0:
                L>>=1
            vv=self.f(v,self.segment_tree[L])
            if f(vv):
                v=vv
                L+=1
            else:
                while L<self.N:
                    L<<=1
                    vv=self.f(v,self.segment_tree[L])
                    if f(vv):
                        v=vv
                        L+=1
                return L-self.N

    def Bisect_Left(self,R=None,f=None):
        if R==0:
            return 0
        if R==None:
            R=self.N
        R+=self.N
        vl=self.e
        vr=self.e
        l,r=self.N,R
        while l<r:
            if l&1:
                vl=self.f(vl,self.segment_tree[l])
                l+=1
            if r&1:
                r-=1
                vr=self.f(self.segment_tree[r],vr)
            l>>=1
            r>>=1
        if f(self.f(vl,vr)):
            return 0
        v=self.e
        while True:
            R-=1
            while R>1 and R%2:
                R>>=1
            vv=self.f(self.segment_tree[R],v)
            if f(vv):
                v=vv
            else:
                while R<self.N:
                    R=2*R+1
                    vv=self.f(self.segment_tree[R],v)
                    if f(vv):
                        v=vv
                        R-=1
                return R+1-self.N

    def __str__(self):
        return "["+", ".join(map(str,self.segment_tree[self.N:]))+"]"

class Path_Doubling:
    def __init__(self,N,permutation,lst=None,f=None,e=None):
        self.N=N
        self.permutation=permutation
        self.lst=lst
        self.f=f
        self.e=e

    def Build_Next(self,K=None):
        if K==None:
            K=self.N
        self.k=K.bit_length()
        self.permutation_doubling=[[self.permutation[n]] for n in range(self.N)]
        if self.lst!=None:
            self.doubling=[[self.lst[n]] for n in range(self.N)]
        for i in range(1,self.k):
            for n in range(self.N):
                self.permutation_doubling[n].append(self.permutation_doubling[self.permutation_doubling[n][i-1]][i-1])
                if self.f!=None:
                    self.doubling[n].append(self.f(self.doubling[n][i-1],self.doubling[self.permutation_doubling[n][i-1]][i-1]))

    def Permutation_Doubling(self,N,K):
        if K<0:
            return N
        for i in range(self.k):
            if K>>i&1:
                N=self.permutation_doubling[N][i]
        return N

    def Doubling(self,N,K):
        if K<0:
            return self.e
        retu=self.e
        for i in range(self.k):
            if K>>i&1:
                retu=self.f(retu,self.doubling[N][i])
                N=self.permutation_doubling[N][i]
        return retu

class Sparse_Table:
    def __init__(self,N,f,e,lst):
        self.N=N
        self.f=f
        self.e=e
        self.n=N.bit_length()
        self.dp=[[None]*(self.N-(1<<n)+1) for n in range(self.n)]
        if self.n:
            for i in range(self.N):
                self.dp[0][i]=lst[i]
            for n in range(1,self.n):
                for i in range(self.N-(1<<n)+1):
                    self.dp[n][i]=self.f(self.dp[n-1][i],self.dp[n-1][i+(1<<n-1)])

    def Fold(self,L,R):
        n=(R-L).bit_length()-1
        return self.f(self.dp[n][L],self.dp[n][R-(1<<n)])

from operator import itemgetter
N=int(readline())
S=[readline().rstrip() for n in range(N)]
S=sorted(list(enumerate(S)),key=itemgetter(1))
idx=[None]*N
for i in range(N):
    idx[S[i][0]]=i
    S[i]=S[i][1]
base=random.randint(1<<50,1<<51)
mod=(1<<61)-1
LCP=[0]*(N-1)
for i in range(N-1):
    for a,b in zip(S[i],S[i+1]):
        if a==b:
            LCP[i]+=1
        else:
            break
ans=0
inf=1<<30
LCP=Sparse_Table(N-1,min,inf,LCP)
M,x,d=map(int,readline().split())
for k in range(1,M+1):
    i,j=(x//(N-1)),(x%(N-1))
    if i>j:
        i,j=j,i
    else:
        j+=1
    x=(x+d)%(N*(N-1))
    i,j=idx[i],idx[j]
    if i>j:
        i,j=j,i
print(ans)
yukicoder

結果

テストケース

ソースコード
