結果

問題 No.262 面白くないビットすごろく
ユーザー LayCurseLayCurse
提出日時 2015-06-19 03:35:10
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 276 ms / 2,000 ms
コード長 5,421 bytes
コンパイル時間 1,374 ms
コンパイル使用メモリ 144,632 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-21 09:37:31
合計ジャッジ時間 2,559 ms
ジャッジサーバーID
(参考情報)
judge12 / judge14
このコードへのチャレンジ
(要ログイン)

テストケース

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

ソースコード

diff #

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

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

template<class T> int extend(const char arr[], T res[]){int i,j,s=1,z=0;static int c[128],f=0;if(f==0)REP(i,33,127)if(i!=34&&i!=92)c[i]=f++;if(arr[0]<' ')return 0;res[0]=0;for(i=0;;i++){if(arr[i]<' ')break;if(c[arr[i]]<46)res[z]=res[z]*46+c[arr[i]];else{res[z]=res[z]*46+c[arr[i]]-46;if(s==-1)res[z]*=-1,s=1;res[++z]=0;}}return z;}

const char *buf = "Q)(0'JS0EGD'e8@CIFi@>(B0oHG39Dy#!G=5Ex#*H8BKp#3-?6=o#;;>MHR#D-6-Ac#L5,>+z$&6L'0a$.IH,Aq$7)#*8T$?I!2#t$H3&G?f%!J&+#^%+CDF#}%4A.,*q%=ME@;l%EF@O7j%MMA:Jh&(04C)U&0E89+q&9<HC%T&AJ+),o&J:@;.o'%1ON>h'.2-MMw'7:%8HZ'?K-?BV'H>/BFl(#4/NEa(,:'L5Z(5<NDEb(><6#8P(GLDD*P)#1371W)-&='Ar)4K9M*o)=%;:2R)E47'6z)MJ-AMc*(CM1Bg*1!*.#{*9@07Ga*B7BM5d*K8$H*a+&>!BHz+/#=(Ii+7D)'FP+@:2J3p+I@OADf,$C+AMP,-C36%|,7$A5<X,@7,&(],J/;5!]-$9HB8u--*/O2W-6!;?=y-?!NFKy-H,9M2s.#)HH:v.,8D?/{.5CI*:o.?6</!a.H6E16W/#=3!8W/,J$3G_/62FFEb/@$*C3W/I78:D~0%/=.A_0/)6#DT095&63b0A(')GR0I/3NKf1#=K9(k1,&>/KX15$)3<m1=,JE7T1EL*A:r1ND;N?X2)D;;'V22G4C5t2;/@!HU2D#(IMY2LF<CJ_3'M-KLT30O22Mp39O3$,b3C0MH0g3LD(D#Y4(9&-Nl40DGB1a496-(8j4B/6)2T4K09F7g5&84@N~5/585#W58G@0@n5B$K(4k5KF#+&k6&BL0#o6/I:4+|69*'(<n6BAFA3p6L03L6x7'E2)Jz71=&&Ho7;7@2IX7E=3BHv7MJE!FX8(<@EBt814:0,U8:6J,At8C=6-$p8L;7$ER9'LG$(o91,C;1W9:N9?+d9CI3B'p9M!!O(X:(1K#C[:1I$3)x:;6F%Er:DLLBMX:NCN!(U;*??$'};4D./&h;==OA3e;FGM-#[<!&O*#Q<+D=7#Q<5,K'Kf<>GF)/q<H=B:Od=$=H'&Z=.9/4Eg=7O$5'g=AF-7.h=KA>@-[>'L->'}>1F(-AW><%O0>P>F41?It?!ND6Jr?*C*4Hh?2K4$K}?;,1H!V?CC'/7l?L>:=Nw@&I?M3f@/;##Op@84=.;Q@A4F>1|@J5B'LSA$K%1<UA-A.8+fA66459vA?=&C.VAH>N&<qB#>OK*_B,NJ7<|B640)?qB@&/,'mBH4!%)mC#%GLCyC+K?/3dC4N&9(~C>&8-DpCG$;K/nD!5M-<xD+D*8%{D57O2OkD>2:NEdDG9,AGXE!I.KGWE,25G2UE5N#B.sE?6-EFPEI--<KaF%(HNBuF/*06BSF79NAAPF@,3>MTFI#/7ObG$'-5$QG-,+4<dG6*@:>cG?;<.5nGHL)EDVH$@&+;sH-9:%JVH6@-4'TH?O(?,UHI:/C7XI%&G*>^I.=+1NVI845MLfIB0&!@nIL3!IMmJ'.@<&}J08I)KsJ9EO%DRJC5>$=`JLJ:HHdK(9*'6SK2.M@LQK</5>GPKF)'#2bKO?@.'jL+6D4DyL52/FC[L?<8*!jLI6=J%TM%D2*#`M0%9E+yM:=-<)iMBK-F)RMK=$K1kN&4G1;^N/72G=SN8=>:,xNA;EE)iNJM)F2{O&-=#1PO/O<LDSO8IH5DXOB!;K!xOK2G0/X#!&IDO#u#!07.D8V#!9MB.F_#!CD@%4b#!M@'C;T##)D5L>o##2>=&3{##;H;D$r##E'?'GT##NE/%3|#$*-8/>a#$3H?-FZ#$=>4M9b#$G>IL8Z#%#9CO7}#%,OHH;p#%6FK.@u#%@B:KCU#%JLH$Ek#&&FEK-e#&1&9;*{#&;5&,0v#&F#A69v#&NH!J&n#'*#FM7a#'3084&U#'<M;N#T#'F8D/8W#'OONIEh#(+FB,0r#(5EB)2o#(?D;C:e#(I*867e#)%!C#>P#).JJ5Bl#)9)%B)Y#)C!'EHS#)M.71L~#*);&:0s#*41D=:g#*=;IOO{#*G.D:Om#+#%2;Eh#+-,:D0n#+7(#M;b#+A.+7Nf#+K;:E:P#,():A9n#,2.0>/a#,<2NLD]#,F@/$<|#-#-#:%v#--B60Kf#-8/B05u#-C%/6Dj#-N*H$Ll#.(HAM*_#.0K0BBo#.90'<Fs#.AA-36b#.J42K1T#/$G>'8h#/-4&!Je#/6-9LFg#/?*8!5n#/H=6B(l#0!EF80x#0+6B*@_#04/!9Ib#0=/*17[#0F8=$Mq#0O5O:%q#1*EJ?JY#14!E'Ny#1=C6CKS#1F0C(1[#1NL@!,Z#2)DOK0r#22BNO8k#2<%6*Bx#2DI&;7d#2N$?H6X#3)1(/9}#32N!9Gt#3<+)E?y#3E+5%Bl#3N;'6Hh#4)NB@.o#43E,2O~#4=&9&7w#4FH9.G}#5!=G82l#5,G.ID`#556)3)Y#5>%!7%Z#5FJ7L!p#5OHJ&Af#6+*/=#b#63O5IB^#6=+,O+u#6F8&EHf#7!'3I:r#7+2$J1e#742#1$T#7=B.',X#7G')G<[#8!JE=5j#8,.L.<Z#86!I))u#8?F)?GW#8J!#B#f#9$O+;,T#9.'L@@t#977&)9p#9@N:LCb#9J<M)CP#:&$-HHz#:/IF9@S#:9D>1DY#:CM0GIY#:M0JLGg#;)$GA7]#;2H'A0{#;=#L+4g#;FK7:I^#<#&+G$n#<-3.5JR#<8#A1;y#<@GL4Ic#<I5MI>S#=$.+D<V#=-,*COv#=6<7BLy#=?2-1,f#=H;J#GZ#>#H7!+o#>-70C)]#>6B7.Mk#>?B?JMQ#>I$7$Cs#?$8)ALv#?..9/._#?7=L<.c#?A1M!4P#?K'-M6c#@'0G96y#@02%<Bq#@98E('s#@BG'3CT#@L0/N>p#A'MNK&Z#A14:>>f#A;,9F.Y#AE&9;&Q#AO0N*Ew#B*@$N8m#B44$3!o#B>)3;Ai#BH2BE-`#C$-CK%d#C.4>-Cs#C8A;(5~#CC1C7@f#CL=7):c#D'D!.O_#D1!=EAR#D:9!ANs#DD*9!&S#DM>)*$Q#E)6+5>X#E3/K;7`#E==A1DP#EFGOI4}#F!:LNNQ#F,14<Mt#F69,*4U#F@49$&]#FJ:B:5]#G&GJ:Dr#G16($:y#G;*3B's#GDFG!.[#GN='G'e#H*=@+2^#H4A$O2`#H>@,3?U#HHM:;Fx#I%4=%,h#I/G%@5s#I9E=L5k#ID%'G7e#IN8K,5]#J+&M!>T#J5;'51n#J@06.;}#JK.H)!v#K'+>$1|#K/B/G=W#K8@,J+V#KA1N.5[#KJ;'8Fp#L%86%He#L.<?M)w#L7J5L0`#LA31*9l#LJMDK:h#M%K.G:Y#M/)A%-m#M859,6y#MB'6=Jp#MK:2F/^#N'(N(Il#N0O1/@f#N;!#C)a#ND<'%5q#NM<,0/x#O(K<#Bg#O20'$Cd#O<(1+I~#OE3/94s#OO%G)KV$!*J1;-]$!5#.<<k$!><L0Lp$!H+*A'b$#$#+61|$#.#O*,Y$#8&!$?w$#B&5?*Y$#L36E*r$$(I7$#[$$2G(O%x$$;F*4Gh$$E(BM#y$$N:*6Kg$%*.'IBs$%3;C34j$%=-GK3u$%G#53:Q$&#)9MBd$&,F<5;W$&64A&<V$&@*).8d$&J*5.G`$'&./G2m$'0-2/2Y$':::=1]$'DNN%'r$'O-!9OX$(*AB0'f$(49?3Hr$(>3FD%l$(H?IOAV$)$96*?R$).G9K8v$)9%JI$P$)CH+(>U$)M=E'&]$*)IAAN[$*4(3&9o$*>K;AAo$*I+.KLq$+%NN3!k$+0E67-r$+;E#!Na$+D<2G<V$+MF,7%y$,)%+$9`$,2B9K@Z$,<,0@HS$,EE+N-|$,O<$C*l$-+:A.?W$-587-1o$->M*4Op$-HE&83W$.$?0->r$..K00?p$.8DL<+h$.C%)@>i$.M1:'8~$/*%+HGh$/30<%K}$/=#BF3p$/FGLE?Q$0#!FJ5z$0,K*E$i$07#>.1s";
ull arr[530];

#define SSE4_M32U_popcount(c,a) asm volatile("popcnt %1, %0;" : "=r"(c) : "r"(a))
#define SSE4_M64U_popcount(c,a) {unsigned U_S_1=a>>32,U_S_2=a; SSE4_M32U_popcount(U_S_1,U_S_1); SSE4_M32U_popcount(U_S_2,U_S_2); c=U_S_1+U_S_2;}

int main(){
  int j, k;
  ll i, x, N;

  extend(buf, arr);
  
  reader(&N);
  for(i=0;;i++) if(arr[i+1] > N) break;
  x = arr[i];
  i *= 100000001;
  i++;
  while(x < N){
    i++;
    SSE4_M64U_popcount(j,x);
    x += j;
  }
  if(x!=N) i = -1;
  writerLn(i);
  return 0;
}
0