結果

問題 No.262 面白くないビットすごろく
ユーザー anta
提出日時 2015-07-31 23:22:33
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 439 ms / 2,000 ms
コード長 9,375 bytes
コンパイル時間 651 ms
コンパイル使用メモリ 81,472 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-17 23:24:30
合計ジャッジ時間 1,856 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#ifdef _MSC_VER
#include <intrin.h>
#endif
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
const ll MaxN = (ll)1e12;
const int Width = 40;
const int Interval = (int)1e8;
#ifdef _MSC_VER
inline int popcnt(ll x) {
    return (int)__popcnt64(x);
}
#else
inline int popcnt(ll x) {
    return __builtin_popcountll(x);
}
#endif
void precomp() {
    ostream &o = cout;
    o << "ll ume[] = {\n\t";
    ll n = 1;
    int iter = -1, num = 0;
    while(n < MaxN) {
        if(++ iter == Interval) {
            o << n << ", ";
            iter = 0;
            if(++ num % 4 == 0)
                o << "\n\t";
        }
        n += popcnt(n);
    }
    o << "};" << endl;
}
extern ll ume[516];
int main() {
//  precomp();
    const int umesize = sizeof(ume) / sizeof(*ume);
    ll N;
    while(cin >> N) {
        int skip = (int)(upper_bound(ume, ume + umesize, N) - 1 - ume);
        ll n = ume[skip], ans = 1 + (ll)skip * Interval;
        while(n < N) {
            n += popcnt(n);
            ++ ans;
        }
        if(n == N)
            cout << ans << endl;
        else
            puts("-1");
    }
    return 0;
}
ll ume[] = {
    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,
};
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0