結果

問題 No.262 面白くないビットすごろく
ユーザー hirokazu1020hirokazu1020
提出日時 2015-08-01 02:37:28
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 2,918 bytes
コンパイル時間 627 ms
コンパイル使用メモリ 83,096 KB
実行使用メモリ 13,756 KB
最終ジャッジ日時 2024-07-18 00:20:53
合計ジャッジ時間 4,331 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
13,756 KB
testcase_01 AC 245 ms
6,940 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