結果
問題 | No.2263 Perms |
ユーザー | 👑 p-adic |
提出日時 | 2023-09-06 18:25:35 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 120 ms / 2,000 ms |
コード長 | 15,295 bytes |
コンパイル時間 | 3,512 ms |
コンパイル使用メモリ | 237,324 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-24 12:49:01 |
合計ジャッジ時間 | 5,708 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 3 ms
6,948 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 15 ms
6,940 KB |
testcase_07 | AC | 7 ms
6,940 KB |
testcase_08 | AC | 3 ms
6,944 KB |
testcase_09 | AC | 30 ms
6,940 KB |
testcase_10 | AC | 120 ms
6,940 KB |
testcase_11 | AC | 7 ms
6,944 KB |
testcase_12 | AC | 9 ms
6,944 KB |
testcase_13 | AC | 18 ms
6,944 KB |
testcase_14 | AC | 18 ms
6,944 KB |
testcase_15 | AC | 16 ms
6,940 KB |
testcase_16 | AC | 2 ms
6,940 KB |
testcase_17 | AC | 3 ms
6,940 KB |
testcase_18 | AC | 2 ms
6,944 KB |
testcase_19 | AC | 3 ms
6,940 KB |
testcase_20 | AC | 11 ms
6,944 KB |
testcase_21 | AC | 14 ms
6,940 KB |
testcase_22 | AC | 11 ms
6,940 KB |
testcase_23 | AC | 5 ms
6,944 KB |
testcase_24 | AC | 3 ms
6,944 KB |
testcase_25 | AC | 13 ms
6,940 KB |
testcase_26 | AC | 15 ms
6,944 KB |
testcase_27 | AC | 4 ms
6,940 KB |
testcase_28 | AC | 3 ms
6,940 KB |
testcase_29 | AC | 4 ms
6,944 KB |
testcase_30 | AC | 2 ms
6,940 KB |
testcase_31 | AC | 2 ms
6,940 KB |
testcase_32 | AC | 3 ms
6,944 KB |
testcase_33 | AC | 2 ms
6,940 KB |
testcase_34 | AC | 2 ms
6,944 KB |
testcase_35 | AC | 2 ms
6,940 KB |
testcase_36 | AC | 2 ms
6,940 KB |
testcase_37 | AC | 2 ms
6,940 KB |
testcase_38 | AC | 10 ms
6,944 KB |
testcase_39 | AC | 1 ms
6,940 KB |
testcase_40 | AC | 1 ms
6,944 KB |
ソースコード
#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(ST+(e+log_2 S)√(S+T))で解く。 // 特に // - eがO(ST)の時はO(ST√(S+T))、 // - eがO(S+T)の時はO(ST) // で解く。 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] = {}; bool chosen_edge[S_max][T_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; }