結果

問題 No.262 面白くないビットすごろく
ユーザー parukiparuki
提出日時 2016-07-16 20:39:55
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 607 ms / 2,000 ms
コード長 9,808 bytes
コンパイル時間 1,605 ms
コンパイル使用メモリ 169,092 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-15 13:58:36
合計ジャッジ時間 3,421 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

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

inline int bitcntll(unsigned long long x) {
    x = (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555);
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
    x = (x & 0x0f0f0f0f0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f0f0f0f0f);
    x = (x & 0x00ff00ff00ff00ff) + ((x >> 8) & 0x00ff00ff00ff00ff);
    x = (x & 0x0000ffff0000ffff) + ((x >> 16) & 0x0000ffff0000ffff);
    x = (x & 0x00000000ffffffff) + ((x >> 32) & 0x00000000ffffffff);
    return (int)x;
}

int main(){
    ll N;
    while(cin >> N){
        ll ans = (ll)(lower_bound(all(VAL), N) - VAL.begin());
        if(VAL[ans] > N)ans--;

        ll n = VAL[ans];
        ans = ans * 100000000 + 1;
        while(n < N){
            n += bitcntll(n);
            ans++;
        }
        if(n != N){
            puts("-1");
        } else{
            cout << ans << endl;
        }
    }
}
0