結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2020-12-21 06:37:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 58 ms / 5,000 ms |
コード長 | 1,302 bytes |
コンパイル時間 | 165 ms |
コンパイル使用メモリ | 81,536 KB |
実行使用メモリ | 65,592 KB |
最終ジャッジ日時 | 2024-07-01 10:01:18 |
合計ジャッジ時間 | 2,849 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
import sysfrom collections import dequesys.setrecursionlimit(10**7)def I(): return int(sys.stdin.readline().rstrip())def MI(): return map(int,sys.stdin.readline().rstrip().split())def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))def LI2(): return list(map(int,sys.stdin.readline().rstrip()))def S(): return sys.stdin.readline().rstrip()def LS(): return list(sys.stdin.readline().rstrip().split())def LS2(): return list(sys.stdin.readline().rstrip())def popcount(n):c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)return cN = I()P = [popcount(i) for i in range(N+1)]inf = 10**18dist = [inf]*(N+1)dist[1] = 1deq = deque([1])while deq:i = deq.pop()j,k = i+P[i],i-P[i]if j <= N and dist[j] == inf:dist[j] = dist[i]+1deq.appendleft(j)if k > 0 and dist[k] == inf:dist[k] = dist[i]+1deq.appendleft(k)ans = dist[-1]print(ans if ans != inf else -1)