結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 93 ms
5,296 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 5 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 5 ms
4,376 KB
testcase_09 AC 4 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 77 ms
4,876 KB
testcase_12 AC 120 ms
5,156 KB
testcase_13 AC 121 ms
5,036 KB
testcase_14 AC 120 ms
5,324 KB
testcase_15 AC 120 ms
5,296 KB
testcase_16 AC 121 ms
5,304 KB
testcase_17 AC 104 ms
4,464 KB
testcase_18 AC 3 ms
4,380 KB
testcase_19 AC 24 ms
4,376 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 AC 3 ms
4,380 KB
testcase_22 AC 3 ms
4,376 KB
testcase_23 AC 2 ms
4,384 KB
testcase_24 AC 114 ms
4,948 KB
testcase_25 AC 101 ms
4,376 KB
testcase_26 AC 26 ms
4,496 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 <int V_max,list<int> E(const int&)>
class BreadthFirstSearch
{

private:
  int m_V;
  int m_init;
  list<int> m_next;
  bool m_found[V_max];

public:
  inline BreadthFirstSearch( const int& V );
  inline BreadthFirstSearch( const int& V , const int& init );

  // m_foundも初期化
  inline void Reset( const int& init );
  // m_foundは非初期化
  inline void Shift( const int& init );

  bool& Found( const int& i );
  int Next();

};

template <int V_max,list<int> E(const int&)> inline BreadthFirstSearch<V_max,E>::BreadthFirstSearch( const int& V ) : m_V( V ) , m_init() , m_next() , m_found() {}
template <int V_max,list<int> E(const int&)> inline BreadthFirstSearch<V_max,E>::BreadthFirstSearch( 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 BreadthFirstSearch<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 BreadthFirstSearch<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& BreadthFirstSearch<V_max,E>::Found( const int& i ) { return m_found[i]; }

template <int V_max,list<int> E(const int&)>
int BreadthFirstSearch<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_back( *itr );
      found_i = true;

    }

  }
  
  return i_curr;

}

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