結果
問題 | No.3 ビットすごろく |
ユーザー |
|
提出日時 | 2023-11-06 19:32:59 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 2,254 ms / 5,000 ms |
コード長 | 1,718 bytes |
コンパイル時間 | 3,201 ms |
コンパイル使用メモリ | 78,516 KB |
実行使用メモリ | 82,960 KB |
最終ジャッジ日時 | 2024-09-25 23:07:33 |
合計ジャッジ時間 | 24,555 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
import java.util.*; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); boolean[] seen = new boolean[n+1]; seen[0] = true; LinkedList<Integer> q = new LinkedList<>(); LinkedList<Integer> next_q = new LinkedList<>(); q.push(1); int turn = 0; boolean flag = false; for(int i = 0 ; q.size() > 0 ; i++){ turn++; while(q.size() > 0){ int v = q.pop(); if(v == n){ flag = true; break; } seen[v] = true; int left = v - getBitCount(v); int right = v + getBitCount(v); if(left > 0 && !seen[left]){ next_q.push(left); } if(right <= n && !seen[right]){ next_q.push(right); } } if(flag){ break; } q.addAll(next_q); next_q.clear(); } System.out.println(flag ? turn : -1); } private static int getBitCount(int bits){ bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555); bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333); bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f); bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff); return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff); } }