#928990 (C++17) No.2577 Simple Permutation Guess

提出ソース

結果

問題	No.2577 Simple Permutation Guess
ユーザー	👑 p-adic
提出日時	2023-11-15 21:24:08
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	151 ms / 2,000 ms
コード長	13,706 bytes
コンパイル時間	3,551 ms
コンパイル使用メモリ	232,812 KB
実行使用メモリ	24,012 KB
平均クエリ数	251.88
最終ジャッジ日時	2023-12-04 00:26:58
合計ジャッジ時間	14,887 ms
ジャッジサーバーID （参考情報）	judge11 / judge12

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	27 ms 24,000 KB
testcase_01	AC	123 ms 24,000 KB
testcase_02	AC	47 ms 24,000 KB
testcase_03	AC	25 ms 24,000 KB
testcase_04	AC	62 ms 24,000 KB
testcase_05	AC	71 ms 24,000 KB
testcase_06	AC	150 ms 24,000 KB
testcase_07	AC	151 ms 24,000 KB
testcase_08	AC	148 ms 24,000 KB
testcase_09	AC	151 ms 24,000 KB
testcase_10	AC	148 ms 24,000 KB
testcase_11	AC	24 ms 24,000 KB
testcase_12	AC	24 ms 24,000 KB
testcase_13	AC	27 ms 24,000 KB
testcase_14	AC	25 ms 24,000 KB
testcase_15	AC	25 ms 24,000 KB
testcase_16	AC	24 ms 24,000 KB
testcase_17	AC	24 ms 24,000 KB
testcase_18	AC	24 ms 24,000 KB
testcase_19	AC	24 ms 24,000 KB
testcase_20	AC	25 ms 24,000 KB
testcase_21	AC	23 ms 24,000 KB
testcase_22	AC	24 ms 24,012 KB
testcase_23	AC	24 ms 24,012 KB
testcase_24	AC	25 ms 24,012 KB
testcase_25	AC	24 ms 24,012 KB
testcase_26	AC	24 ms 24,012 KB
testcase_27	AC	24 ms 24,012 KB
testcase_28	AC	25 ms 24,012 KB
testcase_29	AC	25 ms 24,012 KB
testcase_30	AC	25 ms 24,012 KB
testcase_31	AC	24 ms 24,000 KB
testcase_32	AC	25 ms 24,000 KB
testcase_33	AC	24 ms 24,000 KB
testcase_34	AC	25 ms 24,000 KB
testcase_35	AC	24 ms 24,000 KB
testcase_36	AC	24 ms 24,000 KB
testcase_37	AC	24 ms 24,000 KB
testcase_38	AC	24 ms 24,000 KB
testcase_39	AC	24 ms 24,000 KB
testcase_40	AC	24 ms 24,000 KB
testcase_41	AC	25 ms 24,000 KB
testcase_42	AC	24 ms 24,000 KB
testcase_43	AC	24 ms 24,000 KB
testcase_44	AC	24 ms 24,000 KB
testcase_45	AC	23 ms 24,000 KB
testcase_46	AC	24 ms 24,000 KB
testcase_47	AC	24 ms 24,000 KB
testcase_48	AC	24 ms 24,000 KB
testcase_49	AC	24 ms 24,000 KB
testcase_50	AC	24 ms 24,000 KB
testcase_51	AC	24 ms 24,000 KB
testcase_52	AC	24 ms 24,000 KB
testcase_53	AC	24 ms 24,000 KB
testcase_54	AC	24 ms 24,000 KB
testcase_55	AC	24 ms 24,000 KB
testcase_56	AC	24 ms 24,000 KB
testcase_57	AC	24 ms 24,000 KB
testcase_58	AC	25 ms 24,000 KB
testcase_59	AC	24 ms 24,000 KB
testcase_60	AC	24 ms 24,000 KB
testcase_61	AC	24 ms 24,000 KB
testcase_62	AC	23 ms 24,000 KB
testcase_63	AC	24 ms 24,000 KB
testcase_64	AC	25 ms 24,012 KB
testcase_65	AC	24 ms 24,012 KB
testcase_66	AC	24 ms 24,012 KB
testcase_67	AC	24 ms 24,012 KB
testcase_68	AC	24 ms 24,012 KB
testcase_69	AC	24 ms 24,012 KB
testcase_70	AC	24 ms 24,012 KB
testcase_71	AC	24 ms 24,012 KB
testcase_72	AC	24 ms 24,012 KB
testcase_73	AC	24 ms 24,000 KB
testcase_74	AC	26 ms 24,000 KB
testcase_75	AC	26 ms 24,000 KB
testcase_76	AC	26 ms 24,000 KB
testcase_77	AC	26 ms 24,000 KB
testcase_78	AC	26 ms 24,000 KB
testcase_79	AC	27 ms 24,000 KB
testcase_80	AC	27 ms 24,000 KB
testcase_81	AC	27 ms 24,000 KB
testcase_82	AC	27 ms 24,000 KB
testcase_83	AC	26 ms 24,000 KB
testcase_84	AC	26 ms 24,000 KB
testcase_85	AC	27 ms 24,000 KB
testcase_86	AC	27 ms 24,000 KB
testcase_87	AC	27 ms 24,012 KB
testcase_88	AC	27 ms 24,012 KB
testcase_89	AC	27 ms 24,012 KB
testcase_90	AC	28 ms 24,012 KB
testcase_91	AC	27 ms 24,012 KB
testcase_92	AC	126 ms 24,012 KB
testcase_93	AC	114 ms 24,012 KB
testcase_94	AC	110 ms 24,012 KB
testcase_95	AC	142 ms 24,012 KB
testcase_96	AC	144 ms 24,012 KB
testcase_97	AC	137 ms 24,012 KB
testcase_98	AC	134 ms 24,012 KB
testcase_99	AC	138 ms 24,012 KB
testcase_100	AC	114 ms 24,012 KB
testcase_101	AC	135 ms 24,012 KB
evil_1_rnd_1.txt	RE	-
evil_1_rnd_2.txt	RE	-
evil_2_big_1.txt	RE	-
evil_2_big_2.txt	RE	-
evil_2_big_3.txt	RE	-
evil_3_sorted_1.txt	RE	-
evil_4_sorted_rev_1.txt	RE	-
evil_4_sorted_rev_2.txt	RE	-
evil_400_sorted.txt	RE	-
evil_400_sorted_rev.txt	RE	-

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

ソースコード

raw source code

// 入力フォーマットチェック
#ifdef DEBUG
  #define _GLIBCXX_DEBUG
  #define SIGNAL signal( SIGABRT , &AlertAbort );
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE )
  #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック： " , ( MIN ) , ( ( MIN ) <= A ? "<=" : ">" ) , A , ( A <= ( MAX ) ? "<=" : ">" ) , ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) )
  #define CERR( ... ) VariadicCout( cerr , __VA_ARGS__ ) << endl
  #define COUT( ... ) VariadicCout( cout << "出力： " , __VA_ARGS__ ) << endl
  #define CERR_A( A , N ) OUTPUT_ARRAY( cerr , A , N ) << endl
  #define COUT_A( A , N ) cout << "出力： "; OUTPUT_ARRAY( cout , A , N ) << endl
  #define CERR_ITR( A ) OUTPUT_ITR( cerr , A ) << endl
  #define COUT_ITR( A ) cout << "出力： "; OUTPUT_ITR( cout , A ) << endl
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize ( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #define SIGNAL 
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE )
  #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
  #define CERR( ... ) 
  #define COUT( ... ) VariadicCout( cout , __VA_ARGS__ ) << endl
  #define CERR_A( A , N ) 
  #define COUT_A( A , N ) OUTPUT_ARRAY( cout , A , N ) << endl
  #define CERR_ITR( A ) 
  #define COUT_ITR( A ) OUTPUT_ITR( cout , A ) << endl
#endif
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using lld = __float128;
template <typename INT> using T2 = pair<INT,INT>;
template <typename INT> using T3 = tuple<INT,INT,INT>;
template <typename INT> using T4 = tuple<INT,INT,INT,INT>;
#define SET_TESTCASE_NUM SET_ASSERT( test_case_num , 1 , bound_test_case_num );
// #define #define SET_TESTCASE_NUM GETLINE_COUNT( test_case_num_str , 1 , " " ); STOI( test_case_num_str , test_case_num_prep , bound_test_case_num ); test_case_num = test_case_num_prep
#define REPEAT_MAIN( BOUND ) int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr ); SIGNAL; DEXPR( int , bound_test_case_num , BOUND , min( BOUND , 100 ) ); int test_case_num = 1; if constexpr( bound_test_case_num > 1 ){ SET_TESTCASE_NUM; } REPEAT( test_case_num ){ if constexpr( bound_test_case_num > 1 ){ CERR( "testcase " , VARIABLE_FOR_REPEAT_test_case_num , ":" ); } Solve(); CERR( "" ); } }
#define START_WATCH chrono::system_clock::time_point watch = chrono::system_clock::now()
#define CURRENT_TIME static_cast<double>( chrono::duration_cast<chrono::microseconds>( chrono::system_clock::now() - watch ).count() / 1000.0 )
#define CHECK_WATCH( TL_MS ) ( CURRENT_TIME < TL_MS - 100.0 )
#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define CIN( LL , ... ) LL __VA_ARGS__; VariadicCin( cin , __VA_ARGS__ )
#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 SET_A( A , N ) SOLVE_ONLY; FOR( VARIABLE_FOR_CIN_A , 0 , N ){ cin >> A[VARIABLE_FOR_CIN_A]; }
#define CIN_A( LL , A , N ) vector<LL> A( N ); SET_A( A , N );
#define GETLINE_SEPARATE( SEPARATOR , ... ) string __VA_ARGS__; VariadicGetline( cin , SEPARATOR , __VA_ARGS__ )
#define GETLINE( ... ) GETLINE_SEPARATE( '\n' , __VA_ARGS__ )
#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 OUTPUT_ARRAY( OS , A , N ) FOR( VARIABLE_FOR_OUTPUT_ARRAY , 0 , N ){ OS << A[VARIABLE_FOR_OUTPUT_ARRAY] << (VARIABLE_FOR_OUTPUT_ARRAY==N-1?"":" "); } OS
#define OUTPUT_ITR( OS , A ) { auto ITERATOR_FOR_OUTPUT_ITR = A.begin() , END_FOR_OUTPUT_ITR = A.end(); bool VARIABLE_FOR_OUTPUT_ITR = ITERATOR_FOR_COUT_ITR != END_FOR_COUT_ITR; while( VARIABLE_FOR_OUTPUT_ITR ){ OS << *ITERATOR_FOR_COUT_ITR; ( VARIABLE_FOR_OUTPUT_ITR = ++ITERATOR_FOR_COUT_ITR != END_FOR_COUT_ITR ) ? OS : OS << " "; } } OS
#define RETURN( ... ) COUT( __VA_ARGS__ ); return

// 入出力用
template <class Traits> inline basic_istream<char,Traits>& VariadicCin( basic_istream<char,Traits>& is ) { return is; }
template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicCin( basic_istream<char,Traits>& is , Arg& arg , ARGS&... args ) { return VariadicCin( is >> arg , args... ); }
template <class Traits> inline basic_istream<char,Traits>& VariadicGetline( basic_istream<char,Traits>& is , const char& separator ) { return is; }
template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicGetline( basic_istream<char,Traits>& is , const char& separator , Arg& arg , ARGS&... args ) { return VariadicGetline( getline( is , arg , separator ) , separator , args... ); }
template <class Traits , typename Arg> inline basic_ostream<char,Traits>& VariadicCout( basic_ostream<char,Traits>& os , const Arg& arg ) { return os << arg; }
template <class Traits , typename Arg1 , typename Arg2 , typename... ARGS> inline basic_ostream<char,Traits>& VariadicCout( basic_ostream<char,Traits>& os , const Arg1& arg1 , const Arg2& arg2 , const ARGS&... args ) { return VariadicCout( os << arg1 << " " , arg2 , args... ); }

// デバッグ用
#ifdef DEBUG
  inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }
  void AutoCheck( bool& auto_checked );
#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 ++; } }

// 二分探索テンプレート
// EXPRESSIONがANSWERの広義単調関数の時、EXPRESSION >= TARGETの整数解を格納。
#define BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , DESIRED_INEQUALITY , TARGET , INEQUALITY_FOR_CHECK , UPDATE_U , UPDATE_L , UPDATE_ANSWER ) \
  static_assert( ! is_same<TYPE_OF( TARGET ),uint>::value && ! is_same<TYPE_OF( TARGET ),ull>::value ); \
  ll ANSWER = MINIMUM;							\
  ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM;				\
  ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM;				\
  ANSWER = UPDATE_ANSWER; \
  while( VARIABLE_FOR_BINARY_SEARCH_L < VARIABLE_FOR_BINARY_SEARCH_U ){ \
    CERR( "二分探索中：" , VARIABLE_FOR_BINARY_SEARCH_L , "<", VARIABLE_FOR_BINARY_SEARCH_U ); \
    ll VARIABLE_FOR_EXPRESSION_FOR_BINARY_SEARCH = ( EXPRESSION ); \
    ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = VARIABLE_FOR_EXPRESSION_FOR_BINARY_SEARCH - ( TARGET ); \
    CERR( "( EXPRESSION =" , VARIABLE_FOR_EXPRESSION_FOR_BINARY_SEARCH , ")" , ( VARIABLE_FOR_EXPRESSION_FOR_BINARY_SEARCH == TARGET ? "==" : VARIABLE_FOR_EXPRESSION_FOR_BINARY_SEARCH < TARGET ? "<" : ">" ) , TARGET ); \
    if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH INEQUALITY_FOR_CHECK 0 ){ \
      VARIABLE_FOR_BINARY_SEARCH_U = UPDATE_U;				\
    } else {								\
      VARIABLE_FOR_BINARY_SEARCH_L = UPDATE_L;				\
    }									\
    ANSWER = UPDATE_ANSWER;						\
  }									\
  if( VARIABLE_FOR_BINARY_SEARCH_L > VARIABLE_FOR_BINARY_SEARCH_U ){	\
    CERR( "二分探索失敗：" ); \
    ANSWER = MAXIMUM + 1;						\
  } else {								\
    CERR( "二分探索終了：" ); \
  }									\

// 単調増加の時にEXPRESSION >= TARGETの最小解を格納。
#define BS1( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET )		\
  BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , >= , TARGET , >= , ANSWER , ANSWER + 1 , ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \

// 単調増加の時にEXPRESSION <= TARGETの最大解を格納。
#define BS2( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET )		\
  BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , <= , TARGET , > , ANSWER - 1 , ANSWER , ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \

// 単調減少の時にEXPRESSION >= TARGETの最大解を格納。
#define BS3( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET )		\
  BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , >= , TARGET , < , ANSWER - 1 , ANSWER , ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \

// 単調減少の時にEXPRESSION <= TARGETの最小解を格納。
#define BS4( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET )		\
  BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , <= , TARGET , <= , ANSWER , ANSWER + 1 , ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \

inline void Solve()
{
  CEXPR( int , bound_N , 250 );
  GETLINE_COUNT( N_str , 1 , " " );
  STOI( N_str , N , bound_N );
  int Q[N]{};
  if( N < 10 ){
    ll fact[N+1] = { 1 };
    FOREQ( i , 1 , N ){
      fact[i] = fact[i-1] * i;
    }
    auto enum_fact = [&]( ll k ){
      set<int> unused{};
      FOREQ( i , 1 , N ){
	unused.insert( i );
      }
      FOR( i , 0 , N ){
	int rest[N - i];
	{
	  int j = 0;
	  FOR_ITR( unused ){
	    rest[j++] = *itr;
	  }
	}
	unused.erase( Q[i] = rest[k / fact[N - i - 1] ] );
	k %= fact[N - i - 1];
      }
    };
    auto Ask = [&]( ll k ){
      enum_fact( k );
      cout << "? ";
      COUT_A( Q , N );
      GETLINE_COUNT( QleqP_str , 1 , " " );
      STOI( QleqP_str , QleqP , 1 );
      return QleqP;
    };
    BS3( k , 0 , fact[N] - 1 , Ask( k ) , 1 );
    enum_fact( k );
  } else {
    set<int> unused{};
    FOREQ( i , 1 , N ){
      unused.insert( i );
    }
    FOR( i , 0 , N - 1 ){
      int rest[N - i];
      {
	int j = 0;
	FOR_ITR( unused ){
	  rest[j++] = *itr;
	}
      }
      auto Ask = [&](int k){
	Q[i] = rest[k];
	int j = i + 1;
	FOR_ITR( unused ){
	  if( *itr != Q[i] ){ 
	    Q[j++] = *itr;
	  }
	}
	cout << "? ";
	COUT_A( Q , N );
	GETLINE_COUNT( QleqP_str , 1 , " " );
	STOI( QleqP_str , QleqP , 1 );
	return QleqP;
      };
      BS3( k , 0 , N - i - 1 , Ask( k ) , 1 );
      unused.erase( Q[i] = rest[k] );
    }
    Q[N - 1] = *( unused.begin() );
  }
  cout << "! ";
  COUT_A( Q , N );
}

REPEAT_MAIN(1);

yukicoder

結果

テストケース

ソースコード