結果

問題 No.3 ビットすごろく
ユーザー トミートミー
提出日時 2024-01-04 03:31:51
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,175 bytes
コンパイル時間 2,364 ms
コンパイル使用メモリ 211,324 KB
実行使用メモリ 6,676 KB
最終ジャッジ日時 2024-01-04 03:31:56
合計ジャッジ時間 4,226 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 2 ms
6,676 KB
testcase_03 AC 2 ms
6,676 KB
testcase_04 AC 2 ms
6,676 KB
testcase_05 AC 2 ms
6,676 KB
testcase_06 AC 3 ms
6,676 KB
testcase_07 AC 2 ms
6,676 KB
testcase_08 AC 2 ms
6,676 KB
testcase_09 AC 3 ms
6,676 KB
testcase_10 AC 3 ms
6,676 KB
testcase_11 AC 3 ms
6,676 KB
testcase_12 AC 3 ms
6,676 KB
testcase_13 AC 3 ms
6,676 KB
testcase_14 AC 3 ms
6,676 KB
testcase_15 AC 3 ms
6,676 KB
testcase_16 AC 4 ms
6,676 KB
testcase_17 AC 3 ms
6,676 KB
testcase_18 AC 2 ms
6,676 KB
testcase_19 AC 3 ms
6,676 KB
testcase_20 AC 2 ms
6,676 KB
testcase_21 AC 2 ms
6,676 KB
testcase_22 AC 4 ms
6,676 KB
testcase_23 AC 4 ms
6,676 KB
testcase_24 AC 4 ms
6,676 KB
testcase_25 AC 4 ms
6,676 KB
testcase_26 AC 2 ms
6,676 KB
testcase_27 AC 2 ms
6,676 KB
testcase_28 AC 3 ms
6,676 KB
testcase_29 AC 3 ms
6,676 KB
testcase_30 AC 2 ms
6,676 KB
testcase_31 AC 2 ms
6,676 KB
testcase_32 AC 3 ms
6,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define REPP(i,n,m) for(int i=n;i<=m;i++)
#define REPM(i,n,m) for(int i=n;i>=m;i--)
#define VI vector<int>
using namespace std;
void yn(bool f){if(f){cout<<"Yes\n";}else{cout<<"No\n";}}
bool isnum(char c){return ('0'<=c&&c<='9');}

int btcnt(int n){
	int cnt=0;
	while(n!=0){
		cnt+=(n&1);
		n>>=1;
	}
	return cnt;
}

int main(){
	int n;
	cin>>n;
	if(n==1){
		cout<<1;
	}
	else{
		
		vector<vector<int>> adj(n+1);
		vector<bool> flag(n+1,false);
		deque<int> queue;
		vector<int> depthArray(n+1);
		int queuelen=1;
		bool solved=false;
		
		flag[1]=true;
		depthArray[1]=1;
		queue.push_front(1);
		
		for(int i=0;i<=n;i++){
			if(n>=i+btcnt(i)&&i+btcnt(i)>0){
				adj[i].push_back(i+btcnt(i));
			}
			if(n>=i-btcnt(i)&&i-btcnt(i)>0){
				adj[i].push_back(i-btcnt(i));
			}
		}
		while(queuelen!=0&&!solved){
			int v=queue.front();
			queue.pop_front();
			queuelen--;
			for(auto& u:adj[v]){
				if(u==n){
					solved=true;
				}
				if(!flag[u]){
					flag[u]=true;
					queue.push_back(u);
					queuelen++;
					depthArray[u]=depthArray[v]+1;
				}
			}
			
		}
		if(solved){
			cout<<depthArray[n];
		}
		else{
			cout<<-1;
		}
		
		
		
	}
	
	
}
0