結果

問題 No.2446 完全列
コンテスト
ユーザー 👑 p-adic
提出日時 2023-05-15 08:31:20
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,504 bytes
コンパイル時間 905 ms
コンパイル使用メモリ 69,712 KB
最終ジャッジ日時 2025-02-13 00:38:17
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

// ユークリッドの互除法による解法
#include <iostream>
#include <stdio.h>
#include <stdint.h>
#include <cassert>
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 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 QUIT return 0 
#define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT 

inline CEXPR( int , bound_size , 15 );

int Rank( ll ( &A )[bound_size][bound_size] , const int& L , const int& M )
{
  if( L > M ){
    ll B[bound_size][bound_size];
    FOR( j , 0 , M ){
      ll ( &Bj )[bound_size] = B[j];
      FOR( i , 0 , L ){
	Bj[i] = A[i][j];
      }
    }
    return Rank( B , M , L );
  }
  int i_min = 0;
  int i_gcd;
  int i_curr;
  int j_curr = 0;
  ll a[2][2];
  ll ( &a_0 )[2] = a[0];
  ll ( &a_1 )[2] = a[1];
  ll b[2];
  ll& b_0 = b[0];
  ll& b_1 = b[1];
  int i[2];
  int i_0;
  int i_1;
  ll A_temp[2];
  ll& A_temp_0 = A_temp[0];
  ll& A_temp_1 = A_temp[1];
  ll q;
  while( i_min < L && j_curr < M ){
    i_gcd = i_min;
    i_curr = i_min + 1;
    b_0 = A[i_gcd][j_curr];
    while( i_curr < L ){
      b_1 = A[i_curr][j_curr];
      i[0] = i_gcd;
      i[1] = i_curr;
      i_0 = ( b_0 >= b_1 ? 0 : 1 );
      i_1 = 1 - i_0;
      for( int i = 0 ; i < 2 ; i++ ){
	ll ( &ai )[2] = a[i];
	for( int j = 0 ; j < 2 ; j++ ){
	  ai[j] = ( i == j ? 1 : 0 );
	}
      }
      while( b[i_1] != 0 ){
	ll& b_i_0 = b[i_0];
	ll& b_i_1 = b[i_1];
	ll ( &a_i_0 )[2] = a[i_0];
	ll ( &a_i_1 )[2] = a[i_1];
	q = b_i_0 / b_i_1;
	a_i_0[i_0] -= q * a_i_1[i_0];
	a_i_0[i_1] -= q * a_i_1[i_1];
	b_i_0 %= b_i_1;
	swap( i_0 , i_1 );
      }
      ll ( &A_i_0 )[bound_size] = A[i[0]];
      ll ( &A_i_1 )[bound_size] = A[i[1]];
      for( int j = j_curr ; j < M ; j++ ){
	ll& A_i_0_j = A_i_0[j];
	ll& A_i_1_j = A_i_1[j];
	A_temp_0 = a_0[0] * A_i_0_j + a_0[1] * A_i_1_j;
	A_temp_1 = a_1[0] * A_i_0_j + a_1[1] * A_i_1_j;
	A_i_0_j = A_temp_0;
	A_i_1_j = A_temp_1;
      }
      i_gcd = i[i_0];
      b_0 = A[i_gcd][j_curr];
      i_curr++;
    }
    if( b_0 != 0 ){
      swap( A[i_min] , A[i_gcd] );
      i_min++;
    }
    j_curr++;
  }
  return i_min;
}

int main()
{
  UNTIE;
  CIN( int , L );
  assert( 1 <= L );
  CIN( int , M );
  assert( 1 <= M && L * M <= bound_size );
  CIN( int , N );
  assert( 1 <= N && M * N <= bound_size );
  CEXPR( ll , bound , 6 );
  ll A[bound_size][bound_size];
  FOR( i , 0 , L ){
    ll ( &Ai )[bound_size] = A[i];
    FOR( j , 0 , M ){
      ll& Aij = Ai[j];
      cin >> Aij;
      ASSERT( Aij , - bound , bound );
    }
  }
  ll B[bound_size][bound_size];
  FOR( j , 0 , M ){
    ll ( &Bj )[bound_size] = B[j];
    FOR( k , 0 , N ){
      ll& Bjk = Bj[k];
      cin >> Bjk;
      ASSERT( Bjk , - bound , bound );
    }
  }
  ll sum = 0;
  FOR( i , 0 , L ){
    ll ( &Ai )[bound_size] = A[i];
    FOR( k , 0 , N ){
      FOR( j , 0 , M ){
	sum += Ai[j] * B[j][k];
      }
      if( sum != 0 ){
	RETURN( "No" );
      }
    }
  }
  int rankA = Rank( A , L , M );
  int rankB = Rank( B , M , N );
  RETURN( rankB == M - rankA ? "Yes" : "No" );
}
0