結果

問題 No.262 面白くないビットすごろく
ユーザー hirokazu1020hirokazu1020
提出日時 2015-08-01 02:37:28
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 2,918 bytes
コンパイル時間 658 ms
コンパイル使用メモリ 83,156 KB
実行使用メモリ 7,600 KB
最終ジャッジ日時 2023-09-25 00:03:35
合計ジャッジ時間 4,500 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
7,492 KB
testcase_01 AC 247 ms
4,380 KB
testcase_02 TLE -
testcase_03 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<fstream>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())
#define indexOf(v,x) (find(all(v),x)-v.begin())



#if defined(_MSC_VER)||defined(__SSE4_2__)
#include<nmmintrin.h>
#endif

inline int popcount64(unsigned long long x){
#if defined(_MSC_VER) //Cf
	return __popcnt(x>>32)+__popcnt(x);
#elif defined(__GNUC__)
	return __builtin_popcountll(x);
#else 
	x = (x>>1 & 0x5555555555555555ULL)+(x & 0x5555555555555555ULL);
	x = (x>>2 & 0x3333333333333333ULL)+(x & 0x3333333333333333ULL);
	x = (x>>4 & 0x0f0f0f0f0f0f0f0fULL)+(x & 0x0f0f0f0f0f0f0f0fULL);
	x = (x>>8 & 0x00ff00ff00ff00ffULL)+(x & 0x00ff00ff00ff00ffULL);
	x = (x>>16& 0x0000ffff0000ffffULL)+(x & 0x0000ffff0000ffffULL);
	return ((x>>32)+(x & 0xffffffff));
#endif
}


long long pos[48]={
17783766827 ,
36597922058 ,
55728829658 ,
75271835395 ,
94749519875 ,
114724570219 ,
135675733668 ,
154888300991 ,
174703885783 ,
194982811608 ,
215555696869 ,
236309167965 ,
257608691826 ,
278800736335 ,
298028104037 ,
318086072310 ,
338747180679 ,
359091718042 ,
380081084166 ,
401389964696 ,
422407558678 ,
443212979522 ,
464479050991 ,
486175479780 ,
507764539058 ,
530019313303 ,
552431041517 ,
571588514724 ,
591580681943 ,
612174376769 ,
632548841747 ,
653606242405 ,
674792114825 ,
695982932450 ,
716630677540 ,
737892684385 ,
759673274442 ,
781163722659 ,
803366994623 ,
826195995327 ,
846368250656 ,
867481363526 ,
889237003125 ,
910710669981 ,
932654264548 ,
955327488252 ,
977123986647 ,
999145398059 ,
};
long long num[]={
1073741824
,2147483648
,3221225472
,4294967296
,5368709120
,6442450944
,7516192768
,8589934592
,9663676416
,10737418240
,11811160064
,12884901888
,13958643712
,15032385536
,16106127360
,17179869184
,18253611008
,19327352832
,20401094656
,21474836480
,22548578304
,23622320128
,24696061952
,25769803776
,26843545600
,27917287424
,28991029248
,30064771072
,31138512896
,32212254720
,33285996544
,34359738368
,35433480192
,36507222016
,37580963840
,38654705664
,39728447488
,40802189312
,41875931136
,42949672960
,44023414784
,45097156608
,46170898432
,47244640256
,48318382080
,49392123904
,50465865728
,51539607552
};





int main(){
	/*long long n,s=0,p=1,c=1;
	n=1000000000000;
	ofstream ofs("out.txt");
	while(p<=n){
		if((c&((1<<30)-1))==0)ofs<<p<<' '<<c<<endl;
		c++;
		p+=popcount64(p);
	}*/
	long long n,c=-1,m=0;
	long long *p;
	cin>>n;
	p=upper_bound(pos,pos+48,n);
	if(p==pos){
		m=1;
		c=1;
	}else {
		p--;
		m=*p;
		c=num[p-pos];
	}
	
	while(m<n){
		m+=popcount64(m);
		c++;
	}
	if(m==n)cout<<c<<endl;
	else cout<<-1<<endl;
	return 0;
}
0