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

提出ソース

結果

問題	No.2218 Multiple LIS
ユーザー	👑 p-adic
提出日時	2023-06-01 09:11:28
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	220 ms / 3,000 ms
コード長	3,414 bytes
コンパイル時間	4,285 ms
コンパイル使用メモリ	226,720 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-06-08 21:27:51
合計ジャッジ時間	8,249 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 5,248 KB
testcase_01	AC	2 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	3 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	2 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	2 ms 5,376 KB
testcase_21	AC	10 ms 5,376 KB
testcase_22	AC	58 ms 5,376 KB
testcase_23	AC	95 ms 5,376 KB
testcase_24	AC	22 ms 5,376 KB
testcase_25	AC	110 ms 5,376 KB
testcase_26	AC	156 ms 5,376 KB
testcase_27	AC	156 ms 5,376 KB
testcase_28	AC	156 ms 5,376 KB
testcase_29	AC	155 ms 5,376 KB
testcase_30	AC	158 ms 5,376 KB
testcase_31	AC	73 ms 5,376 KB
testcase_32	AC	73 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	10 ms 5,376 KB
testcase_37	AC	220 ms 5,376 KB
testcase_38	AC	2 ms 5,376 KB
testcase_39	AC	3 ms 5,376 KB
testcase_40	AC	123 ms 5,376 KB
testcase_41	AC	118 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード