結果
問題 | No.1437 01 Sort |
ユーザー | zkou |
提出日時 | 2021-03-22 17:04:05 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,770 bytes |
コンパイル時間 | 356 ms |
コンパイル使用メモリ | 82,288 KB |
実行使用メモリ | 91,964 KB |
最終ジャッジ日時 | 2024-05-03 06:13:44 |
合計ジャッジ時間 | 4,880 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
58,496 KB |
testcase_01 | AC | 39 ms
52,864 KB |
testcase_02 | AC | 39 ms
52,608 KB |
testcase_03 | AC | 39 ms
52,864 KB |
testcase_04 | AC | 39 ms
52,864 KB |
testcase_05 | AC | 39 ms
52,864 KB |
testcase_06 | AC | 46 ms
53,120 KB |
testcase_07 | AC | 39 ms
52,736 KB |
testcase_08 | AC | 40 ms
52,480 KB |
testcase_09 | AC | 39 ms
52,736 KB |
testcase_10 | AC | 40 ms
53,120 KB |
testcase_11 | WA | - |
testcase_12 | AC | 40 ms
52,864 KB |
testcase_13 | TLE | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
ソースコード
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)