結果
問題 | No.1694 ZerOne |
ユーザー | LyricalMaestro |
提出日時 | 2024-08-12 14:26:55 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,378 bytes |
コンパイル時間 | 380 ms |
コンパイル使用メモリ | 82,556 KB |
実行使用メモリ | 281,188 KB |
最終ジャッジ日時 | 2024-08-12 14:27:00 |
合計ジャッジ時間 | 4,290 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
61,572 KB |
testcase_01 | AC | 38 ms
56,120 KB |
testcase_02 | AC | 39 ms
55,220 KB |
testcase_03 | TLE | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
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 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
ソースコード
## https://yukicoder.me/problems/no/1694 from collections import deque def main(): S = input() init_state = 0 for i in range(len(S)): if S[i] == "1": init_state |= (1 << i) states = {init_state:0} queue = deque() queue.append(init_state) while len(queue) > 0: state = queue.popleft() for l in range(2, (len(S) // 2) + 1): # 0, 1の状態を計算 array = [[-1, -1] for _ in range(len(S) + 1 - l)] cnt = [0, 0] for k in range(l): if state & (1 << k) > 0: cnt[1] += 1 else: cnt[0] += 1 array[0][0] = cnt[0] array[0][1] = cnt[1] for k in range(l, len(S)): if state & (1 << k) > 0: cnt[1] += 1 else: cnt[0] += 1 if state & (1 << (k - l)) > 0: cnt[1] -= 1 else: cnt[0] -= 1 array[k - (l - 1)][0] = cnt[0] array[k - (l - 1)][1] = cnt[1] a_set = {} for s_i in range(len(array)): cnt = array[s_i] if cnt[0] == 0 or cnt[1] == 0: continue t_cnt = tuple(cnt) if t_cnt not in a_set: a_set[t_cnt] = [] a_set[t_cnt].append(s_i) for value_indexes in a_set.values(): for indi in range(len(value_indexes)): s_i = value_indexes[indi] for indj in range(indi + 1, len(value_indexes)): t_i = value_indexes[indj] if s_i + l <= t_i: s_bit = (state & ((2 **l - 1) << s_i)) t_bit = (state & ((2 **l - 1) << t_i)) new_state = state - s_bit - t_bit new_state |= (s_bit >> s_i) << t_i new_state |= (t_bit >> t_i) << s_i if new_state not in states: states[new_state] = 0 queue.append(new_state) print(len(states)) if __name__ == '__main__': main()