結果

問題 No.262 面白くないビットすごろく
ユーザー keikei
提出日時 2018-09-30 18:32:33
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 474 ms / 2,000 ms
コード長 8,625 bytes
コンパイル時間 1,618 ms
コンパイル使用メモリ 164,400 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-20 13:45:18
合計ジャッジ時間 3,020 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:https://yukicoder.me/problems/no/262>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

ll table[]={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};
void make_table(){
    ll N = 1,cnt = 0;
    cout << "ll table[]={1,";
    while(N <= 1000000000000){
        cnt++;
        N+=__builtin_popcountl(N);
        if(cnt%100000000==0){
            cerr << "Now: " << N << endl;
            cout << N << ",";
        }
    }
    cout <<"}";
}
ll solve(){
    ll N; cin >> N;
    if(N == 1) return 1;
    ll idx = lower_bound(table,table+516,N) - table;
    ll res = (idx-1)*100000000;
    ll now = table[idx-1];
    while(now < N){
        res++;
        now+=__builtin_popcountl(now);
    }
    res++;
    if(now == N) return res;
    else return -1;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    //make_table();
    cout << solve() << endl;
    return 0;
}
0