結果

問題 No.2178 Payable Magic Items
ユーザー 👑 p-adicp-adic
提出日時 2023-05-31 11:11:46
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 121 ms / 4,000 ms
コード長 5,326 bytes
コンパイル時間 3,174 ms
コンパイル使用メモリ 220,060 KB
実行使用メモリ 5,456 KB
最終ジャッジ日時 2023-08-28 01:26:31
合計ジャッジ時間 5,698 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 94 ms
5,456 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 6 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 6 ms
4,376 KB
testcase_09 AC 4 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 76 ms
4,892 KB
testcase_12 AC 120 ms
5,276 KB
testcase_13 AC 121 ms
5,056 KB
testcase_14 AC 119 ms
5,260 KB
testcase_15 AC 119 ms
5,256 KB
testcase_16 AC 119 ms
5,096 KB
testcase_17 AC 104 ms
4,400 KB
testcase_18 AC 3 ms
4,384 KB
testcase_19 AC 24 ms
4,384 KB
testcase_20 AC 3 ms
4,380 KB
testcase_21 AC 3 ms
4,380 KB
testcase_22 AC 3 ms
4,380 KB
testcase_23 AC 2 ms
4,380 KB
testcase_24 AC 114 ms
4,744 KB
testcase_25 AC 101 ms
4,376 KB
testcase_26 AC 26 ms
4,396 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

// Resetはm_foundも初期化
// Shiftはm_foundは非初期化
#define DECLARATION_OF_FIRST_SEARCH( BREADTH )				\
  template <int V_max,list<int> E(const int&)>				\
  class BREADTH ## FirstSearch						\
  {									\
									\
  private:								\
    int m_V;								\
    int m_init;								\
    list<int> m_next;							\
    bool m_found[V_max];						\
									\
  public:								\
    inline BREADTH ## FirstSearch( const int& V );			\
    inline BREADTH ## FirstSearch( const int& V , const int& init );	\
									\
    inline void Reset( const int& init );				\
    inline void Shift( const int& init );				\
									\
									\
    bool& Found( const int& i );					\
    int Next();								\
									\
  };									\

#define DEFINITION_OF_FIRST_SEARCH( BREADTH , PUSH )			\
  template <int V_max,list<int> E(const int&)> inline BREADTH ## FirstSearch<V_max,E>::BREADTH ## FirstSearch( const int& V ) : m_V( V ) , m_init() , m_next() , m_found() {} \
  template <int V_max,list<int> E(const int&)> inline BREADTH ## FirstSearch<V_max,E>::BREADTH ## FirstSearch( const int& V , const int& init ) : m_V( V ) , m_init( init ) , m_next() , m_found() { m_next.push_back( m_init ); m_found[m_init] = true; } \
									\
  template <int V_max,list<int> E(const int&)> inline void BREADTH ## FirstSearch<V_max,E>::Reset( const int& init ) { m_init = init; m_next.clear(); m_next.push_back( m_init ); for( int i = 0 ; i < m_V ; i++ ){ m_found[i] = i == m_init; } } \
  template <int V_max,list<int> E(const int&)> inline void BREADTH ## FirstSearch<V_max,E>::Shift( const int& init ) { m_init = init; m_next.clear(); if( ! m_found[m_init] ){ m_next.push_back( m_init ); m_found[m_init] = true;} } \
									\
  template <int V_max,list<int> E(const int&)> inline bool& BREADTH ## FirstSearch<V_max,E>::Found( const int& i ) { return m_found[i]; } \
									\
  template <int V_max,list<int> E(const int&)>				\
  int BREADTH ## FirstSearch<V_max,E>::Next()				\
  {									\
									\
    if( m_next.empty() ){						\
									\
      return -1;							\
									\
    }									\
									\
    const int i_curr = m_next.front();					\
    m_next.pop_front();							\
    list<int> edge = E( i_curr );					\
									\
    for( auto itr = edge.begin() , end = edge.end() ; itr != end ; itr++ ){ \
									\
      bool& found_i = m_found[*itr];					\
									\
      if( ! found_i ){							\
									\
	m_next.PUSH( *itr );						\
	found_i = true;							\
									\
      }									\
									\
    }									\
									\
    return i_curr;							\
									\
  }									\


DECLARATION_OF_FIRST_SEARCH( Breadth );
DEFINITION_OF_FIRST_SEARCH( Breadth , push_back );


inline CEXPR( int , bound_K , 8 );
class power_constexpr
{
public:
  int m_val[bound_K+1];
  constexpr power_constexpr() : m_val{ 1 } { FOREQ( i , 1 , bound_K ){ m_val[i] = m_val[i-1] * 5; } }
};

int K = 0;
constexpr power_constexpr power{};

list<int> E( const int& e )
{

  list<int> answer{};
  FOR( i , 0 , K ){
    const int& power_i = power.m_val[i];
    if( ( e / power_i ) % 5 > 0 ){
      answer.push_back( e - power_i );
    }
  }
  return answer;
}

int main()
{
  UNTIE;
  CEXPR( int , bound_N , 200000 );
  CIN_ASSERT( N , 1 , bound_N );
  CIN_ASSERT( K_prep , 1 , bound_K );
  K = K_prep;
  assert( N <= power.m_val[K] );
  int S[bound_N];
  CEXPR( int , bound_Si , 100000000 );
  FOR( i , 0 , N ){
    CIN_ASSERT( Si , 0 , bound_Si );
    int Si_copy = 0;
    REPEAT( K ){
      ( Si_copy *= 5 ) += Si % 10;
      Si /= 10;
    }
    S[i] = Si_copy;
  }
  bool b[power.m_val[bound_K]] = {};
  FOR( i , 0 , N ){
    b[S[i]] = true;
  }
  int answer = 0;
  BreadthFirstSearch<power.m_val[bound_K],E> bfs{ power.m_val[bound_K] };
  FOR( i , 0 , N ){
    int& Si = S[i];
    bool& found_Si = bfs.Found( Si );
    if( ! found_Si ){
      bfs.Shift( Si );
      int e = bfs.Next();
      while( ( e = bfs.Next() ) != -1 ){
	b[e] ? ++answer : answer;
      }
      found_Si = false;
    }
  }
  RETURN( answer );
}
0