結果

問題 No.2868 Another String of yuusaan
ユーザー lam6er
提出日時 2025-04-15 23:07:58
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,798 bytes
コンパイル時間 398 ms
コンパイル使用メモリ 82,008 KB
実行使用メモリ 68,288 KB
最終ジャッジ日時 2025-04-15 23:10:14
合計ジャッジ時間 2,407 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 RE * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

def get_char(N, K):
    s = "yuusaan"
    if N == 1:
        return s[K-1]
    
    prev_level = N - 1
    prev_length = 2 * (4 ** prev_level) - 1
    prev_u_a_count = 4 ** prev_level
    
    current_pos = 0
    u_a_blocks = 0
    non_u_a_blocks = 0
    
    low, high = 1, prev_length
    j = 0
    
    while low <= high:
        mid = (low + high) // 2
        u_a = 0
        non_u_a = 0
        stack = [(prev_level, mid)]
        while stack:
            level, pos = stack.pop()
            if level == 1:
                c = s[pos-1]
                if c in {'u', 'a'}:
                    u_a += 1
                else:
                    non_u_a += 1
                continue
            prev_prev_length = 2 * (4 ** (level-1)) - 1
            prev_prev_u_a = 4 ** (level-1)
            total_u_a_block = 7 * prev_prev_u_a
            if pos <= total_u_a_block:
                stack.append((level-1, (pos - 1) // 7 + 1))
            else:
                stack.append((level-1, pos - total_u_a_block + prev_prev_u_a))
        
        total = 7 * u_a + non_u_a
        if current_pos + total < K:
            current_pos += total
            low = mid + 1
        else:
            high = mid - 1
            j = mid
    
    current_pos = 0
    for j in range(1, high + 1):
        stack = [(prev_level, j)]
        u_a = 0
        non_u_a = 0
        while stack:
            level, pos = stack.pop()
            if level == 1:
                c = s[pos-1]
                if c in {'u', 'a'}:
                    u_a += 1
                else:
                    non_u_a += 1
                continue
            prev_prev_length = 2 * (4 ** (level-1)) - 1
            prev_prev_u_a = 4 ** (level-1)
            total_u_a_block = 7 * prev_prev_u_a
            if pos <= prev_prev_u_a:
                stack.append((level-1, pos))
            else:
                stack.append((level-1, pos - prev_prev_u_a))
        
        block_size = 7 if u_a else 1
        if current_pos + block_size >= K:
            offset = K - current_pos - 1
            if u_a:
                return s[offset]
            else:
                stack = [(prev_level, j)]
                while stack:
                    level, pos = stack.pop()
                    if level == 1:
                        return s[pos-1]
                    prev_prev_length = 2 * (4 ** (level-1)) - 1
                    prev_prev_u_a = 4 ** (level-1)
                    total_u_a_block = 7 * prev_prev_u_a
                    if pos <= prev_prev_u_a:
                        stack.append((level-1, pos))
                    else:
                        stack.append((level-1, pos - prev_prev_u_a))
        current_pos += block_size

    return '?'

# Read input
N, K = map(int, input().split())
print(get_char(N, K))
0