結果
問題 | No.2067 ±2^k operations |
ユーザー |
👑 |
提出日時 | 2022-09-02 23:14:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 170 ms / 2,000 ms |
コード長 | 1,226 bytes |
コンパイル時間 | 317 ms |
コンパイル使用メモリ | 81,988 KB |
実行使用メモリ | 77,568 KB |
最終ジャッジ日時 | 2024-11-16 06:07:02 |
合計ジャッジ時間 | 4,774 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 23 |
ソースコード
"""直近が000...111...で遷移が変わるはず110113なんだよな"""bi = [1]for _ in range(60):bi.append(bi[-1] * 2)def solve(S):eq = 0ans = 0dp = [0, 0, 0, 0]eq = 1cnt = 1t = len(S) - 2flg = Truefor s in S[1:]:ndp = [0] * 4ndp[0] = dp[3]ndp[1] = dp[0] + dp[1] + dp[2]ndp[2] = dp[1]ndp[3] = dp[0] + dp[2] + dp[3]ans += (dp[0] + dp[1] + dp[2]) * bi[t]if s == "1":if cnt >= 2:ndp[0] += 1else:ndp[1] += 1ans += eq * bi[t]cnt += 1if cnt <= 2:eq += 1flg = Falseelif flg:cnt = 0else:if cnt == 1:cnt = 0else:cnt = 1flg = Truendp[2] += 1ans += bi[t]t -= 1dp = ndpans += eqreturn ansfor _ in range(int(input())):n = int(input())ans = solve(bin(n)[2:])print(ans)exit()print()bef = 0for i in range(1, 33):ans = solve(bin(i)[2:])print(bin(i)[2:], ans - bef, ans)bef = ans