結果

問題 No.2000 Distanced Characters
コンテスト
ユーザー 👑 Kazun
提出日時 2022-07-08 21:34:11
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,419 bytes
コンパイル時間 1,799 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 88,832 KB
最終ジャッジ日時 2024-12-28 04:16:18
合計ジャッジ時間 9,837 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 12 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def Binary_Search_Small_Count(A, x, equal=False, sort=False):
    """二分探索によって, x 未満の要素の個数を調べる.

    A: リスト
    x: 調べる要素
    sort: ソートをする必要があるかどうか (True で必要)
    equal: True のときは x "未満" が x "以下" になる
    """
    if sort:
        A.sort()

    if len(A)==0 or A[0]>x or ((not equal) and A[0]==x):
        return 0

    L,R=0,len(A)
    while R-L>1:
        C=L+(R-L)//2
        if A[C]<x or (equal and A[C]==x):
            L=C
        else:
            R=C

    return L+1

def Binary_Search_Big_Count(A, x, equal=False, sort=False):
    """二分探索によって, x を超える要素の個数を調べる.

    A: リスト
    x: 調べる要素
    sort: ソートをする必要があるかどうか (True で必要)
    equal: True のときは x "を超える" が x "以上" になる
    """

    if sort:
        A.sort()

    if len(A)==0 or A[-1]<x or ((not equal) and A[-1]==x):
        return 0

    L,R=-1,len(A)-1
    while R-L>1:
        C=L+(R-L)//2
        if A[C]>x or (equal and A[C]==x):
            R=C
        else:
            L=C
    return len(A)-R

def Binary_Search_Range_Count(A, x, y, sort=False, left_close=True, right_close=True):
    """二分探索によって, x 以上 y 以下 の個数を調べる.

    A: リスト
    x, y: 調べる要素
    sort: ソートをする必要があるかどうか (True で必要)
    left_equal: True のときは x<=a, False のときは x<a
    right_equal: True のときは y<=a, False のときは y<a
    """

    if sort:
        A.sort()

    alpha=Binary_Search_Small_Count(A, y, equal=right_close)
    beta =Binary_Search_Small_Count(A, x, equal=not left_close)
    return alpha-beta
#==================================================
S=input()

alpha=26
I=[[] for _ in range(alpha)]
for i,s in enumerate(S):
    I[ord(s)-ord("a")].append(i)

D=[[] for _ in range(alpha)]

Ans=[["N"]*alpha for _ in range(alpha)]
for a in range(alpha):
    D[a]=list(map(int,input().split()))

    for b in range(alpha):
        flag=1
        if D[a][b]==0:
            Ans[a][b]="Y"
            continue

        for i in I[a]:
            if Binary_Search_Range_Count(I[b], i, i+D[a][b], False, False, False):
                flag=0
                break
        if flag:
            Ans[a][b]="Y"

for ans in Ans:
    print(*ans)
0