#911317 (C++17) No.2263 Perms

提出ソース

結果

問題	No.2263 Perms
ユーザー	👑 p-adic
提出日時	2023-09-06 21:24:37
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	112 ms / 2,000 ms
コード長	15,370 bytes
コンパイル時間	3,294 ms
コンパイル使用メモリ	238,400 KB
実行使用メモリ	4,384 KB
最終ジャッジ日時	2023-09-06 21:24:44
合計ジャッジ時間	5,904 ms
ジャッジサーバーID （参考情報）	judge12 / judge14

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	1 ms 4,376 KB
testcase_04	AC	1 ms 4,376 KB
testcase_05	AC	2 ms 4,380 KB
testcase_06	AC	15 ms 4,380 KB
testcase_07	AC	7 ms 4,384 KB
testcase_08	AC	3 ms 4,380 KB
testcase_09	AC	29 ms 4,380 KB
testcase_10	AC	112 ms 4,376 KB
testcase_11	AC	6 ms 4,380 KB
testcase_12	AC	8 ms 4,376 KB
testcase_13	AC	16 ms 4,376 KB
testcase_14	AC	16 ms 4,380 KB
testcase_15	AC	14 ms 4,380 KB
testcase_16	AC	2 ms 4,380 KB
testcase_17	AC	3 ms 4,380 KB
testcase_18	AC	2 ms 4,376 KB
testcase_19	AC	3 ms 4,376 KB
testcase_20	AC	11 ms 4,376 KB
testcase_21	AC	13 ms 4,380 KB
testcase_22	AC	9 ms 4,380 KB
testcase_23	AC	5 ms 4,380 KB
testcase_24	AC	2 ms 4,380 KB
testcase_25	AC	10 ms 4,380 KB
testcase_26	AC	14 ms 4,380 KB
testcase_27	AC	4 ms 4,376 KB
testcase_28	AC	2 ms 4,380 KB
testcase_29	AC	3 ms 4,376 KB
testcase_30	AC	2 ms 4,376 KB
testcase_31	AC	2 ms 4,380 KB
testcase_32	AC	2 ms 4,376 KB
testcase_33	AC	3 ms 4,376 KB
testcase_34	AC	1 ms 4,376 KB
testcase_35	AC	2 ms 4,380 KB
testcase_36	AC	2 ms 4,376 KB
testcase_37	AC	2 ms 4,380 KB
testcase_38	AC	9 ms 4,380 KB
testcase_39	AC	1 ms 4,380 KB
testcase_40	AC	1 ms 4,380 KB

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

ソースコード

raw source code

#ifdef DEBUG
  #define _GLIBCXX_DEBUG
  #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ); signal( SIGABRT , &AlertAbort )
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE )
  #define CERR( MESSAGE ) cerr << MESSAGE << endl;
  #define COUT( ANSWER ) cout << "出力： " << ANSWER << endl
  #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック： " << ( MIN ) << ( ( MIN ) <= A ? "<=" : ">" ) << A << ( A <= ( MAX ) ? "<=" : ">" ) << ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) )
  #define AUTO_CHECK bool auto_checked = true; AutoCheck( auto_checked ); if( auto_checked ){ return 0; };
  #define START_WATCH( PROCESS_NAME ) StartWatch( PROCESS_NAME )
  #define STOP_WATCH( HOW_MANY_TIMES ) StopWatch( HOW_MANY_TIMES )
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE )
  #define CERR( MESSAGE ) 
  #define COUT( ANSWER ) cout << ANSWER << "\n"
  #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
  #define AUTO_CHECK
  #define START_WATCH( PROCESS_NAME )
  #define STOP_WATCH( HOW_MANY_TIMES )
#endif
// #define RANDOM_TEST
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#define ATT __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) ) )
#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define CIN( LL , A ) LL A; cin >> A
#define CIN_ASSERT( A , MIN , MAX ) TYPE_OF( MAX ) A; SET_ASSERT( A , MIN , MAX )
#define GETLINE( A ) string A; getline( cin , A )
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR )
#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 AUTO_ITR( ARRAY ) auto itr_ ## ARRAY = ARRAY .begin() , end_ ## ARRAY = ARRAY .end()
#define FOR_ITR( ARRAY ) for( AUTO_ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES )
#define SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS )
#define QUIT goto END_MAIN
#define TEST_CASE_NUM( BOUND ) DEXPR( int , bound_T , BOUND , min( BOUND , 100 ) ); int T = 1; if constexpr( bound_T > 1 ){ SET_ASSERT( T , 1 , bound_T ); }
#define START_MAIN REPEAT( T ){ if constexpr( bound_T > 1 ){ CERR( "testcase " << VARIABLE_FOR_REPEAT_T << ":" ); }
#define FINISH_MAIN QUIT; } END_MAIN: CERR( "" );

#ifdef DEBUG
  inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }
  void AutoCheck( bool& auto_checked );
  void StartWatch( const string& process_name = "nothing" );
  void StopWatch( const int& how_many_times = 1 );
#endif
#if defined( DEBUG ) && defined( RANDOM_TEST )
  ll GetRand( const ll& Rand_min , const ll& Rand_max );
  #define SET_ASSERT( A , MIN , MAX ) CERR( #A << " = " << ( A = GetRand( MIN , MAX ) ) )
  #define RETURN( ANSWER ) if( ( ANSWER ) == guchoku ){ CERR( ( ANSWER ) << " == " << guchoku ); goto END_MAIN; } else { CERR( ( ANSWER ) << " != " << guchoku ); QUIT; }
#else
  #define SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX )
  #define RETURN( ANSWER ) COUT( ( ANSWER ) ); QUIT
#endif

// Resetはm_foundとm_prevを初期化
// Shiftはm_foundとm_prevを非初期化
#define DECLARATION_OF_FIRST_SEARCH( BREADTH )				\
  template <int V_max>							\
  class BREADTH ## FirstSearch_Body					\
  {									\
									\
  protected:								\
    int m_V;								\
    int m_init;								\
    list<int> m_next;							\
    bool m_found[V_max];						\
    int m_prev[V_max];							\
									\
  public:								\
    inline BREADTH ## FirstSearch_Body( const int& V );			\
    inline BREADTH ## FirstSearch_Body( const int& V , const int& init ); \
									\
    inline void Reset( const int& init );				\
    inline void Shift( const int& init );				\
									\
    inline const int& size() const;					\
    inline const int& init() const;					\
    inline bool& found( const int& i );					\
    inline const int& prev( const int& i ) const;			\
									\
    int Next();								\
									\
  private:								\
    virtual list<int> e( const int& t ) = 0;				\
									\
  };									\
									\
  template <int V_max,list<int> E(const int&)>				\
  class BREADTH ## FirstSearch :					\
    public BREADTH ## FirstSearch_Body<V_max>				\
  {									\
									\
  public:								\
									\
    template<typename... Args> inline BREADTH ## FirstSearch( const Args&... args ); \
									\
  private:								\
    inline list<int> e( const int& t );					\
									\
  };									\
									\
  template <int V_max,list<int> E(const int&)> void BREADTH ## FirstConnectedComponent( const int& V , int ( &vertex )[V_max] , int& count ); \

#define DEFINITION_OF_FIRST_SEARCH( BREADTH , PUSH )			\
  template <int V_max> inline BREADTH ## FirstSearch_Body<V_max>::BREADTH ## FirstSearch_Body( const int& V ) : m_V( V ) , m_init() , m_next() , m_found() , m_prev() { assert( m_V <= V_max ); for( int i = 0 ; i < m_V ; i++ ){ m_prev[i] = -1; } } \
  template <int V_max> inline BREADTH ## FirstSearch_Body<V_max>::BREADTH ## FirstSearch_Body( const int& V , const int& init ) : BREADTH ## FirstSearch_Body( V ) { m_init = init; m_next.push_back( m_init ); m_found[m_init] = true; } \
  template <int V_max,list<int> E(const int&)> template <typename... Args> inline BREADTH ## FirstSearch<V_max,E>::BREADTH ## FirstSearch( const Args&... args ) : BREADTH ## FirstSearch_Body<V_max>( args... ) {} \
									\
  template <int V_max> inline void BREADTH ## FirstSearch_Body<V_max>::Reset( const int& init ) { m_init = init; assert( m_init < m_V ); m_next.clear(); m_next.push_back( m_init ); for( int i = 0 ; i < m_V ; i++ ){ m_found[i] = i == m_init; m_prev[i] = -1; } } \
  template <int V_max> inline void BREADTH ## FirstSearch_Body<V_max>::Shift( const int& init ) { m_init = init; assert( m_init < m_V ); m_next.clear(); if( ! m_found[m_init] ){ m_next.push_back( m_init ); m_found[m_init] = true; } } \
									\
  template <int V_max> inline const int& BREADTH ## FirstSearch_Body<V_max>::size() const { return m_V; } \
  template <int V_max> inline const int& BREADTH ## FirstSearch_Body<V_max>::init() const { return m_init; } \
  template <int V_max> inline bool& BREADTH ## FirstSearch_Body<V_max>::found( const int& i ) { assert( i < m_V ); return m_found[i]; } \
  template <int V_max> inline const int& BREADTH ## FirstSearch_Body<V_max>::prev( const int& i ) const { assert( i < m_V ); return m_prev[i]; } \
									\
  template <int V_max>							\
  int BREADTH ## FirstSearch_Body<V_max>::Next()			\
  {									\
									\
    if( m_next.empty() ){						\
									\
      return -1;							\
									\
    }									\
									\
    const int i_curr = m_next.front();					\
    m_next.pop_front();							\
    list<int> edge = e( i_curr );					\
									\
    while( ! edge.empty() ){						\
									\
      const int& i = edge.front();					\
      bool& found_i = found( i );					\
									\
      if( ! found_i ){							\
									\
	m_next.PUSH( i );						\
	m_prev[i] = i_curr;						\
	found_i = true;							\
									\
      }									\
									\
      edge.pop_front();							\
									\
    }									\
									\
    return i_curr;							\
									\
  }									\
									\
  template <int V_max,list<int> E(const int&)> inline list <int> BREADTH ## FirstSearch<V_max,E>::e( const int& t ) { return E( t ); } \
									\
  template <int V_max,list<int> E(const int&)> void BREADTH ## FirstConnectedComponentSearch( const int& V , int ( &vertex )[V_max] , int& count ) \
  {									\
									\
    BREADTH ## FirstSearch<V_max,E> bfs{ V };				\
    count = 0;								\
									\
    for( int i = 0 ; i < V ; i++ ){					\
									\
      vertex[i] = -1;							\
									\
    }									\
									\
    for( int i = 0 ; i < V ; i++ ){					\
									\
      if( vertex[i] == -1 ){						\
									\
	bfs.Shift( i );							\
	int j = bfs.Next();						\
									\
	while( j != -1 ? vertex[j] == 0 : false ){			\
									\
	  vertex[j] = count;						\
	  j = bfs.Next();						\
									\
	}								\
									\
	count++;							\
									\
      }									\
									\
    }									\
									\
    return;								\
									\
  }									\

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

// (S,T,edge)が二部グラフである場合のみサポート。
// edgeのサイズをeと置く。最大二部マッチング問題を
// 時間計算量O((S+T+e)√(S+T))
// 空間計算量O(S+T+e)
// で解く。特に
// - eがO(ST)の時は時間計算量O(ST√(S+T))
// - eがO(S+T)の時は時間計算量O((S+T)√(S+T))
// で解く。
template <int S_max , int T_max>
class HopcroftKarp
{

private:
  // BFSのテンプレート引数にEdgeを渡すために、staticメンバのみを使う。
  static int g_S;
  static int g_T;
  static set<int> g_unchosen_source;
  static list<int> g_edge[S_max];
  static int g_prev[T_max];

public:
  HopcroftKarp() = delete;

  static list<pair<int,int> > Solve( const int& S , const int& T , const list<pair<int,int> >& edge );

  // BFSのテンプレート引数に渡す。
  // (1) w=0の時は、最大二部マッチングに使わなかったSの頂点リストを返す。
  // (2) 0<w<=Sの時は、s=w-1からの有向辺の終端全体のリストを返す。
  // (3) S<w<=S+Tの時は、t=w-S-1が最大二部マッチングに使われたならば
  //     対応する有向辺の始端sのみのリスト、使われなかったならば空リストを返す。
  static list<int> Edge( const int& w );

};

template <int S_max , int T_max> int HopcroftKarp<S_max,T_max>::g_S = 0;
template <int S_max , int T_max> int HopcroftKarp<S_max,T_max>::g_T = 0;
template <int S_max , int T_max> set<int> HopcroftKarp<S_max,T_max>::g_unchosen_source{};
template <int S_max , int T_max> list<int> HopcroftKarp<S_max,T_max>::g_edge[S_max] = {};
template <int S_max , int T_max> int HopcroftKarp<S_max,T_max>::g_prev[T_max] = {};

template <int S_max , int T_max>
list<pair<int,int> > HopcroftKarp<S_max,T_max>::Solve( const int& S , const int& T ,  const list<pair<int,int> >& edge )
{

  g_S = S;
  g_T = T;
  assert( g_S <= S_max && g_T <= T_max );
  
  for( int s = 0 ; s < g_S ; s++ ){

    g_unchosen_source.insert( s );

  }

  for( int s = 0 ; s < g_S ; s++ ){

    g_edge[s].clear();

  }

  for( auto itr = edge.begin() , end = edge.end() ; itr != end ; itr++ ){

    const int& s = itr->first;
    const int& t = itr->second;
    assert( 0 <= s && s < g_S && 0 <= s && t < g_T );
    g_edge[s].push_back( 1 + g_S + t );

  }

  for( int t = 0 ; t < g_T ; t++ ){

    g_prev[t] = -1;

  }

  BreadthFirstSearch<1 + S_max + T_max , Edge> bfs{ 1 + g_S + g_T };
  bool chosen_source[S_max] = {};
  bool chosen_target[T_max] = {};
  map<int,bool> chosen_edge[S_max] = {};
  int depth[1 + S_max + T_max] = {};
  int depth_min = -1;
  int root[S_max + T_max] = {};
  list<int> new_chosen_target{ 0 };
  int v , w;
  bool found;
  
  while( ! new_chosen_target.empty() ){

    new_chosen_target.clear();
    bfs.Reset( 0 );
    v = bfs.Next();
    found = false;
    
    while( ( v = bfs.Next() ) != -1 ){

      w = bfs.prev( v );
      int& depth_v = depth[v] = depth[w] + 1;
      
      if( found ? depth_v > depth_min : false ){

	break;
      
      }

      if( w == 0 ){

	const int s = v - 1;
	assert( 0 <= s && s < g_S );
	root[s] = s;

      } else {

	root[v - 1] = root[w - 1];

      }

      if( depth_v % 2 == 0 ){

	const int t = v - 1 - g_S;
	assert( 0 <= t && t < g_T );
	bool& chosen_target_t = chosen_target[t];
      
	if( !chosen_target_t ){

	  const int& s = root[v - 1];
	  assert( 0 <= s && s < g_S );
	  bool& chosen_source_s = chosen_source[s];

	  if( !chosen_source_s ){

	    chosen_source_s = true;
	    chosen_target_t = true;
	    new_chosen_target.push_back( v );

	    if( !found ){

	      found = true;
	      depth_min = depth_v;

	    }

	  }

	}

      }

    }

    for( auto itr = new_chosen_target.begin() , end = new_chosen_target.end() ; itr != end ; itr++ ){

      int* p[2] = { &w , &v };
      int*& p0 = p[0];
      int*& p1 = p[1];
      v = *itr;

      while( ( w = bfs.prev( v ) ) != 0 ){

	const int s = *p0 - 1;
	const int t = *p1 - 1 - g_S;
	assert( 0 <= s && s < g_S && 0 <= t && t < g_T );
	
	if( chosen_edge[s][t] ^= true ){

	  g_prev[t] = s;

	}
	
	swap( w , v );
	swap( p0 , p1 );

      }

      const int s = v - 1;
      assert( 0 <= s && s < g_S && g_unchosen_source.count( s ) == 1 );
      g_unchosen_source.erase( s );

    }

  }

  list<pair<int,int> > answer{};

  for( int t = 0 ; t < g_T ; t++ ){

    const int& s = g_prev[t];
    
    if( s != -1 ){

      assert( 0 <= s && s < g_S && 0 <= t && t < g_T );
      answer.push_back( { s , t } );

    }

  }
  
  return answer;

}

template <int S_max , int T_max>
list<int> HopcroftKarp<S_max,T_max>::Edge( const int& w )
{

  list<int> answer{};
  
  if( w == 0 ){

    for( auto itr = g_unchosen_source.begin() , end = g_unchosen_source.end() ; itr != end ; itr++ ){

      answer.push_back( 1 + *itr );

    }

  } else if( w <= g_S ){

    answer = g_edge[ w - 1 ];

  } else {

    const int t = w - 1 - g_S;
    assert( t < g_T );
    const int& s = g_prev[t];

    if( s != -1 ){
      
      assert( 0 <= s && s < g_S );
      answer.push_back( 1 + s );

    }

  }

  return answer;

}

int main()
{
  UNTIE;
  AUTO_CHECK;
  TEST_CASE_NUM( 1 );
  START_MAIN;

  CEXPR( int , bound , 50 );
  CIN_ASSERT( N , 2 , bound );
  CIN_ASSERT( M , 2 , bound );
  int A[bound][bound];
  FOR( i , 0 , N ){
    int ( &Ai )[bound] = A[i];
    FOR( j , 0 , N ){
      CIN_ASSERT( Aij , 0 , M );
      Ai[j] = Aij;
    }
  }
  int answer[bound][bound];
  FOR( m , 0 , M ){
    list<pair<int,int> > edge{};
    FOR( i , 0 , N ){
      int ( &Ai )[bound] = A[i];
      FOR( j , 0 , N ){
	if( Ai[j] != 0 ){
	  edge.push_back( { i , j } );
	}
      }
    }
    edge = HopcroftKarp<bound,bound>::Solve( N , N , edge );
    if( int( edge.size() ) != N ){
      RETURN( -1 );
    }
    int ( &answer_m )[bound] = answer[m];
    FOR_ITR( edge ){
      int& i = itr->first;
      int& j = itr->second;
      assert( 0 <= i && i < N && 0 <= j && j < N );
      A[i][j]--;
      answer_m[i] = j + 1;
    }
  }
  FOR( i , 0 , N ){
    int ( &Ai )[bound] = A[i];
    FOR( j , 0 , N ){
      if( Ai[j] != 0 ){
	RETURN( -1 );
      }
    }
  }
  FOR( m , 0 , M ){
    int ( &answer_m )[bound] = answer[m];
    FOR( i , 0 , N ){
      cout << answer_m[i] << " \n"[i==N-1];
    }
  }
  
  FINISH_MAIN;
}

yukicoder

結果

テストケース

ソースコード