結果

問題 No.2000 Distanced Characters
ユーザー 👑 KazunKazun
提出日時 2022-07-08 21:34:11
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,419 bytes
コンパイル時間 475 ms
コンパイル使用メモリ 87,200 KB
実行使用メモリ 90,196 KB
最終ジャッジ日時 2023-08-27 20:57:00
合計ジャッジ時間 10,600 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 84 ms
71,516 KB
testcase_01 AC 115 ms
76,904 KB
testcase_02 AC 78 ms
71,396 KB
testcase_03 AC 78 ms
71,364 KB
testcase_04 AC 140 ms
77,332 KB
testcase_05 AC 159 ms
78,356 KB
testcase_06 AC 136 ms
77,712 KB
testcase_07 AC 139 ms
78,068 KB
testcase_08 AC 113 ms
90,196 KB
testcase_09 TLE -
testcase_10 AC 1,960 ms
83,064 KB
testcase_11 AC 684 ms
88,468 KB
testcase_12 AC 1,128 ms
80,024 KB
testcase_13 AC 1,161 ms
79,912 KB
testcase_14 AC 667 ms
79,108 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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