結果

問題 No.1437 01 Sort
コンテスト
ユーザー zkou
提出日時 2021-03-22 17:04:05
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,770 bytes
コンパイル時間 307 ms
コンパイル使用メモリ 82,320 KB
実行使用メモリ 169,344 KB
最終ジャッジ日時 2024-11-24 03:55:37
合計ジャッジ時間 9,311 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17 WA * 5 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve(N, S):
    if list(S) == sorted(S):
        return 0

    one_cnt = S.count('1')
    S = S * 2

    ones = []
    for i, c in enumerate(S):
        if c == '1':
            ones.append(i)

    if S[0] == '0':
        last0 = N
    else:
        for last0 in reversed(range(N)):
            if S[last0] == '0':
                break

    answer = 10 ** 18

    flgsum = False

    l = 0
    r = one_cnt - 1
    t = ones[l]

    left0 = 0
    right1 = one_cnt - 1
    loop = max(right1, left0)
    answer_try = loop * N + (N - t - 1 - right1) % N
    roll = (t, left0, right1)
    if answer > answer_try:
        answer = answer_try
    while t < ones[r]:
        nt = t + 1
        new_left0 = left0 + (S[nt] == '0')
        new_right1 = right1 - (S[nt] == '1')
        if new_right1 < 0:
            break
        flg = (ones[l] <= last0 and N <= nt)
        flgsum = flgsum or flg
        if flgsum and not flg: # Add to original ?
            flgsum = False
            t = ones[l] - 1
            left0 = 0
            right1 = one_cnt
            continue
        new_loop = max(new_right1, max(new_left0 - flg, 0))
        new_answer_try = new_loop * N + (N - nt - 1 - new_right1) % N
        if loop < new_loop:
            break
        elif loop > new_loop:
            roll = (nt, new_left0, new_right1)
        right1 = new_right1
        left0 = new_left0
        loop = new_loop
        t = nt
        answer_try = new_answer_try
        if answer > answer_try:
            answer = answer_try
        # print(l, r, ones[l], t, ones[r], answer_try, left0, right1)



    for i in range(one_cnt - 1):
        t, left0, right1 = roll
        if t < ones[l + 1]:
            l = (l + 1)
            t = ones[l]
            r = (r + 1)
        else:
            nl = (l + 1)
            nr = (r + 1)
            left0 -= (ones[nl] - ones[l] - 1) % N
            right1 += 1
            l = nl
            r = nr
            flg = (ones[l] <= last0 and N <= t)
            flgsum = flgsum or flg
            if flgsum and not flg: # Add to original ?
                flgsum = False
                t = ones[l] - 1
                left0 = 0
                right1 = one_cnt
            loop = max(right1, max(new_left0 - flg, 0))
        answer_try = loop * N + (N - t - 1 - right1) % N
        roll = (t, left0, right1)
        if answer > answer_try:
            answer = answer_try
        while t < ones[r]:
            nt = t + 1
            new_left0 = left0 + (S[nt] == '0')
            new_right1 = right1 - (S[nt] == '1')
            flg = (ones[l] <= last0 and N <= nt)
            flgsum = flgsum or flg
            if flgsum and not flg: # Add to original ?
                flgsum = False
                t = ones[l] - 1
                left0 = 0
                right1 = one_cnt
                continue
            new_loop = max(new_right1, max(new_left0 - flg, 0))
            new_answer_try = new_loop * N + (N - nt - 1 - new_right1) % N
            if loop < new_loop:
                break
            elif loop > new_loop:
                roll = (nt, new_left0, new_right1)
            right1 = new_right1
            left0 = new_left0
            loop = new_loop
            t = nt
            answer_try = new_answer_try
            if answer > answer_try:
                answer = answer_try
            # print(l, r, ones[l], t, ones[r], answer_try, left0, right1)
    return (answer)


def slow(N, S):
    parent = dict()
    sorted_S = sorted(S)
    q = [(0, list(S))]
    while True:
        nq = []
        for t, Sp in q:
            # print(Sp, sorted_S)
            if Sp == sorted_S:
                tr = []
                Sp_str = ''.join(Sp)
                while Sp_str != S:
                    tr.append(Sp_str)
                    Sp_str = parent[Sp_str]
                tr.append(S)
                print(tr[::-1])
                for i in range(len(tr)):
                    k = i % N
                    print(tr[-i-1][k:] + tr[-i-1][:k])
                return t
            newSp = [Sp[-1]] + Sp[:-1]
            nq.append((t + 1, newSp))
            if ''.join(newSp) not in parent:
                parent[''.join(newSp)] = ''.join(Sp)
            newSp = [Sp[0]] + [Sp[-1]] + Sp[1:-1]
            nq.append((t + 1, newSp))
            if ''.join(newSp) not in parent:
                parent[''.join(newSp)] = ''.join(Sp)
        q = nq
    

def main():
    N = int(input())
    S = input()
    print(solve(N, S))
    # print(slow(N, S))

def test(t):
    import random
    for i in range(t):
        r = random.randint(1, 2 ** 9)
        S = bin(r)[2:]
        N = len(S)
        print(N, S)
        ac = slow(N, S)
        wa = solve(N, S)
        print(ac, wa)
        assert ac == wa

main()
# test(1000)
0