結果

問題 No.3562 Communicate Sorted Vector
コンテスト
ユーザー maspy
提出日時 2026-05-29 20:38:09
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 402 ms / 2,000 ms
コード長 1,739 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 652 ms
コンパイル使用メモリ 20,696 KB
実行使用メモリ 35,480 KB
平均クエリ数 3.00
最終ジャッジ日時 2026-05-29 20:39:15
合計ジャッジ時間 57,704 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点1 10 % AC * 45
部分点2 25 % AC * 45
部分点3 65 % AC * 46
合計 100 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def C(N, K):
    ANS = 1
    for k in range(K):
        ANS = ANS * (N - k) // (k + 1)
    return ANS


def count(N, M):
    if M < N:
        return 0
    # 1<=A[i]<=M
    return C(M, N)


def binary_search(check, ok, ng):
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        if check(mid):
            ok = mid
        else:
            ng = mid
    return ok


def to_rank(A):
    if not A:
        return 0
    N = len(A)
    a = A.pop()
    ANS = count(N, a - 1)
    ANS += to_rank(A)
    return ANS


def from_rank(N, rank):
    if N == 0:
        assert rank == 0
        return []

    def check(a):
        return count(N, a) <= rank

    a = binary_search(check, 0, 10**9)
    rank -= count(N, a)
    A = from_rank(N - 1, rank)
    A.append(a + 1)
    return A


from_rank(1, 1)

# for n in range(120):
#     A = from_rank(3, n)
#     m = to_rank(A)
#     print(n, A, m)


def ALICE():
    N, Q = map(int, input().split())
    A = [int(x) for x in input().split()]
    M = to_rank(A)
    S = bin(M)[2:]

    if N == 1:
        print(1)
        print(S)
        return

    #
    while len(S) < 384:
        S = "0" + S

    X = S[:7]
    Y = S[7:]
    n = int(X, 2)
    L = Y[0:n + 1]
    R = Y[n + 1:]

    print(2)
    print(L)
    print(R)


def BOB():
    N, Q = map(int, input().split())
    K = int(input())

    if N == 1:
        assert K == 1
        S = input()
        A = from_rank(N, int(S, 2))
        print(*A)
        return

    assert K == 2
    L = input()
    R = input()
    n = len(L) - 1
    X = bin(n)[2:]
    while len(X) < 7:
        X = "0" + X
    Y = L + R
    S = X + Y
    X = int(X, 2)
    A = from_rank(N, int(S, 2))
    print(*A)


P = input()
if P[0] == "A":
    ALICE()
else:
    BOB()
0