結果

問題 No.262 面白くないビットすごろく
ユーザー しらっ亭しらっ亭
提出日時 2017-03-05 01:43:32
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 426 ms / 2,000 ms
コード長 9,633 bytes
コンパイル時間 1,358 ms
コンパイル使用メモリ 166,628 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-23 02:12:44
合計ジャッジ時間 2,755 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 426 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 418 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define _p(...) (void)printf(__VA_ARGS__)
#define forr(x,arr) for(auto&& x:arr)
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) _rep3(i,0,n)
#define _rep3(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2,)(__VA_ARGS__)
#define _rrep2(i,n) _rrep3(i,0,n)
#define _rrep3(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2,)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
#define bit(n) (1LL<<(n))
#define sz(x) ((int)(x).size())
#define fst first
#define snd second
using ll=long long;
using pii=pair<int,int>;using pll=pair<ll,ll>;using pil=pair<int,ll>;using pli=pair<ll,int>;
using vs=vector<string>;using vvs=vector<vs>;using vvvs=vector<vvs>;
using vb=vector<bool>;using vvb=vector<vb>;using vvvb=vector<vvb>;
using vi=vector<int>;using vvi=vector<vi>;using vvvi=vector<vvi>;
using vl=vector<ll>;using vvl=vector<vl>;using vvvl=vector<vvl>;
using vd=vector<double>;using vvd=vector<vd>;using vvvd=vector<vvd>;
using vpii=vector<pii>;using vvpii=vector<vpii>;using vvvpii=vector<vvpii>;
template<class T,class U>istream&operator>>(istream&is,pair<T,U>&P){is>>P.fst;is>>P.snd;return is;}
template<class T>T read(){T t;cin>>t;return t;}
template<class T,class U>ostream&operator<<(ostream&o,const pair<T,U>&p){return o<<'('<<p.fst<<", "<<p.snd<<')';}
template<class T>ostream&operator<<(ostream&o,const vector<T>&t){o<<"{";rep(i,sz(t))o<<t[i]<<",";o<<"}"<<endl;return o;}
#ifdef LOCAL
vs s_p_l_i_t(const string&s,char c){vs v;stringstream ss(s);string x;while(getline(ss,x,c))v.emplace_back(x);return move(v);}
void e_r_r(vs::iterator it){cerr<<endl;}
template<class T,class... Args>void e_r_r(vs::iterator it,T a,Args... args){cerr<<it->substr((*it)[0]==' ',it->length())<<" = "<<a<<", ";e_r_r(++it,args...);}
#define out(args...){vs a_r_g_s=s_p_l_i_t(#args,',');e_r_r(a_r_g_s.begin(),args);}
#else
#define out(args...)
#endif

ll gened[] = {
1,
1469980682, 3043866212, 4668805409, 6304910373, 7993963848,
9642632564, 11294354943, 13027785740, 14738125641, 16528261375,
18210846386, 19866094009, 21598491427, 23305273534, 25096174497,
26851772374, 28602397046, 30427698867, 32270214646, 34179892637,
35795799216, 37474898933, 39197471652, 40939570400, 42754518130,
44462028976, 46246138687, 48061009294, 49915842586, 51804505761,
53529119448, 55324780533, 57133698007, 59013445746, 60879847551,
62731107733, 64657845640, 66594902248, 68606219970, 70213317069,
71896995173, 73611431536, 75356722003, 77182126886, 78884623046,
80667255480, 82482422734, 84337635812, 86217961301, 87953309938,
89746820666, 91556662143, 93439998092, 95303593667, 97158013922,
99080204117, 101016865959, 103042167188, 104735939624, 106520038461,
108339020461, 110194551904, 112090962920, 113932646967, 115853066778,
117756428334, 119756595296, 121611143237, 123494368506, 125404818570,
127360339056, 129354551818, 131294634763, 133318905970, 135350966231,
137462808125, 139052375614, 140732668145, 142445346067, 144194746393,
146037422438, 147724195504, 149512054409, 151331584274, 153185209653,
155051645119, 156798952109, 158596635939, 160402984627, 162286550795,
164149606192, 166003338830, 167926774511, 169866379992, 171876516828,
173576727178, 175365124328, 177188326764, 179046824749, 180935812837,
182776411125, 184711441709, 186615413487, 188617425859, 190457184794,
192340450187, 194259404542, 196219122517, 198200809867, 200148332580,
202170968418, 204206289209, 206291552308, 207999147186, 209789717168,
211606934845, 213471105767, 215354169177, 217198961226, 219130300531,
221046311026, 223051245661, 224881948287, 226765329947, 228690056611,
230647419412, 232625258768, 234578074839, 236597532732, 238637796475,
240718182584, 242543758169, 244441961634, 246354023499, 248340289572,
250293791186, 252267865239, 254282368803, 256342539975, 258381856246,
260332956441, 262353169362, 264392085346, 266499308735, 268531551868,
270653190668, 272777094984, 274954969328, 276550885608, 278235349289,
279949996554, 281699656520, 283532815989, 285230291483, 287018460850,
288843338529, 290697914218, 292555622135, 294299027632, 296108809336,
297913802581, 299797478106, 301659455418, 303513296426, 305438074433,
307378730113, 309375584150, 311084691351, 312874881380, 314691888318,
316556574461, 318438834135, 320283900459, 322215373230, 324132816437,
326137829796, 327967124398, 329850743236, 331776265114, 333733585567,
335710857866, 337664009017, 339683323432, 341723231862, 343789429912,
345507238667, 347300064350, 349113030840, 350984406135, 352860264736,
354707032557, 356636401290, 358564384537, 360569937186, 362394197650,
364277970856, 366198335844, 368164629325, 370136993397, 372090932249,
374111296941, 376151464705, 378224220960, 380058390875, 381957670005,
383870119640, 385856452156, 387803833108, 389785718954, 391799556548,
393861322106, 395892667666, 397847294362, 399867029816, 401906744673,
404011963610, 406045283138, 408166458655, 410293988630, 412459892513,
414170300487, 415960418167, 417777139873, 419642241648, 421523913358,
423369329089, 425300867467, 427219090689, 429224980146, 431052903006,
432936691509, 434863107905, 436819529994, 438796401986, 440750473367,
442769590824, 444808941609, 446887863691, 448715363575, 450613672574,
452525875722, 454512303700, 456465371949, 458440607830, 460454459144,
462516131473, 464552796690, 466505438580, 468525009072, 470565134403,
472670820245, 474703374234, 476824486461, 478949396296, 481137046691,
482947439062, 484844914786, 486755371546, 488739231350, 490705646259,
492663323054, 494681424791, 496736570450, 498791098622, 500733994162,
502758835083, 504792318352, 506906580542, 508935069724, 511049944011,
513166144224, 515389888649, 517288857480, 519289749375, 521307331285,
523399099799, 525438600325, 527525826917, 529645152611, 531830142929,
533911179954, 535991669365, 538110881857, 540290279141, 542445766977,
544627454221, 546846436546, 549136811513, 550918245602, 552577704794,
554309590979, 556033975615, 557829972985, 559563840963, 561330089610,
563154351847, 564994400089, 566933008719, 568618071111, 570404156594,
572223399213, 574077826799, 575973613140, 577815644715, 579740475323,
581642857022, 583642878785, 585412682639, 587185448355, 589004843649,
590849466513, 592776838356, 594584205659, 596480632590, 598390213848,
600373164701, 602276789225, 604131558058, 606055535834, 607996922408,
610014086322, 611936152792, 613942070950, 615953831172, 618055837482,
619832855781, 621609731741, 623425191203, 625271673298, 627194398350,
629008378139, 630905954546, 632817224875, 634802011556, 636703471280,
638556986940, 640483343578, 642421663991, 644434745133, 646369655949,
648375252409, 650387040722, 652490864964, 654340820929, 656224576189,
658146134026, 660104803135, 662085614135, 664034735323, 666056469887,
668092915894, 670191528127, 672123851671, 674129434810, 676141175724,
678244658509, 680275412064, 682374196306, 684492287082, 686688081834,
688498052941, 690271265396, 692090271191, 693934884550, 695861454783,
697669335632, 699566093251, 701476114233, 703459014946, 705362572698,
707217077730, 709141525004, 711083438845, 713099812794, 715022516642,
717028460170, 719040292107, 721142705765, 723002026267, 724885629032,
726803561592, 728761045579, 730747568720, 732693287993, 734717019390,
736749758874, 738856174302, 740777465961, 742783307821, 744795165468,
746896572050, 748933922639, 751024347007, 753141880458, 755336643853,
757242843585, 759125818601, 761035892927, 762989904072, 764984543942,
766926219065, 768950249380, 770981663499, 773102984407, 775002837011,
777003979124, 779020939116, 781115568136, 783154062627, 785241482314,
787360097555, 789546215920, 791553252818, 793534166666, 795550462220,
797612465334, 799687356918, 801743227036, 803862443625, 806016345293,
808158770188, 810211805541, 812331967883, 814480115181, 816665287720,
818815284449, 821033071135, 823291446296, 825336664996, 827085965369,
828930392300, 830720144582, 832614810573, 834456466214, 836329001352,
838244378913, 840200563740, 842172566043, 844015128001, 845924301194,
847830932678, 849827622308, 851765990426, 853747688137, 855773169362,
857835953013, 859806361441, 861660536604, 863582897550, 865519592653,
867544389704, 869447143816, 871446393635, 873463619464, 875554302728,
877522802074, 879503038972, 881526923742, 883590032966, 885658701687,
887720236940, 889838183538, 891996345815, 894045653774, 895894981736,
897822674154, 899754550956, 901760199509, 903674751149, 905672137367,
907685190026, 909772129132, 911755883600, 913735370979, 915747908991,
917808707287, 919885714570, 921941106979, 924059753965, 926210825894,
928324426778, 930270736126, 932294263359, 934327743215, 936441420445,
938472256198, 940594928117, 942709938290, 944923194197, 946936098999,
949049124016, 951165540848, 953382717840, 955503787985, 957723191654,
959946162612, 962209863199, 964024768740, 965922590824, 967834326487,
969819285239, 971779514592, 973744657012, 975763287764, 977816739031,
979866439343, 981812882713, 983836311144, 985870025629, 987983393422,
990014429317, 992137825273, 994252783159, 996463258969, 998367757387,
1000369833422
};

ll solve() {
  ll n = read<ll>();
  int m = sizeof(gened) / sizeof(ll);

  int idx = lower_bound(gened, gened+m, n) - gened;

  if (gened[idx] == n) {
    return idx * 1e8 + 1;
  }

  idx--;
  ll ans = idx * 1e8 + 1;
  ll t = gened[idx];

  while (t < n) {
    t += __builtin_popcountll(t);
    ans++;
  }
  if (t > n) return -1;
  return ans;
}

void Main() {
  cout << solve() << endl;
}
int main() { cin.tie(nullptr); ios::sync_with_stdio(false); Main(); return 0; }
0