// テストケースバリデーション #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 using namespace std; #define TYPE_OF( VAR ) decay_t #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 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 inline constexpr PrimeEnumeration::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 inline constexpr const INT& PrimeEnumeration::Get( const int& n ) const { assert( n < m_length ); return m_val[n]; } template inline constexpr const bool& PrimeEnumeration::IsComposite( const int& i ) const { assert( i < val_limit ); return m_is_composite[i]; } template inline constexpr const int& PrimeEnumeration::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& 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 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 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 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; }