結果
| 問題 | No.262 面白くないビットすごろく |
| ユーザー |
 hirokazu1020
|
| 提出日時 | 2015-08-01 03:17:14 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
AC
|
| 実行時間 | 542 ms / 2,000 ms |
| コード長 | 11,398 bytes |
| コンパイル時間 | 702 ms |
| コンパイル使用メモリ | 83,524 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-07-18 00:21:15 |
| 合計ジャッジ時間 | 2,196 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 245 ms
5,376 KB |
| testcase_02 | AC | 542 ms
5,376 KB |
| testcase_03 | AC | 245 ms
5,376 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:456:18: warning: ‘c’ may be used uninitialized in this function [-Wmaybe-uninitialized]
456 | c++;
| ~^~
ソースコード
#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)
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 umekomi[385*2]={
1,1,
2016542071,134217728,
4179858569,268435456,
6351146542,402653184,
8647178755,536870912,
10819798116,671088640,
13112582219,805306368,
15435178180,939524096,
17783766827,1073741824,
19995222517,1207959552,
22298558097,1342177280,
24671210129,1476395008,
27025469753,1610612736,
29419673939,1744830464,
31867924532,1879048192,
34425213697,2013265920,
36597922058,2147483648,
38891625631,2281701376,
41213834226,2415919104,
43603505547,2550136832,
45958473687,2684354560,
48400385439,2818572288,
50924749040,2952790016,
53293089791,3087007744,
55728829658,3221225472,
58170653878,3355443200,
60697569081,3489660928,
63183433146,3623878656,
65758854595,3758096384,
68442700319,3892314112,
70661484582,4026531840,
72969132463,4160749568,
75271835395,4294967296,
77670276594,4429185024,
80006937100,4563402752,
82439330605,4697620480,
84946429638,4831838208,
87342403410,4966055936,
89751965666,5100273664,
92208054462,5234491392,
94749519875,5368709120,
97211131403,5502926848,
99784395545,5637144576,
102436113901,5771362304,
104834038943,5905580032,
107270116149,6039797760,
109711750702,6174015488,
112238661111,6308233216,
114724570219,6442450944,
117300162543,6576668672,
119984139589,6710886400,
122462777612,6845104128,
125014691055,6979321856,
127634170589,7113539584,
130264415683,7247757312,
132956946308,7381975040,
135675733668,7516192768,
138241056728,7650410496,
140465265264,7784628224,
142776316130,7918845952,
145148534275,8053063680,
147499482149,8187281408,
149910559561,8321499136,
152366833793,8455716864,
154888300991,8589934592,
157211169976,8724152320,
159643294324,8858370048,
162150468133,8992587776,
164635228850,9126805504,
167185535816,9261023232,
169776711171,9395240960,
172359558766,9529458688,
174703885783,9663676416,
177151125559,9797894144,
179661385814,9932111872,
182144512242,10066329600,
184720666574,10200547328,
187296671048,10334765056,
189891036698,10468982784,
192401104118,10603200512,
194982811608,10737418240,
197678486903,10871635968,
200266485344,11005853696,
202974372890,11140071424,
205774323592,11274289152,
208155048164,11408506880,
210586658775,11542724608,
213035163652,11676942336,
215555696869,11811160064,
218060036927,11945377792,
220640220678,12079595520,
223347436431,12213813248,
225780105414,12348030976,
228341866325,12482248704,
230981581406,12616466432,
233605999277,12750684160,
236309167965,12884901888,
239030208489,13019119616,
241672580826,13153337344,
244196748680,13287555072,
246787509975,13421772800,
249456655551,13555990528,
252067337555,13690208256,
254776255621,13824425984,
257608691826,13958643712,
260191183456,14092861440,
262892179649,14227079168,
265681778420,14361296896,
268446156869,14495514624,
271259619702,14629732352,
274171913146,14763950080,
276521441675,14898167808,
278800736335,15032385536,
281114470250,15166603264,
283544884029,15300820992,
285852835570,15435038720,
288283924375,15569256448,
290763748771,15703474176,
293199756432,15837691904,
295581351848,15971909632,
298028104037,16106127360,
300602170446,16240345088,
303040709490,16374562816,
305601134527,16508780544,
308237808535,16642998272,
310678988857,16777216000,
313088582760,16911433728,
315544482879,17045651456,
318086072310,17179869184,
320547859886,17314086912,
323120861173,17448304640,
325772537435,17582522368,
328282611788,17716740096,
330849410482,17850957824,
333437897824,17985175552,
336090631822,18119393280,
338747180679,18253611008,
341480974806,18387828736,
344155541592,18522046464,
346499527149,18656264192,
348946227830,18790481920,
351456846484,18924699648,
353940162160,19058917376,
356516609308,19193135104,
359091718042,19327352832,
361686532100,19461570560,
364196152147,19595788288,
366777957353,19730006016,
369474099733,19864223744,
372062036344,19998441472,
374769985423,20132659200,
377569335023,20266876928,
380081084166,20401094656,
382628039435,20535312384,
385240053763,20669530112,
387877100790,20803747840,
390560526683,20937965568,
393282398741,21072183296,
396015792087,21206401024,
398662931024,21340618752,
401389964696,21474836480,
404188416745,21609054208,
406953341933,21743271936,
409799362270,21877489664,
412648707113,22011707392,
414982515610,22145925120,
417415920338,22280142848,
419920030228,22414360576,
422407558678,22548578304,
424964298081,22682796032,
427549812403,22817013760,
430162455060,22951231488,
432661629018,23085449216,
435232387291,23219666944,
437927773242,23353884672,
440516068395,23488102400,
443212979522,23622320128,
445996903475,23756537856,
448536527790,23890755584,
451104150699,24024973312,
453692236398,24159191040,
456345415402,24293408768,
459000578672,24427626496,
461735174237,24561844224,
464479050991,24696061952,
467115094192,24830279680,
469827406203,24964497408,
472646469342,25098715136,
475380930467,25232932864,
478226828698,25367150592,
481160082435,25501368320,
483608128691,25635586048,
486175479780,25769803776,
488822525399,25904021504,
491443091627,26038239232,
494140462121,26172456960,
496878054426,26306674688,
499572441362,26440892416,
502258684900,26575110144,
504978951149,26709327872,
507764539058,26843545600,
510559467944,26977763328,
513420839485,27111981056,
516239972036,27246198784,
518887028634,27380416512,
521610553228,27514634240,
524411125776,27648851968,
527171730268,27783069696,
530019313303,27917287424,
532938068951,28051505152,
535690699690,28185722880,
538540163469,28319940608,
541483251731,28454158336,
544375470226,28588376064,
547361940036,28722593792,
550225278381,28856811520,
552431041517,28991029248,
554727669221,29125246976,
557084373276,29259464704,
559459305587,29393682432,
561839186032,29527900160,
564284783501,29662117888,
566853429503,29796335616,
569167508599,29930553344,
571588514724,30064771072,
574059188182,30198988800,
576577860148,30333206528,
579088582777,30467424256,
581676679524,30601641984,
584328247525,30735859712,
586648762205,30870077440,
589081292737,31004295168,
591580681943,31138512896,
594071320014,31272730624,
596615205825,31406948352,
599211144408,31541166080,
601835128621,31675383808,
604315857287,31809601536,
606889957436,31943819264,
609570400469,32078036992,
612174376769,32212254720,
614864044320,32346472448,
617639156877,32480690176,
620097194685,32614907904,
622517545445,32749125632,
624972403825,32883343360,
627497010443,33017561088,
629972677602,33151778816,
632548841747,33285996544,
635217857653,33420214272,
637714246142,33554432000,
640267674815,33688649728,
642874013266,33822867456,
645512988221,33957085184,
648190092126,34091302912,
650915905967,34225520640,
653606242405,34359738368,
656111984342,34493956096,
658687379474,34628173824,
661395430381,34762391552,
663967787129,34896609280,
666671284040,35030827008,
669465057593,35165044736,
672108003115,35299262464,
674792114825,35433480192,
677556103806,35567697920,
680314494230,35701915648,
683145157173,35836133376,
686025123273,35970351104,
688576597632,36104568832,
690983419885,36238786560,
693433886325,36373004288,
695982932450,36507222016,
698441455108,36641439744,
701010169220,36775657472,
703658457677,36909875200,
706172636493,37044092928,
708745314059,37178310656,
711328510130,37312528384,
713978535525,37446746112,
716630677540,37580963840,
719367061827,37715181568,
722090104641,37849399296,
724569752176,37983617024,
727144027882,38117834752,
729824064813,38252052480,
732428969549,38386270208,
735118281667,38520487936,
737892684385,38654705664,
740551497237,38788923392,
743248844904,38923141120,
745986457298,39057358848,
748755133674,39191576576,
751597061404,39325794304,
754444883408,39460012032,
757137463386,39594229760,
759673274442,39728447488,
762264136776,39862665216,
764925312743,39996882944,
767540666658,40131100672,
770251054933,40265318400,
773095770910,40399536128,
775663624674,40533753856,
778368775225,40667971584,
781163722659,40802189312,
783915824272,40936407040,
786736748483,41070624768,
789656319354,41204842496,
792328577274,41339060224,
795014454005,41473277952,
797778250150,41607495680,
800536611606,41741713408,
803366994623,41875931136,
806243657141,42010148864,
809063904614,42144366592,
811893354710,42278584320,
814761014195,42412802048,
817667902979,42547019776,
820627453229,42681237504,
823650060126,42815455232,
826195995327,42949672960,
828612440851,43083890688,
831077047597,43218108416,
833597627570,43352326144,
836068832557,43486543872,
838647038463,43620761600,
841310374496,43754979328,
843808447973,43889197056,
846368250656,44023414784,
848966127935,44157632512,
851610921820,44291850240,
854280918759,44426067968,
857008597012,44560285696,
859704793829,44694503424,
862213151388,44828721152,
864780731605,44962938880,
867481363526,45097156608,
870062275305,45231374336,
872762121434,45365592064,
875550051951,45499809792,
878198171106,45634027520,
880885470079,45768245248,
883644514120,45902462976,
886407041817,46036680704,
889237003125,46170898432,
892109534187,46305116160,
894761642004,46439333888,
897309737568,46573551616,
899901725685,46707769344,
902555203259,46841987072,
905190813817,46976204800,
907901932075,47110422528,
910710669981,47244640256,
913303452698,47378857984,
916012702837,47513075712,
918823458017,47647293440,
921559060330,47781511168,
924394097805,47915728896,
927326782087,48049946624,
929966223364,48184164352,
932654264548,48318382080,
935426562441,48452599808,
938189679642,48586817536,
941013717345,48721035264,
943908862437,48855252992,
946710721889,48989470720,
949537429585,49123688448,
952431438722,49257906176,
955327488252,49392123904,
958287695828,49526341632,
961323916125,49660559360,
963924738955,49794777088,
966492737517,49928994816,
969080925079,50063212544,
971734774348,50197430272,
974388247512,50331648000,
977123986647,50465865728,
979867932939,50600083456,
982503823698,50734301184,
985215205279,50868518912,
988034643437,51002736640,
990768335853,51136954368,
993614895574,51271172096,
996557223110,51405389824,
999145398059,51539607552
};
int main(){
/*long long n,s=0,p=1,c=1;
n=1000000000000;
ofstream ofs("out.txt");
while(p<=n){
if((c&((1<<27)-1))==0)ofs<<p<<','<<c<<','<<endl;
c++;
p+=popcount64(p);
}*/
long long n,c,p=1;
cin>>n;
rep(i,385){
if(umekomi[i*2]<=n){
p=umekomi[i*2];
c=umekomi[i*2+1];
}
}
while(p<n){
p+=popcount64(p);
c++;
}
if(p==n)cout<<c<<endl;
else cout<<-1<<endl;
return 0;
}