fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. inline int my_getchar_unlocked(){
  5.   static char buf[1048576];
  6.   static int s = 1048576;
  7.   static int e = 1048576;
  8.   if(s == e && e == 1048576){
  9.     e = fread_unlocked(buf, 1, 1048576, stdin);
  10.     s = 0;
  11.   }
  12.   if(s == e){
  13.     return EOF;
  14.   }
  15.   return buf[s++];
  16. }
  17. inline void rd(int &x){
  18.   int k;
  19.   int m=0;
  20.   x=0;
  21.   for(;;){
  22.     k = my_getchar_unlocked();
  23.     if(k=='-'){
  24.       m=1;
  25.       break;
  26.     }
  27.     if('0'<=k&&k<='9'){
  28.       x=k-'0';
  29.       break;
  30.     }
  31.   }
  32.   for(;;){
  33.     k = my_getchar_unlocked();
  34.     if(k<'0'||k>'9'){
  35.       break;
  36.     }
  37.     x=x*10+k-'0';
  38.   }
  39.   if(m){
  40.     x=-x;
  41.   }
  42. }
  43. inline int rd_int(void){
  44.   int x;
  45.   rd(x);
  46.   return x;
  47. }
  48. struct MY_WRITER{
  49.   char buf[1048576];
  50.   int s;
  51.   int e;
  52.   MY_WRITER(){
  53.     s = 0;
  54.     e = 1048576;
  55.   }
  56.   ~MY_WRITER(){
  57.     if(s){
  58.       fwrite_unlocked(buf, 1, s, stdout);
  59.     }
  60.   }
  61. }
  62. ;
  63. MY_WRITER MY_WRITER_VAR;
  64. void my_putchar_unlocked(int a){
  65.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  66.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  67.     MY_WRITER_VAR.s = 0;
  68.   }
  69.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  70. }
  71. inline void wt_L(char a){
  72.   my_putchar_unlocked(a);
  73. }
  74. inline void wt_L(int x){
  75.   int s=0;
  76.   int m=0;
  77.   char f[10];
  78.   if(x<0){
  79.     m=1;
  80.     x=-x;
  81.   }
  82.   while(x){
  83.     f[s++]=x%10;
  84.     x/=10;
  85.   }
  86.   if(!s){
  87.     f[s++]=0;
  88.   }
  89.   if(m){
  90.     my_putchar_unlocked('-');
  91.   }
  92.   while(s--){
  93.     my_putchar_unlocked(f[s]+'0');
  94.   }
  95. }
  96. inline void wt_L(const char c[]){
  97.   int i=0;
  98.   for(i=0;c[i]!='\0';i++){
  99.     my_putchar_unlocked(c[i]);
  100.   }
  101. }
  102. template<class S, class T> inline S chmax(S &a, T b){
  103.   if(a<b){
  104.     a=b;
  105.   }
  106.   return a;
  107. }
  108. int TEST;
  109. int dp1[1000000+1];
  110. int dp2[1000000+1];
  111. int main(){
  112.   int i;
  113.   for(i=(1);i<(1000000+1);i++){
  114.     int j;
  115.     for(j=(2*i);j<(1000000+1);j+=(i)){
  116.       chmax(dp2[j], dp2[i-1] + 1);
  117.     }
  118.   }
  119.   for(i=(1);i<(1000000+1);i++){
  120.     int j;
  121.     for(j=(3*i);j<(1000000+1);j+=(i)){
  122.       chmax(dp1[j], dp2[i-1] + 1);
  123.     }
  124.   }
  125.   int WYIGIcGE = rd_int();
  126.   for(TEST=(0);TEST<(WYIGIcGE);TEST++){
  127.     wt_L("Case #");
  128.     wt_L(TEST+1);
  129.     wt_L(": ");
  130.     wt_L(dp1[rd_int()]);
  131.     wt_L("\n");
  132.   }
  133.   return 0;
  134. }
  135. // cLay version 20210405-1
  136.  
  137. // --- original code ---
  138. // int TEST;
  139. // int dp1[1d6+1], dp2[1d6+1];
  140. // {
  141. //   rep(i,1,1d6+1) rep(j,2*i,1d6+1,i) dp2[j] >?= dp2[i-1] + 1;
  142. //   rep(i,1,1d6+1) rep(j,3*i,1d6+1,i) dp1[j] >?= dp2[i-1] + 1;
  143. //   REP(TEST,rd_int()) wtF("Case #{TEST+1}: {dp1[rd_int()]}\n");
  144. // }
  145.  
Time limit exceeded #stdin #stdout 5s 11820KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GdvJWr
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!