#876401 (C++17) No.2218 Multiple LIS

• 問題: No.2218 Multiple LIS
• ユーザー: 👑 p-adic
• 提出日時: 2023-06-01 09:55:50
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 225 ms / 3,000 ms
• コード長: 3,952 bytes
• コンパイル時間: 3,384 ms
• コンパイル使用メモリ: 222,204 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-08 21:29:05
• 合計ジャッジ時間: 6,532 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	3 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	3 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	3 ms; 5,376 KB
testcase_14	AC	3 ms; 5,376 KB
testcase_15	AC	3 ms; 5,376 KB
testcase_16	AC	3 ms; 5,376 KB
testcase_17	AC	3 ms; 5,376 KB
testcase_18	AC	2 ms; 5,376 KB
testcase_19	AC	2 ms; 5,376 KB
testcase_20	AC	3 ms; 5,376 KB
testcase_21	AC	8 ms; 5,376 KB
testcase_22	AC	43 ms; 5,376 KB
testcase_23	AC	73 ms; 5,376 KB
testcase_24	AC	17 ms; 5,376 KB
testcase_25	AC	81 ms; 5,376 KB
testcase_26	AC	113 ms; 5,376 KB
testcase_27	AC	113 ms; 5,376 KB
testcase_28	AC	112 ms; 5,376 KB
testcase_29	AC	115 ms; 5,376 KB
testcase_30	AC	114 ms; 5,376 KB
testcase_31	AC	72 ms; 5,376 KB
testcase_32	AC	72 ms; 5,376 KB
testcase_33	AC	74 ms; 5,376 KB
testcase_34	AC	74 ms; 5,376 KB
testcase_35	AC	74 ms; 5,376 KB
testcase_36	AC	11 ms; 5,376 KB
testcase_37	AC	225 ms; 5,376 KB
testcase_38	AC	2 ms; 5,376 KB
testcase_39	AC	2 ms; 5,376 KB
testcase_40	AC	122 ms; 5,376 KB
testcase_41	AC	122 ms; 5,376 KB

ソースコード

#ifdef DEBUG
  #define _GLIBCXX_DEBUG
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
#define CEXPR( LL , BOUND , VALUE ) constexpr const LL BOUND = VALUE
#define CIN( LL , A ) LL A; cin >> A
#define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ )
#define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- )
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )
#define QUIT return 0
#define COUT( ANSWER ) cout << ( ANSWER ) << "\n"
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT

template <typename INT , INT val_limit , int length_max = val_limit>
class PrimeEnumeration
{

public:
  INT m_val[length_max];
  int m_length;
  inline constexpr PrimeEnumeration();

};

template <typename INT , INT val_limit , int length_max>
inline constexpr PrimeEnumeration<INT,val_limit,length_max>::PrimeEnumeration() : m_val() , m_length( 0 )
{

  bool is_comp[val_limit] = {};

  for( INT i = 2 ; i < val_limit ; i++ ){

    if( is_comp[i] == false ){

      INT j = i;

      while( ( j += i ) < val_limit ){

	is_comp[j] = true;

      }

      m_val[m_length++] = i;

      if( m_length >= length_max ){

	break;
	
      }

    }

  }

}

// n < val_limitの2乗 の時のみサポート。
template <typename INT , INT val_limit , int length_max> list<int> EnumerateDivisor( const PrimeEnumeration<INT,val_limit,length_max>& prime , INT n ) noexcept
{

  list<pair<INT,int> > factor{};

  for( int i = 0 ; i < prime.m_length ; i++ ){

    const INT& pi = prime.m_val[i];
    int ei = 0;

    while( n % pi == 0 ){

      n /= pi;
      ei++;

    }

    if( ei > 0 ){

      factor.push_back( pair<INT,int>( pi , ei ) );

    }
    
    if( n == 1 ){

      break;

    }

  }

  if( n > 1 ){

    factor.push_back( pair<INT,int>( n , 1 ) );

  }
  
  list<INT> divisor{};
  divisor.push_back( 1 );
  auto begin = divisor.begin() , end = divisor.end();
  
  while( ! factor.empty() ){

    pair<INT,int>& factor_curr = factor.front();
    INT& pi = factor_curr.first;
    int& ei = factor_curr.second;
    list<int> temp{};
    INT power = 1;
    
    for( int e = 1 ; e <= ei ; e++ ){

      power *= pi;

      for( auto itr = begin ; itr != end ; itr++ ){

	temp.push_back( *itr * power );

      }
      
    }
    
    while( ! temp.empty() ){

      divisor.push_back( temp.front() );
      temp.pop_front();

    }

    factor.pop_front();

  }

  return divisor;

}

int main()
{
  UNTIE;
  CEXPR( int , bound , 100000 );
  CIN_ASSERT( N , 1 , bound );
  CEXPR( int , sqrt_bound , 317 );
  constexpr PrimeEnumeration<int,sqrt_bound> prime{};
  int count[bound+1] = {};
  REPEAT( N ){
    CIN_ASSERT( A , 1 , bound );
    int& count_A = count[A];
    list<int> divisor = EnumerateDivisor( prime , A );
    int count_curr = 0;
    while( ! divisor.empty() ){
      int& count_d = count[divisor.front()];
      count_d < count_curr ? count_curr : count_curr = count_d + 1;
      divisor.pop_front();
    }
    count_A < count_curr ? count_A = count_curr : count_A;
  }
  int answer = 0;
  FOREQ( i , 1 , bound ){
    int& count_i = count[i];
    answer < count_i ? answer = count_i : answer;
  }
  RETURN( answer );
}