結果
| 問題 | No.2218 Multiple LIS |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2023-06-01 09:45:13 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 3,886 bytes |
| コンパイル時間 | 3,992 ms |
| コンパイル使用メモリ | 226,336 KB |
| 実行使用メモリ | 816,256 KB |
| 最終ジャッジ日時 | 2024-06-08 21:28:46 |
| 合計ジャッジ時間 | 10,180 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | MLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
ソースコード
#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;
}
}
}
}
// 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();
}
}
return divisor;
}
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<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 );
}