#911055 (C++17) No.2496 LCM between Permutations

提出ソース

結果

問題	No.2496 LCM between Permutations
ユーザー	👑 p-adic
提出日時	2023-09-05 15:14:41
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	115 ms / 2,000 ms
コード長	11,275 bytes
コンパイル時間	3,998 ms
コンパイル使用メモリ	255,076 KB
実行使用メモリ	25,588 KB
平均クエリ数	951.59
最終ジャッジ日時	2024-06-24 04:23:38
合計ジャッジ時間	7,352 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	25 ms 25,324 KB
testcase_01	AC	23 ms 24,580 KB
testcase_02	AC	26 ms 25,220 KB
testcase_03	AC	25 ms 25,220 KB
testcase_04	AC	28 ms 24,836 KB
testcase_05	AC	24 ms 24,824 KB
testcase_06	AC	23 ms 25,220 KB
testcase_07	AC	24 ms 25,220 KB
testcase_08	AC	24 ms 24,580 KB
testcase_09	AC	23 ms 25,220 KB
testcase_10	AC	24 ms 24,836 KB
testcase_11	AC	23 ms 25,588 KB
testcase_12	AC	24 ms 24,964 KB
testcase_13	AC	24 ms 24,836 KB
testcase_14	AC	24 ms 24,836 KB
testcase_15	AC	29 ms 24,556 KB
testcase_16	AC	33 ms 24,940 KB
testcase_17	AC	33 ms 25,196 KB
testcase_18	AC	92 ms 25,220 KB
testcase_19	AC	70 ms 24,580 KB
testcase_20	AC	95 ms 24,836 KB
testcase_21	AC	82 ms 24,836 KB
testcase_22	AC	80 ms 25,348 KB
testcase_23	AC	106 ms 25,220 KB
testcase_24	AC	92 ms 25,220 KB
testcase_25	AC	114 ms 24,964 KB
testcase_26	AC	114 ms 24,812 KB
testcase_27	AC	115 ms 24,812 KB
testcase_28	AC	115 ms 25,196 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 ) )
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #define UNTIE 
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE )
  #define CERR( MESSAGE ) 
  #define COUT( ANSWER ) cout << ANSWER << endl
  #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#endif
#include <bits/stdc++.h>
using namespace std;
#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 SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX )
#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 QUIT return 0
#define RETURN( ANSWER ) COUT( ( ANSWER ) ); QUIT

#ifdef DEBUG
  inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }
#endif

// 入力フォーマットチェック用
// 1行中の変数の個数をSEPARATOR区切りで確認
#define GETLINE_COUNT( S , VARIABLE_NUMBER , SEPARATOR ) GETLINE( S ); int VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S = 0; int VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S  = S.size(); { int size = S.size(); int count = 0; for( int i = 0 ; i < size ; i++ ){ if( S.substr( i , 1 ) == SEPARATOR ){ count++; } } assert( count + 1 == VARIABLE_NUMBER ); }
// 余計な入力の有無を確認
#ifdef DEBUG
  #define CHECK_REDUNDANT_INPUT 
#else
  #define CHECK_REDUNDANT_INPUT string VARIABLE_FOR_CHECK_REDUNDANT_INPUT = ""; cin >> VARIABLE_FOR_CHECK_REDUNDANT_INPUT; assert( VARIABLE_FOR_CHECK_REDUNDANT_INPUT == "" ); assert( ! cin )
  // #define CHECK_REDUNDANT_INPUT string VARIABLE_FOR_CHECK_REDUNDANT_INPUT = ""; getline( cin , VARIABLE_FOR_CHECK_REDUNDANT_INPUT ); assert( VARIABLE_FOR_CHECK_REDUNDANT_INPUT == "" ); assert( ! cin )
#endif
// |N| <= BOUNDを満たすNをSから構築
#define STOI( S , N , BOUND ) TYPE_OF( BOUND ) N = 0; { bool VARIABLE_FOR_POSITIVITY_FOR_GETLINE = true; assert( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ); if( S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) == "-" ){ VARIABLE_FOR_POSITIVITY_FOR_GETLINE = false; VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; assert( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ); } assert( S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) != " " ); string VARIABLE_FOR_LETTER_FOR_GETLINE{}; int VARIABLE_FOR_DIGIT_FOR_GETLINE{}; while( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ? ( VARIABLE_FOR_LETTER_FOR_GETLINE = S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) ) != " " : false ){ VARIABLE_FOR_DIGIT_FOR_GETLINE = stoi( VARIABLE_FOR_LETTER_FOR_GETLINE ); assert( N < BOUND / 10 ? true : N == BOUND / 10 && VARIABLE_FOR_DIGIT_FOR_GETLINE <= BOUND % 10 ); N = N * 10 + VARIABLE_FOR_DIGIT_FOR_GETLINE; VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } if( ! VARIABLE_FOR_POSITIVITY_FOR_GETLINE ){ N *= -1; } if( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ){ VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } }
// SをSEPARATORで区切りTを構築
#define SEPARATE( S , T , SEPARATOR ) string T{}; { assert( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ); int VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S_prev = VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S; assert( S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) != SEPARATOR ); string VARIABLE_FOR_LETTER_FOR_GETLINE{}; while( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ? ( VARIABLE_FOR_LETTER_FOR_GETLINE = S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) ) != SEPARATOR : false ){ VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } T = S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S_prev , VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S - VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S_prev ); if( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ){ VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } }

// m_lengthの値は
// val_limit = 316 -> 65
// val_limit = 10^3 -> 168
// val_limit = 10^4 -> 1229
// val_limit = 10^5 -> 9592
// val_limit = 2×10^5 -> 17984
// 以下コンパイル畤計算の上限回数262144を超過。非constexpr変数を初期化すればよい。
// val_limit = 316228 -> 27293（実行時間4[ms]）
// val_limit = 10^6 -> 78498（実行時間8[ms]）
// val_limit = 10^7 -> 664579（実行時間93[ms]）
// val_limit = 10^8 -> 5761455（実行時間2839[ms]）
template <typename INT , INT val_limit , int length_max = val_limit>
class PrimeEnumeration
{

private:
  bool m_is_composite[val_limit];
  INT m_val[length_max];
  int m_length;

public:
  inline constexpr PrimeEnumeration();

  // 1+n個目の素数を返す。
  inline constexpr const INT& Get( const int& n ) const;

  // length_max個目の素数までで割り切れる合成数であるか否かを判定する。
  inline constexpr const bool& IsComposite( const int& i ) const;

  // val_limit未満の素数の個数Pi(val_limit)を返す。
  inline constexpr const int& length() const noexcept;

};

template <typename INT , INT val_limit , int length_max> inline constexpr PrimeEnumeration<INT,val_limit,length_max>::PrimeEnumeration() : m_is_composite() , m_val() , m_length( 0 )
{

  for( INT i = 2 ; i < val_limit ; i++ ){

    if( ! m_is_composite[i] ){

      INT j = i;

      while( ( j += i ) < val_limit ){

	m_is_composite[j] = true;

      }

      m_val[m_length++] = i;

      if( m_length >= length_max ){

	break;
	
      }

    }

  }

}

template <typename INT , INT val_limit , int length_max> inline constexpr const INT& PrimeEnumeration<INT,val_limit,length_max>::Get( const int& n ) const { assert( n < m_length ); return m_val[n]; }
template <typename INT , INT val_limit , int length_max> inline constexpr const bool& PrimeEnumeration<INT,val_limit,length_max>::IsComposite( const int& i ) const { assert( i < val_limit ); return m_is_composite[i]; }
template <typename INT , INT val_limit , int length_max> inline constexpr const int& PrimeEnumeration<INT,val_limit,length_max>::length() const noexcept { return m_length; }

inline CEXPR( int , bound_N , 1000 ); // 0が3個
class PrimeMax
{
public:
  int m_val[bound_N+1];
  constexpr PrimeMax( const PrimeEnumeration<int,bound_N>& pe ) : m_val()
  {
    const int& length = pe.length();
    const int& p_max = pe.Get( length - 1 );
    FOREQ( N , 2 , bound_N ){
      int& m_val_N = m_val[N] = p_max;
      FOR( i , 0 , length ){
	const int& p_i = pe.Get( i );
	if( p_i > N ){
	  assert( i > 0 );
	  const int& p_i_minus = pe.Get( i - 1 );
	  m_val_N = p_i_minus;
	  break;
	}
      }
      // ベルトランの公準
      assert( m_val_N * 2 > N );
    }
  }
};

int main()
{
  UNTIE;
  constexpr PrimeEnumeration<int,bound_N> pe{};
  constexpr PrimeMax pm{ pe };
  CIN_ASSERT( N , 1 , bound_N );
  if( N == 1 ){
    // 質問回数: 0 < 3*N
    RETURN( "! 1 1" );
  }
  int lcm[bound_N+1];
  int A[bound_N+1];
  int B[bound_N+1];
  int& B1 = B[1] = N + 1;
  FOREQ( i , 1 , N ){
    COUT( "? " << i << " " << 1 );
    int& lcm_i = lcm[i];
    cin >> lcm_i;
    if( B1 > lcm_i ){
      // B[1] は lcm(A[i],B[1]) の最小値
      B1 = lcm_i;
    }
  }
  const int& p_max = pm.m_val[N];
  if( B1 == p_max ){
    // A の中で 1 が現れうる箇所を格納
    int A_one_inv_candidate[2];
    int position_one = 0;
    FOREQ( i , 1 , N ){
      if( B1 == lcm[i] ){
	A_one_inv_candidate[position_one++] = i;
      }
    }
    // B[j] != p_max かつ lcm(A[i],B[j]) が p_max の倍数ならば A[i] == p_max
    COUT( "? " << A_one_inv_candidate[0] << " " << 2 );
    int& B2 = B[2];
    cin >> B2;
    if( B2 % p_max == 0 ){
      position_one = 1;
      B2 /= p_max;
    } else {
      position_one = 0;
    }
    int& A_one_inv = A_one_inv_candidate[position_one];
    int& A_p_max_inv = A_one_inv_candidate[1-position_one];
    A[A_one_inv] = 1;
    A[A_p_max_inv] = p_max;
    FOREQ( i , 1 , N ){
      if( i != A_one_inv && i != A_p_max_inv ){
	A[i] = lcm[i] / p_max;    
      }
    }
    FOREQ( j , 3 , N ){
      COUT( "? " << A_one_inv << " " << j );
      cin >> B[j];
    }
    // 質問回数: N+1+(N-2) == 2*N-1 < 3*N
  } else {
    int B1_p_max = p_max * B1;
    int A_p_max_inv = -1;
    FOREQ( i , 1 , N ){
      if( lcm[i] == B1_p_max ){
	// B[1] != p_max かつ p_max * 2 > N なので
	// lcm(A[i],B[1]) == B[1] * p_max ならば A[i] == p_max
	A_p_max_inv = i;
	break;
      }
    }
    // B の中で 1 か p_max が現れうる箇所を格納
    int B_one_inv_candidate[2] = { 1 };
    int position_one = B1 == 1 ? 1 : 0;
    FOREQ( j , 2 , N ){
      COUT( "? " << A_p_max_inv << " " << j );
      int& Bj = B[j];
      cin >> Bj;
      Bj /= p_max;
      if( Bj == 1 ){
	B_one_inv_candidate[position_one++] = j;
      }
    }
    int A_non_p_max_inv = A_p_max_inv == 1 ? 2 : 1;
    // p_max * 2 > Nなので
    // A[i] != p_max かつ lcm(A[i],B[j]) が p_max の倍数ならば B[j] == p_max
    COUT( "? " << A_non_p_max_inv << " " << B_one_inv_candidate[0] );
    int& A_non_p_max = A[A_non_p_max_inv];
    cin >> A_non_p_max;
    if( A_non_p_max % p_max == 0 ){
      position_one = 1;
      A_non_p_max /= p_max;
    } else {
      position_one = 0;
    }
    int& B_one_inv = B_one_inv_candidate[position_one];
    int& B_p_max_inv = B_one_inv_candidate[1-position_one];
    A[A_p_max_inv] = B[B_p_max_inv] = p_max;
    B[B_one_inv] = 1;
    FOREQ( i , 1 , N ){
      if( i != A_p_max_inv && i != A_non_p_max_inv ){
	COUT( "? " << i << " " << B_one_inv );
	cin >> A[i];
      }
    }
    // 質問回数: N+(N-1)+1+(N-2) == 3*N-2 < 3*N
  }
  // CHECK_REDUNDANT_INPUT;
  cout << "! ";
  set<int> A_set{};
  FOREQ( i , 1 , N ){
    int& Ai = A[i];
    ASSERT( Ai , 1 , N );
    assert( A_set.count( Ai ) == 0 );
    A_set.insert( Ai );
    cout << Ai << " ";
  }
  set<int> B_set{};
  FOREQ( j , 1 , N ){
    int& Bj = B[j];
    ASSERT( Bj , 1 , N );
    assert( B_set.count( Bj ) == 0 );
    B_set.insert( Bj );
    cout << Bj << " ";
  }
  QUIT;
}

yukicoder

結果

テストケース

ソースコード