結果

問題 No.2218 Multiple LIS
ユーザー 👑 p-adicp-adic
提出日時 2023-06-01 09:55:50
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 223 ms / 3,000 ms
コード長 3,952 bytes
コンパイル時間 4,288 ms
コンパイル使用メモリ 219,140 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-28 01:54:03
合計ジャッジ時間 6,750 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 3 ms
4,376 KB
testcase_21 AC 9 ms
4,376 KB
testcase_22 AC 42 ms
4,376 KB
testcase_23 AC 72 ms
4,376 KB
testcase_24 AC 16 ms
4,376 KB
testcase_25 AC 81 ms
4,380 KB
testcase_26 AC 114 ms
4,380 KB
testcase_27 AC 114 ms
4,380 KB
testcase_28 AC 114 ms
4,380 KB
testcase_29 AC 114 ms
4,380 KB
testcase_30 AC 114 ms
4,380 KB
testcase_31 AC 74 ms
4,376 KB
testcase_32 AC 74 ms
4,376 KB
testcase_33 AC 74 ms
4,376 KB
testcase_34 AC 74 ms
4,380 KB
testcase_35 AC 73 ms
4,376 KB
testcase_36 AC 11 ms
4,380 KB
testcase_37 AC 223 ms
4,380 KB
testcase_38 AC 2 ms
4,376 KB
testcase_39 AC 2 ms
4,376 KB
testcase_40 AC 121 ms
4,380 KB
testcase_41 AC 121 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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 = 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 );
}
0