結果

問題 No.2000 Distanced Characters
ユーザー 👑 KazunKazun
提出日時 2022-07-08 23:07:17
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,356 bytes
コンパイル時間 269 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 89,088 KB
最終ジャッジ日時 2024-10-06 00:34:39
合計ジャッジ時間 8,510 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
53,888 KB
testcase_01 AC 70 ms
73,600 KB
testcase_02 AC 42 ms
53,760 KB
testcase_03 AC 40 ms
53,504 KB
testcase_04 AC 91 ms
76,160 KB
testcase_05 AC 112 ms
77,108 KB
testcase_06 AC 91 ms
76,288 KB
testcase_07 AC 92 ms
76,076 KB
testcase_08 AC 72 ms
78,336 KB
testcase_09 TLE -
testcase_10 AC 1,572 ms
81,536 KB
testcase_11 AC 549 ms
89,088 KB
testcase_12 AC 917 ms
78,976 KB
testcase_13 AC 930 ms
79,360 KB
testcase_14 AC 543 ms
78,336 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 max(alpha-beta,0)

#==================================================
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
        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