結果

問題 No.262 面白くないビットすごろく
ユーザー char134217728char134217728
提出日時 2018-01-04 23:29:02
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 16,158 bytes
コンパイル時間 1,798 ms
コンパイル使用メモリ 200,656 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-02 08:40:59
合計ジャッジ時間 2,727 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 WA -
testcase_03 AC 334 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main(){
      | ^~~~

ソースコード

diff # 

#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_popcount
#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,12,3,18,10,16,18,10,12,16,18,11,10,10,12,3,3,3,10,18,12,12,12,18,3,10,10,3,10,3,10,18,18,10,4,16,3,3,3,10,10,18,3,11,12,16,12,4,18,3,3,18,3,10,10,11,10,12,4,10,3,16,3,3,10,16,3,3,3,20,10,11,4,12,12,12,12,22,3,10,3,12,3,12,3,18,3,16,3,12,12,11,10,18,12,18,12,10,4,10,3,10,12,10,3,12,18,3,12,3,10,3,10,10,12,10,10,18,18,11,8,16,10,18,3,12,12,12,12,3,3,12,10,12,12,11,12,10,3,10,3,18,10,10,10,18,10,16,4,12,12,18,18,10,18,12,12,18,4,10,12,12,3,10,3,12,12,3,4,12,18,3,4,12,18,10,3,16,12,11,12,10,12,16,12,12,10,10,10,10,18,3,12,10,3,12,10,12,10,11,4,10,10,12,12,10,10,12,12,18,10,10,12,18,10,3,18,16,3,4,10,12,12,18,10,3,3,12,16,20,10,10,10,16,10,12,10,12,3,3,3,16,12,12,8,20,12,16,10,10,18,10,3,3,10,11,18,10,12,16,12,12,3,18,12,16,18,11,10,10,12,11,18,10,10,11,12,20,10,3,12,3,10,18,3,18,18,11,10,16,3,10,3,12,18,10,10,3,12,12,8,12,12,3,12,10,3,18,3,12,10,10,18,18,18,3,10,12,3,3,4,18,10,10,10,10,18,16,3,10,10,3,12,10,10,20,12,18,3,3,8,3,18,10,18,12,3,10,4,10,18,11,3,10,10,16,3,18,12,3,18,3,12,10,12,3,10,3,10,16,16,3,12,20,10,18,10,12,10,12,10,3,10,3,3,18,4,16,12,4,10,4,12,18,18,18,10,10,12,3,16,18,10,18,8,3,10,12,10,3,18,4,10,16,10,3,10,16,18,11,10,3,18,10,10,16,3,18,10,12,18,16,10,20,3,18,3,20,12,3,3,10,4,18,10,18,18,18,12,10,18,12,3,3,12,3,3,12,12,10,12,16,3,4,3,10,10,3,10,12,12,18,3,18,12,10,10,20,18,3,12,12,3,3,3,20,12,3,10,16,12,10,8,18,10,3,18,12,12,18,10,18,10,12,3,16,3,3,3,3,3,3,10,20,10,10,18,16,10,11,18,16,12,10,10,12,12,18,3,16,3,12,10,3,16,3,18,12,10,11,10,10,10,3,12,12,10,16,3,3,10,11,10,3,12,10,10,3,3,3,10,12,3,18,10,10,12,12,10,18,18,11,12,3,3,10,18,12,12,12,10,12,12,10,4,10,10,18,3,18,18,3,3,3,10,10,10,12,12,11,18,10,12,12,8,3,18,16,10,12,12,18,12,16,10,11,12,12,3,18,3,18,12,10,10,18,10,10,18,10,18,11,3,12,12,10,10,12,12,10,3,20,12,16,8,18,18,10,10,16,16,16,10,12,10,20,18,12,12,3,4,12,10,12,10,12,3,10,10,3,10,12,10,10,18,3,18,3,3,11,3,3,3,18,1,12,12,10,18,16,10,3,3,10,10,10,12,3,10,18,4,16,16,3,3,18,12,18,3,10,10,3,3,18,16,10,3,3,3,3,18,3,3,12,18,10,3,10,10,12,10,3,12,3,3,11,3,12,12,18,10,20,16,10,12,16,4,11,12,16,10,3,16,12,3,3,3,3,12,12,10,18,18,18,3,3,3,3,10,20,4,18,12,12,18,10,4,3,12,10,18,3,4,3,10,10,4,12,10,10,3,18,18,18,18,16,10,3,10,10,12,10,3,11,12,12,3,3,10,16,18,12,8,10,12,18,10,3,12,10,10,12,12,12,3,8,4,3,10,12,12,11,10,18,3,10,10,3,12,11,3,10,10,12,10,10,3,11,3,12,3,18,10,18,16,16,4,12,3,4,10,10,12,10,3,12,12,3,10,3,10,18,3,11,3,11,12,3,10,10,12,16,12,18,12,20,10,10,4,12,3,16,3,10,18,18,18,12,3,10,10,18,10,11,18,18,12,11,4,12,12,10,12,12,3,11,12,10,10,11,12,12,10,3,18,18,12,10,4,12,4,11,3,18,16,18,3,18,3,3,10,12,10,10,18,10,18,16,3,20,3,10,18,12,10,3,10,4,10,10,3,20,12,16,12,12,12,16,4,12,12,16,3,20,10,10,18,11,12,3,10,3,16,11,18,3,16,10,1,18,18,10,10,12,4,16,1
}, B[1001]={
  1,68893379,133259591,197306960,258074468,324418508,389669250,453302119,515162190,578985391,645476721,709035141,771952301,832881649,900383199,963987661,1028222723,1088757204,1155910248,1220875775,1284702116,1346041133,1410524053,1476818584,1540649875,1602993746,1665096657,1732284025,1795765250,1858907517,1919156743,1987360582,2051945853,2115835658,2176942816,2242630471,2307996236,2371835872,2433939023,2497196162,2563704907,2627491399,2690427101,2750645325,2818519898,2882843719,2946943339,3007564291,3074312933,3139407461,3203199188,3264522977,3328962358,3395292435,3459048424,3521578793,3583121319,3650478783,3713735931,3777730593,3838120554,3905821402,3970440588,4034510276,4095667632,4160706047,4226449810,4290411643,4352673967,4415135989,4482181055,4545670392,4608870083,4668436748,4737171133,4801572369,4865539382,4926417714,4992612363,5057893263,5121436356,5183449033,5247150881,5313723220,5377316028,5440216481,5500969949,5568492181,5632338206,5696504113,5757072148,5824007955,5889141218,5952986924,6014324174,6078786983,6145058282,6208894806,6271240342,6333260524,6400419492,6463875095,6527107761,6587539692,6655646016,6720208338,6784136795,6845238370,6910815018,6976161935,7040100977,7102190960,7165318259,7231955062,7295720952,7358694684,7418691272,7486811811,7551143077,7615228787,7675834216,7742509380,7807609358,7871424176,7932901161,7997178498,8063547885,8127222624,8189878218,8251209644,8318631379,8381778987,8446030979,8506476355,8574056602,8638767689,8702765675,8763959259,8828811337,8894743589,8958634797,9020929632,9083174850,9150393342,9213914317,9277092656,9336835198,9405407769,9469864861,9533787467,9594746240,9660742244,9726070145,9789662831,9851800570,9915372614,9981924714,10045549482,10108456449,10169098058,10236570487,10300650926,10364741105,10425390153,10492306763,10557421316,10621248823,10682554663,10747029851,10813309686,10877119657,10939445945,11001349011,11068582596,11132055910,11195483040,11255900697,11323881217,11388452722,11452438107,11513521372,11578950535,11644265915,11708365349,11770521769,11833482073,11900217999,11963903050,12026937491,12086719198,12155097150,12219405591,12283476800,12344121136,12410740886,12475894828,12539630753,12601252667,12665354514,12731794448,12795387984,12858145761,12919255345,12986749501,13050062478,13114365549,13174842242,13242253034,13307060469,13371010647,13432244055,13496882554,13562999047,13626832765,13689210756,13751403434,13818611838,13882110247,13945265693,14005223998,14073642959,14138142037,14201982798,14263045752,14328927688,14394309819,14457991863,14520108370,14583545708,14650101567,14713793226,14776679029,14837144115,14904616706,14968970494,15033089464,15093718624,15160565485,15225656654,15289487734,15350806459,15415251560,15481511053,15545293280,15607704568,15669546658,15736803873,15800189045,15863819790,15924243928,15992135363,16056676645,16120700030,16181754145,16247089359,16312599665,16376646090,16438837266,16501570662,16568461613,16632092157,16695162767,16754678843,16823332257,16887689874,16951770642,17012497874,17078944986,17144134430,17207813878,17269600294,17333518422,17399998635,17463497435,17526406672,17587407377,17654915242,17718422598,17782666553,17843185929,17910437601,17975346044,18039217020,18100495812,18164973617,18231285226,18295117959,18357478158,18419600959,18486785807,18550294051,18613431782,18673589832,18741839346,18806392918,18870278000,18931379647,18997143689,19062505257,19126283926,19188407979,19251709920,19318253934,19381989184,19444873301,19505219379,19572954891,19637297295,19701397149,19762010317,19828806677,19893896207,19957710920,20019001770,20083432930,20149754864,20213536885,20276033175,20337674948,20404977232,20468289803,20532168082,20592572352,20660334653,20724863194,20788967297,20850105543,20915245421,20980911739,21044879774,21107131465,21169698334,21236682881,21300225248,21363334261,21422828941,21491636871,21556019457,21620032567,21680832809,21747125573,21812385921,21875973622,21937915840,22001607231,22068205321,22131780080,22194687963,22255543902,22323012653,22386768417,22450967881,22511518199,22578573013,22643585541,22707441594,22768786628,22833257607,22899548207,22963361467,23025721065,23087786295,23154951488,23218429044,23281546960,23341947344,23410112202,23474678601,23538593776,23599683975,23665319754,23730690126,23794569150,23856675286,23919837479,23986402474,24050216547,24113158924,24173285235,24241263354,24305590194,24369696004,24430295104,24497022589,24562091615,24625897725,24687322618,24751661549,24818029950,24881732830,24944324543,25005783543,25073148887,25136366883,25200475768,25260879221,25328550352,25393204741,25457246741,25518413112,25583344553,25649206063,25713123199,25775410388,25837744370,25904862984,25968400115,26031582093,26091242871,26159895622,26224309985,26288271187,26349184144,26415281728,26480587175,26544083951,26606234250,26669864185,26736426671,26800041168,26862920744,26923648907,26991136013,27055098070,27119229804,27179805300,27246762584,27311886056,27375722368,27437050930,27501486352,27567791719,27631611696,27693946500,27755922748,27823048733,27886565862,27949900429,28010324165,28078374982,28142917967,28206892731,28267983784,28333483794,28398825740,28462812489,28524952926,28588007872,28654687601,28718420252,28781406711,28841303813,28909563353,28973875863,29037960480,29098546675,29165216197,29230361471,29294127478,29355686311,29419858653,29486267325,29549916634,29612610128,29673849320,29741275205,29804466269,29868807870,29929257413,29996766182,30061512586,30125484160,30186712839,30251433066,30317481037,30381319215,30443657131,30505903364,30573097826,30636620190,30699777379,30759626863,30828136747,30892603392,30956494432,31017491612,31083398409,31148799832,31212428509,31274562961,31338062208,31404599888,31468279138,31531168457,31591728787,31659183910,31723393115,31787522657,31848156548,31915040868,31980146369,32043956106,32105290615,32169743143,32236013135,32299813651,32362122639,32424061074,32491297741,32554724895,32618259987,32678659124,32746617681,32811169586,32875173512,32936248111,33001572650,33067031655,33131110275,33193283667,33256144298,33322922396,33386602162,33449654668,33509300584,33577826062,33642115091,33706225288,33766913845,33833444583,33898624479,33962308729,34024031596,34088044103,34154496939,34218051672,34280857815,34341915214,34409442663,34472845234,34537123354,34597608642,34664942590,34729812601,34793713913,34854979893,34919477717,34985732821,35049584935,35111942664,35174115395,35241294157,35304795747,35367960561,35428005041,35496352522,35560858945,35624703184,35685823354,35751627052,35817017990,35880736785,35942854421,36006243600,36072771248,36136499260,36199363783,36259753479,36327396134,36391734444,36455851807,36516463896,36583277485,36648386267,36712199170,36773513479,36837941102,36904199340,36968022868,37030470724,37092218018,37159497003,37222822642,37286601169,37347010329,37414839675,37479370633,37543410965,37604539067,37669769505,37735359362,37799371240,37861571638,37924249261,37991176692,38054761098,38117857621,38177206410,38246092740,38310459799,38374505997,38435275421,38501609010,38566867939,38630498258,38692362321,38756180500,38822668229,38886233647,38949151883,39010078025,39077577813,39141186528,39205422540,39265955978,39333106518,39398075616,39461895037,39523241429,39587722356,39654017747,39717847492,39780190304,39842294128,39909478897,39972961879,40036097829,40096356216,40164562030,40229145096,40293037495,40354141228,40419823828,40485192322,40549036062,40611139901,40674388482,40740897613,40804689106,40867626106,40927842717,40995719266,41060042367,41124143927,41184763746,41251506126,41316604399,41380395271,41441725871,41506161270,41572488713,41636243027,41698778395,41760317683,41827675451,41890925723,41954930407,42015317537,42083021255,42147643180,42211707542,42272867958,42337897764,42403650491,42467609321,42529872331,42592329091,42659375926,42722870425,42786065527,42845639098,42914371140,42978771575,43042739805,43103617722,43169805701,43235089413,43298631056,43360652515,43424347779,43490920332,43554513743,43617413742,43678169019,43745685631,43809538406,43873703202,43934271584,44001195902,44066341558,44130186493,44191522756,44255985879,44322252327,44386091580,44448438294,44510456898,44577613935,44641064877,44704310383,44764739935,44832845909,44897408138,44961334013,45022438678,45088009286,45153357446,45217298720,45279387491,45342515715,45409153767,45472919375,45535890141,45595878899,45664013261,45728342282,45792429177,45853030815,45919702697,45984809212,46048622712,46110104641,46174373331,46240744908,46304418396,46367077277,46428406961,46495824844,46558968311,46623232999,46683678583,46751249936,46815968071,46879963589,46941159443,47006006422,47071939787,47135829476,47198127646,47260374685,47327591771,47391109403,47454288998,47514035395,47582607707,47647066121,47710982590,47771946576,47837933912,47903269259,47966863979,48029000508,48092570066,48159119540,48222749468,48285651889,48346288910,48413764978,48477850118,48541944204,48602590161,48669504333,48734619526,48798447310,48859755486,48924226799,48990506673,49054315436,49116641166,49178549520,49245780316,49309250648,49372685083,49433101545,49501074837,49565651574,49629637630,49690720007,49756145653,49821454162,49885563975,49947723014,50010678449,50077416453,50141095714,50204135701,50263904959,50332297067,50396605398,50460671873,50521324205,50587937295,50653093901,50716826643,50778452573,50842551988,50908991353,50972584557,51035341223,51096442948,51163947926,51227264536,51291567345,51352042255,51419446287,51484260423,51548209049,51609444862,51674072106,51740195985,51804032152,51866409825,51928603897,51995807591,52059305000,52122463180,52182426219,52250836431,52315340928,52379178718,52440247376,52506126628,52571503727,52635190526,52697308143,52760743873,52827298214,52890988326,52953875395,53014329756,53081819446,53146173103,53210288242,53270919001,53337761889,53402855688,53466685695,53528002935,53592449018,53658705810,53722493251,53784903732,53846740218,53914002314,53977382117,54041022868,54101443943,54169330944,54233873072,54297898442,54358957598,54424284248,54489799865,54553843841,54616036369,54678769567,54745659317,54809286904,54872360188,54931866377,55000526298,55064891775,55128970103,55189699488,55256142181,55321328289,55385008672,55446801618,55510714703,55577195308,55640687215,55703606493,55764599433,55832111714,55895625213,55959863546,56020387732,56087631743,56152545037,56216413104,56277692268,56342174297,56408483870,56472317907,56534673618,56596794546,56663984253,56727489491,56790628821,56850789837,56919032554,56983592973,57047479441,57108581818,57174338615,57239699965,57303483269,57365607116,57428908789,57495447402,57559183944,57622073896,57682412823,57750152849,57814497826,57878596587,57939210512,58006005651,58071089998,58134905744,58196198117,58260632661,58326954943,58390731969,58453233002,58514863853,58582175579,58645486184,58709366785,58769772765,58837528794,58902065065,58966167141,59027305425,59092440923,59158110402,59222079719,59284328911,59346889186,59413881317,59477418355,59540534603,59600031723,59668834394,59733219497,59797230985,59858036246,59924320538,59989582679,60053167044,60115115005,60178808973,60245403039,60308978742,60371886998,60432737366,60500200679,60563970381,60628167266,60688718408,60755768263,60820779296,60884640355,60945986505,61010457302,61076746731,61140556564,61202919298,61264978256,61332148007,61395625382,61458736376,61519150491,61587310398,61651877508,61715793691,61776882238,61842517188,61907884928,61971769089,62033870750,62097028360,62163603900,62227413989,62290359254,62350474204,62418460849,62482790260,62546896012,62607495850,62674217578,62739286200,62803095392,62864524726,62928861841,62995227665,63058927566,63121525064,63182977020,63250339937,63313559884,63377675122,63438082151,63505749371,63570402639,63634443749,63695613040,63760540744,63826406161,63890318293,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;
}
0