#227581 (C++17) No.262 面白くないビットすごろく

• 問題: No.262 面白くないビットすごろく
• ユーザー: char134217728
• 提出日時: 2018-01-04 23:53:28
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 252 ms / 2,000 ms
• コード長: 15,910 bytes
• コンパイル時間: 1,736 ms
• コンパイル使用メモリ: 200,472 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-02 08:41:16
• 合計ジャッジ時間: 2,442 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	94 ms; 5,376 KB
testcase_03	AC	252 ms; 5,376 KB

コンパイルメッセージ

main.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main(){
      | ^~~~

ソースコード

#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define pcnt __builtin_popcountll
#define show(x) cout<<#x<<" = "<<x<<endl;
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define fi first
#define se second
#define rng(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define sz(x) (int)(x).size()
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
typedef __int128_t lll;
typedef pair<lll,lll> plll;
typedef vector<lll> vlll;
template<typename T>string join(vector<T>&v)
{stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
ll gcd(ll a,ll b){if(a>b)swap(a,b);for(;a>0;b%=a,swap(a,b));return b;}
int modpow(ll a,ll n,int m){if(a==0)return a;ll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(int)p;}
void dout(double d){printf("%.12f\n",d);}

const int iinf = 1e9;
const ll linf = 1e18;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-10;
ll A[1001]={
 1,12,10,3,10,18,12,3,3,12,3,10,10,18,12,10,4,3,18,4,12,12,3,11,10,20,3,11,10,12,3,7,8,20,4,3,3,20,18,18,10,10,10,4,4,12,10,10,3,3,3,8,12,10,10,11,10,12,18,3,4,12,8,4,1,12,3,3,18,12,12,11,12,3,3,10,1,20,3,3,10,7,10,20,10,12,18,3,8,12,10,3,10,9,3,3,4,10,12,10,4,3,8,20,10,3,10,3,10,12,10,10,3,20,18,10,3,13,4,7,8,10,10,3,8,12,8,10,13,22,10,10,4,8,4,10,7,20,18,10,10,16,10,3,10,12,4,4,4,12,3,3,13,3,3,11,12,9,12,11,3,10,8,20,3,12,1,12,3,12,10,3,1,3,12,10,1,12,10,20,10,3,12,3,3,20,12,11,4,12,4,4,8,22,10,8,10,13,3,10,8,10,12,6,7,1,1,3,10,3,4,11,3,10,4,20,3,10,18,1,10,12,3,8,4,12,3,10,1,3,3,10,12,7,7,1,8,10,8,10,1,12,10,1,10,12,4,10,17,7,10,11,1,21,3,8,8,22,8,4,10,13,10,10,8,6,8,3,8,10,3,7,8,10,21,10,3,20,10,10,10,12,12,10,10,10,4,11,10,10,10,3,18,18,18,12,8,12,10,6,4,20,12,11,8,10,4,3,4,13,10,11,10,3,12,4,10,10,10,10,4,3,10,3,20,20,1,18,4,12,10,11,8,3,18,8,4,20,18,7,10,3,4,12,13,10,12,4,10,12,10,20,13,18,10,3,10,13,1,11,3,10,12,10,10,10,4,6,4,3,21,3,8,12,10,8,8,8,18,10,8,9,8,10,1,3,8,8,3,20,8,10,10,18,7,7,4,20,10,10,1,7,10,8,10,3,1,3,1,20,13,3,8,10,12,7,3,3,4,10,18,3,10,3,4,7,10,1,8,12,1,10,4,3,10,11,3,7,8,10,3,7,10,4,4,12,7,10,8,10,10,10,4,13,10,10,13,3,12,3,4,6,10,7,10,12,8,8,8,12,8,12,7,20,10,3,20,12,3,8,13,20,10,10,3,12,8,3,3,7,10,3,8,12,10,11,1,3,8,8,10,12,10,3,13,3,13,10,4,10,8,20,7,20,8,20,1,7,18,20,3,10,7,6,3,10,10,7,1,7,21,4,17,10,4,10,7,20,10,17,4,7,8,7,8,10,10,8,8,20,10,12,12,12,3,10,3,10,10,3,3,10,18,10,18,3,10,11,3,3,10,3,8,10,10,3,3,20,10,20,10,10,4,10,7,20,3,4,1,18,18,10,1,10,10,10,10,1,1,20,8,12,3,3,10,12,10,10,7,3,10,11,18,12,4,3,8,10,7,10,10,3,10,10,10,10,12,20,8,10,18,12,10,20,10,4,10,12,3,4,8,22,4,20,3,7,4,11,17,3,3,1,8,3,3,3,8,12,18,7,10,22,10,3,8,12,12,10,7,10,28,7,8,3,21,10,1,12,1,12,3,12,12,1,8,20,8,4,8,20,10,4,10,3,18,10,10,12,18,20,3,9,1,10,8,3,3,1,10,20,4,10,3,3,7,3,8,20,10,8,4,14,10,10,10,20,3,10,10,20,3,1,8,10,1,4,8,12,4,4,8,10,4,10,1,8,10,8,10,10,17,6,1,20,8,20,3,12,10,7,7,3,12,10,1,10,10,10,13,22,4,4,1,8,8,10,4,12,3,11,7,12,10,8,3,22,3,7,8,10,1,10,8,20,3,3,3,9,3,10,13,22,8,8,3,20,7,7,10,20,12,8,8,20,4,3,12,1,21,4,20,7,4,7,8,20,10,3,10,12,8,7,4,3,12,3,18,10,3,3,7,3,12,3,10,12,4,10,8,20,8,4,3,10,8,3,7,3,10,3,8,9,10,8,8,3,4,20,3,12,10,3,12,12,13,3,8,18,3,4,4,22,8,8,10,10,18,3,8,8,10,19,1,21,10,3,1,22,10,10,10,12,3,1,8,20,7,6,3,9,10,4,8,10,4,8,18,20,4,20,8,7,1,6,3,7,8,20,10,20,10,20,8,20,7,20,20,3,10,3,8,12,8,20,13,20,21,8,3,7,4,10,17,14,18,19,4,9,7,7,8,12,7,4,10,13,3,11,4,12,10,11,8,10,4,10,4,8,8,8,10,18,4,19,7,12,10,6,3,12,10,8,12,12,4,8,8,10,8,11,1
}, B[1001]={
  1,68893379,133259591,197306960,258074468,321058221,382283055,442079943,500336881,560227456,622527994,682263310,741445786,798255889,857654838,914069998,970961803,1024948204,1087295678,1148272938,1208239027,1266032467,1324334749,1382824742,1439392570,1494819498,1549934741,1609100783,1665400173,1721448008,1775209790,1831848235,1885921502,1939492010,1991112178,2050766614,2112089871,2172073888,2230540789,2288414772,2347070139,2403605820,2459496598,2513177555,2572867295,2629831324,2686613447,2740669518,2796708683,2851139772,2904639475,2956417011,3011953153,3070471970,3126979592,3182557544,3236564856,3292540797,3345675612,3399342161,3450440323,3506572034,3560670104,3614368952,3666026060,3718408310,3770426294,3821300803,3871117137,3924201552,3986979946,4046654586,4106081960,4162299846,4222649856,4279677383,4336351952,4390617398,4448907149,4506623060,4562967535,4618135436,4673002392,4728449967,4781815192,4834711164,4886411694,4945825903,5002429447,5059264500,5113278404,5169320974,5223781411,5277319553,5329104825,5382955823,5438195024,5491726909,5544231781,5595619698,5648497295,5699054575,5749487500,5798115491,5857595712,5914749517,5971396760,6025839571,6081377194,6135983289,6189595487,6241916689,6294820896,6350315936,6403795947,6456745143,6507366547,6560831994,6611950056,6662905993,6711648450,6766476490,6820913441,6874428795,6926316662,6978562171,7030960758,7081651500,7131721775,7180825296,7233861602,7284235157,7335308949,7383946129,7434580247,7483421882,7531839826,7578661200,7635236241,7697055297,7757077932,7815715894,7873058681,7932249087,7988577994,8044653415,8098012333,8158200422,8215272556,8271911022,8326242088,8381944927,8436540546,8489905558,8542261777,8596915673,8655602906,8712015325,8767882313,8821503977,8877552279,8931277229,8984991041,9036279047,9091851779,9146297230,9199821997,9251584778,9303831279,9356171278,9406948647,9456804991,9507772972,9566975567,9623267240,9679543313,9733434435,9789975117,9844038500,9897678920,9949281447,10003792381,10058377960,10112100641,10164470482,10216181230,10268809154,10319505606,10369813965,10418075498,10474741638,10528615269,10582315243,10633600196,10686641977,10738286605,10789015399,10838422600,10889263629,10941706579,10992345971,11042480940,11091014413,11141401193,11189446688,11238047136,11284442708,11342692541,11400043716,11456704383,11511253813,11566358838,11621500042,11675030116,11727558944,11779819896,11835695130,11888992017,11942064853,11992859175,12046543940,12097772160,12148568205,12197611505,12251694863,12306324279,12359755044,12412095484,12463983381,12516495567,12567201826,12617413973,12665991339,12719059556,12770192510,12821170415,12869928561,12920299146,12969355125,13017676801,13064569631,13116119347,13171350401,13224844768,13277398041,13328753819,13381693538,13432205283,13482893638,13531516435,13584772394,13636026472,13686943500,13735979681,13785865978,13835161648,13883608315,13931009795,13979504601,14032227055,14082889109,14133219767,14181207648,14232225569,14280860013,14329327186,14375873685,14425570429,14474683511,14522917961,14570088152,14617220833,14664680717,14710598876,14756230527,14803053091,14866225579,14925927517,14986265249,15043328397,15102901646,15160331795,15216929503,15271514456,15328480420,15386984215,15443553442,15498993161,15553194664,15609054522,15662358066,15715418486,15766356253,15826159190,15883308182,15939920147,15994362686,16049976945,16104592423,16158092431,16210438554,16263461084,16318888957,16372352529,16425238888,16476018007,16529247955,16580373360,16631338620,16680086231,16737769616,16795335104,16851890142,16906483785,16961690624,17016966940,17070458270,17123074150,17174950077,17230890570,17284061996,17337647739,17388756481,17442181830,17493429253,17544397267,17593488535,17646855915,17701690242,17755314900,17807754287,17859287687,17912067603,17962675317,18013029620,18061051667,18114910348,18166062377,18216970316,18265841953,18316057310,18365210709,18413392955,18460653078,18512811702,18571535301,18627907994,18683776001,18737478153,18793523773,18847023235,18900817010,18952032974,19007700102,19062077239,19115623623,19167414472,19219600213,19271947279,19322726451,19372604726,19422941152,19478787182,19532070445,19585117795,19636226456,19689807271,19741077501,19791923965,19840983418,19892786562,19944564038,19995393521,20045107047,20094326963,20144210085,20192521559,20240354779,20286812865,20343211783,20397099061,20450824469,20502075677,20555132614,20606722070,20657498201,20706775955,20757770915,20810168846,20860876478,20910906300,20959582579,21009901081,21057882587,21106382415,21152733653,21205582997,21256911392,21307838382,21356948180,21406663385,21456158031,21504528504,21551986324,21599340914,21649528392,21697684749,21745651073,21791570282,21840108257,21886513345,21932668415,21977247105,22032765700,22090499681,22146811735,22202085605,22256916738,22312357720,22365738137,22418619531,22469874592,22525931819,22579576162,22633319952,22684554459,22737643133,22789267578,22840061963,22889275723,22941965870,22997229960,23050749231,23103246849,23154628689,23207487337,23258082556,23308580465,23357203057,23410563852,23461818718,23512704452,23561764436,23611689892,23660887009,23709303731,23756675358,23806512279,23862038008,23915494214,23968452300,24019036913,24072586010,24123691686,24174646838,24223376757,24275846139,24327485032,24378233442,24427599239,24477185052,24526980271,24575197079,24622891068,24670092483,24723131042,24773537932,24824662600,24873302579,24923908688,24972770853,25021173629,25068015340,25116725355,25166323441,25214648447,25262135769,25308734245,25356544942,25402475776,25448230516,25492236915,25548761491,25602750833,25656319523,25707862221,25760574712,25812372246,25863040051,25912772321,25963227390,26015729128,26066427640,26116641736,26165009849,26215373392,26263928405,26312425247,26358914392,26411098174,26462710771,26513488077,26562705714,26612343806,26662058296,26710362411,26757832996,26804969942,26855218742,26903312512,26951487944,26997835974,27046135568,27092611591,27138793405,27183456062,27233513116,27285348708,27336299916,27386057975,27435168073,27485170427,27533405061,27581301057,27627179926,27678132439,27726725638,27775211168,27821734145,27869617955,27916421232,27962431775,28007444758,28054640597,28104460510,28152624567,28200381644,28246654269,28294624737,28340513178,28386841642,28431184673,28478973586,28525619603,28571742908,28616509167,28661560942,28706768564,28750833408,28794209890,28842294795,28905186179,28964871069,29024268121,29080912125,29141037405,29198148725,29254728214,29309186074,29367170406,29424967689,29481456857,29536704007,29591438990,29646855940,29700314882,29753185651,29804503416,29864014334,29920990330,29977786884,30031835556,30087884718,30142325907,30195839987,30247608847,30301434929,30356667064,30410188912,30462769173,30514081134,30567033733,30617511319,30668291595,30716904513,30775993046,30833122275,30889859071,30944323366,30999721831,31054502386,31108158627,31160560928,31213149133,31268843077,31322196448,31375230687,31425584168,31479496111,31530637849,31581567653,31630418873,31684919690,31739467818,31792852286,31845019592,31897049165,31949521357,32000147932,32050381058,32099238035,32152316731,32202990880,32254045637,32302741063,32353195621,32402185241,32450499646,32497409774,32551101145,32609591857,32666158607,32721584519,32775796735,32831655359,32884942408,32938001296,32989010364,33045508593,33099580207,33153152633,33204770257,33257402540,33309179907,33359986547,33409698617,33461157567,33516562801,33570065316,33622988313,33673705811,33727022843,33778135478,33829101918,33877853900,33930368788,33981976675,34032741869,34081959056,34131660215,34181408364,34229685130,34277288021,34325312559,34381288713,34434419167,34488092437,34539188452,34592595750,34643902701,34694844421,34743950376,34795369738,34847393331,34898265923,34948082630,34997030702,35047179871,35095312743,35143286697,35189153260,35242936517,35294100315,35344979105,35393901555,35444069626,35493236339,35541392994,35588698098,35636825064,35686709681,35734899440,35782707383,35828886343,35876851414,35922974203,35969239653,36013628678,36070900958,36128511987,36185090982,36239720085,36294815630,36350051418,36403585146,36456091000,36508230343,36564070737,36617336915,36670475371,36721602683,36775159520,36826427008,36877280470,36926349562,36980123985,37034730897,37088344838,37140664989,37192453164,37245019146,37295767291,37346034592,37394326368,37447800007,37498916595,37549873315,37598613251,37648963795,37698029779,37746340905,37793332372,37844577296,37899889336,37953304897,38006036408,38057158348,38110192274,38160563603,38211645123,38260282435,38313330273,38364700291,38415596635,38464725898,38514409378,38563944577,38612299315,38659763286,38707880970,38760794776,38811389298,38861784878,38909973383,38960970876,39009664604,39058034694,39104721938,39154152250,39203347804,39251538904,39298907368,39345928455,39393421262,39439409416,39485035016,39530249158,39586299701,39640027984,39693744652,39745030431,39798105992,39849725029,39900513757,39949714551,40000796801,40053136798,40103913396,40153769454,40202608515,40252853905,40300971699,40349088867,40395447353,40448582465,40499859499,40550752322,40599806638,40649707029,40698886606,40747372532,40794754856,40842456201,40892436453,40940670216,40988559536,41034433015,41082838570,41129184850,41175397824,41219833290,41271204736,41322851146,41373578055,41422987701,41472546648,41522358757,41570544176,41618273689,41664941793,41715334144,41763381832,41811982121,41858376596,41906483985,41953101213,41999249406,42044000184,42091800496,42141440213,42189765544,42237274776,42283860365,42331675768,42377593888,42423349647,42467417030,42515787485,42562239893,42608330177,42652991930,42698463164,42743263085,42787257264,42830516276,42879866836,42938555865,42995017858,43050869401,43104414949,43160478747,43214385710,43268118096,43319392668,43374910945,43429341914,43482868518,43534639023,43586906812,43639232091,43689996304,43739907828,43789986623,43845900150,43899115238,43952535353,44003656521,44057131437,44108386154,44159304409,44208343923,44259953435,44311826333,44362754634,44412525321,44461580936,44511644575,44559849001,44607756843,44653623140,44710470636,44764386221,44818091501,44869438266,44922394390,44974059527,45024753921,45074271625,45124990629,45177458723,45228036686,45278272231,45326777467,45377170940,45425333727,45473894882,45520319337,45572819759,45624315341,45675128938,45724311857,45773867693,45823605113,45871928648,45919424834,45966662798,46016885033,46065023007,46112965771,46159179567,46207557209,46254039379,46300157829,46344835665,46397425336,46452040635,46505543966,46557889914,46609727016,46662228315,46712962404,46763178604,46811682021,46864914811,46916041921,46967006457,47015754564,47066127891,47115179597,47163492546,47210370402,47260302074,47312670017,47363425343,47413396560,47462138029,47512428498,47560459107,47608831244,47655183406,47705644461,47754383950,47802864066,47849652415,47897073524,47944129862,47990289696,48035576892,48082547945,48135332378,48185936754,48236295662,48284319307,48335417278,48384068012,48432493864,48479087062,48528688942,48577843341,48626023725,48673287136,48720335006,48767850905,48813810542,48859439447,48904206513,48954574344,49002882587,49051418731,49097859263,49145834216,49192551562,49238655926,49283463255,49329769173,49377130277,49423206696,49468552755,49513048939,49558665052,49602556140,49646288703,49688710985,49744658348,49798718214,49852308207,49903914517,49956535721,50008311554,50059144371,50108854941,50159094561,50211622213,50262399231,50312650254,50360866599,50411529345,50460146516,50508628923,50555097791,50607095355,50658684536,50709462627,50758743358,50808399506,50858169911,50906415298,50954054324,51000913558,51051231023,51099213331,51147716752,51194070184,51242282605,51288814448,51335012612,51379727681,51429382479,51481475435,51532317307,0
};
const ll i9 = 1e9;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n, a, c;
  cin >> n;
  a = n/i9 * i9 + A[n/i9];
  c = B[n/i9];
  while(a < n){
    a += pcnt(a);
    c++;
  }
  if(a == n){
    cout << c << endl;
  }else{
    cout << -1 << endl;
  }
  return 0;
}