結果

問題 No.2218 Multiple LIS
ユーザー 👑 p-adicp-adic
提出日時 2023-06-01 09:11:28
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 224 ms / 3,000 ms
コード長 3,414 bytes
コンパイル時間 13,597 ms
コンパイル使用メモリ 282,988 KB
最終ジャッジ日時 2025-02-13 17:15:06
ジャッジサーバーID
（参考情報） 		judge1 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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>
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;
	
      }

    }

  }

}

int main()
{
  UNTIE;
  CEXPR( int , bound , 100000 );
  CIN_ASSERT( N , 1 , bound );
  constexpr PrimeEnumeration<int,bound+1,317> prime{};
  int count[bound+1] = {};
  REPEAT( N ){
    CIN_ASSERT( A , 1 , bound );
    int& count_A = count[A];
    list<pair<int,int> > factor{};
    FOR( i , 0 , prime.m_length ){
      const int& p = prime.m_val[i];
      int exponent = 0;
      while( A % p == 0 ){
	exponent++;
	A /= p;
      }
      if( exponent > 0 ){
	factor.push_back( pair<int,int>( p , exponent ) );
      }
      if( A == 1 ){
	break;
      }
    }
    if( A > 1 ){
      factor.push_back( pair<int,int>( A , 1 ) );
    }
    list<int> divisor{};
    divisor.push_back( 1 );
    FOR_ITR( factor , itr_factor , end_factor ){
      list<int> temp{};
      int p = 1;
      FOREQ( e , 1 , itr_factor->second ){
	p *= itr_factor->first;
	FOR_ITR( divisor , itr_divisor , end_divisor ){
	  temp.push_back( *itr_divisor * p );
	}
      }
      while( ! temp.empty() ){
	divisor.push_back( temp.front() );
	temp.pop_front();
      }
    }
    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 );
}
0