結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2018-09-08 15:22:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 814 bytes |
コンパイル時間 | 1,938 ms |
コンパイル使用メモリ | 179,420 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-01 09:06:49 |
合計ジャッジ時間 | 2,970 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; vector<int> a; vector<bool> b; vector<int> c; int bitsum(int n){ int ans=0; while(n>0){ if(n&1) ans++; n>>=1; } return ans; } int main(){ int n;cin >> n; a.resize(n+1); b.resize(n+1,false); c.resize(n+1,100000000); for(int i=1;i<=n;++i){ a.at(i)=bitsum(i); } queue<int> q; q.push(1); c.at(1)=1; while(!q.empty()){ int np=q.front(); q.pop(); if(b.at(np)) continue; b.at(np)=true; if(0<np-a.at(np) && np-a.at(np)<=n && !b.at(np-a.at(np))){ c.at(np-a.at(np))=min(c.at(np)+1,c.at(np-a.at(np))); q.push(np-a.at(np)); } if(0<np+a.at(np) && np+a.at(np)<=n && !b.at(np+a.at(np))){ c.at(np+a.at(np))=min(c.at(np)+1,c.at(np+a.at(np))); q.push(np+a.at(np)); } } if(b.at(n)) cout << c.at(n) << endl; else cout << -1 << endl; }