結果

問題 No.2000 Distanced Characters
ユーザー KazunKazun
提出日時 2022-07-08 21:34:11
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,419 bytes
コンパイル時間 197 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 89,216 KB
最終ジャッジ日時 2024-06-08 16:35:35
合計ジャッジ時間 8,344 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
53,504 KB
testcase_01 AC 70 ms
72,064 KB
testcase_02 AC 41 ms
52,992 KB
testcase_03 AC 42 ms
53,376 KB
testcase_04 AC 101 ms
76,160 KB
testcase_05 AC 124 ms
77,300 KB
testcase_06 AC 105 ms
76,576 KB
testcase_07 AC 107 ms
76,696 KB
testcase_08 AC 79 ms
78,080 KB
testcase_09 TLE -
testcase_10 AC 1,598 ms
81,280 KB
testcase_11 AC 579 ms
89,216 KB
testcase_12 AC 944 ms
79,160 KB
testcase_13 AC 938 ms
78,720 KB
testcase_14 AC 550 ms
78,244 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