結果

問題 No.3 ビットすごろく
コンテスト
ユーザー abinull
提出日時 2025-06-29 16:18:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 828 bytes
コンパイル時間 916 ms
コンパイル使用メモリ 84,076 KB
実行使用メモリ 28,424 KB
最終ジャッジ日時 2025-06-29 16:19:11
合計ジャッジ時間 35,173 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 WA * 16 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <bitset>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

int main() {

  int n;
  int t;
  
  cin >> n;

  vector<int> w(n+1,0);
  vector<bool> v(n+1, false);

  queue<int> q;

  /*for (int i=1; i<=n; i++) {
      cout << __popcnt(i) << " ";
  }
cout << endl;*/

 int u, ub, uf;
  q.push(1);
  u = 1; w[1] = 1;

  while (!q.empty()) {

      u = q.front(); q.pop();
      v[u] = true;

      if (v[n]==true) {cout << w[n] << endl;return 0;}

      ub = u - __popcount(u); uf = u + __popcount(u);

      if (ub>0 && v[ub]==false) {
        q.push(ub);
        w[ub] = w[u] +1; 
      }

      if (uf<=n && v[uf]==false) {
        q.push(uf);
        w[uf] = w[u] +1;
      }
  } 
  cout << -1 << endl;

  return 0;
}
0