結果

問題 No.2376 障害物競プロ
ユーザー 👑 p-adicp-adic
提出日時 2023-07-07 23:04:03
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 285 ms / 4,000 ms
コード長 37,549 bytes
コンパイル時間 13,892 ms
コンパイル使用メモリ 295,652 KB
最終ジャッジ日時 2025-02-15 08:18:50
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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( ANSWER ) cerr << ANSWER << 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 LIBRARY_SEARCH if( LibrarySearch() != 0 ){ QUIT; };
#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( ANSWER )
#define COUT( ANSWER ) cout << ANSWER << "\n"
#define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#define LIBRARY_SEARCH
#define START_WATCH( PROCESS_NAME )
#define STOP_WATCH( HOW_MANY_TIMES )
#endif
#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 ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX )
#define SET_ASSERT( A , MIN , MAX ) cin >> A; 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 QUIT return 0
#define SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS )
#define RETURN( ANSWER ) COUT( ( ANSWER ) ); QUIT
#ifdef DEBUG
inline void AlertAbort( int n ) { CERR(
      "abortassert" ); }
void StartWatch( const string& process_name = "nothing" );
void StopWatch( const int& how_many_times = 1 );
#endif
template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : -a; }
template <typename T> inline T Residue( const T& a , const T& p ){ return a >= 0 ? a % p : p - 1 - ( ( - ( a + 1 ) ) % p ); }
#define POWER( ANSWER , ARGUMENT , EXPONENT ) \
static_assert( ! is_same<TYPE_OF( ARGUMENT ),int>::value && ! is_same<TYPE_OF( ARGUMENT ),uint>::value ); \
TYPE_OF( ARGUMENT ) ANSWER{ 1 }; \
{ \
TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT ); \
TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \
while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \
if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \
ANSWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \
} \
ARGUMENT_FOR_SQUARE_FOR_POWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \
EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \
} \
} \
#define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO ) \
ll ANSWER{ 1 }; \
{ \
ll ARGUMENT_FOR_SQUARE_FOR_POWER = ( ( MODULO ) + ( ( ARGUMENT ) % ( MODULO ) ) ) % ( MODULO ); \
TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \
while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \
if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \
ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % ( MODULO ); \
} \
ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % ( MODULO ); \
EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \
} \
} \
#define FACTORIAL_MOD( ANSWER , ANSWER_INV , INVERSE , MAX_INDEX , CONSTEXPR_LENGTH , MODULO ) \
static ll ANSWER[CONSTEXPR_LENGTH]; \
static ll ANSWER_INV[CONSTEXPR_LENGTH]; \
static ll INVERSE[CONSTEXPR_LENGTH]; \
{ \
ll VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \
ANSWER[0] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL; \
FOREQ( i , 1 , MAX_INDEX ){ \
ANSWER[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= i ) %= ( MODULO ); \
} \
ANSWER_INV[0] = ANSWER_INV[1] = INVERSE[1] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \
FOREQ( i , 2 , MAX_INDEX ){ \
ANSWER_INV[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= INVERSE[i] = ( MODULO ) - ( ( ( ( MODULO ) / i ) * INVERSE[ ( MODULO ) % i ] ) % (
          MODULO ) ) ) %= ( MODULO ); \
} \
} \
//
// EXPRESSIONANSWER調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; \
if( MINIMUM <= MAXIMUM ){ \
ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \
ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM; \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH; \
while( VARIABLE_FOR_BINARY_SEARCH_L != VARIABLE_FOR_BINARY_SEARCH_U ){ \
VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \
CERR( " " << VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" <<
          TARGET << "=" << VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ); \
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; \
} \
CERR( " " << VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << (
        EXPRESSION > TARGET ? ">" : EXPRESSION < TARGET ? "<" : "=" ) << TARGET ); \
CERR( ( EXPRESSION DESIRED_INEQUALITY TARGET ? "" : "" ) ); \
assert( EXPRESSION DESIRED_INEQUALITY TARGET ); \
} else { \
CERR( " " << MINIMUM << ">" << MAXIMUM ); \
assert( MINIMUM <= MAXIMUM ); \
} \
// 調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 ) \
//
#define TE template
#define TY typename
#define US using
#define ST static
#define IN inline
#define CL class
#define PU public
#define OP operator
#define CE constexpr
#define CO const
#define NE noexcept
#define RE return
#define WH while
#define VO void
#define VE vector
#define LI list
#define BE begin
#define EN end
#define SZ size
#define MO move
#define TH this
#define CRI CO int&
#define CRUI CO uint&
#define CRL CO ll&
#define ASK_DETAILS( ... ) \
CERR( "" ); \
problems = { __VA_ARGS__ }; \
problems_size = problems.size(); \
FOR( i , 0 , problems_size ){ \
CERR( i << ": " << problems[i] ); \
} \
cin >> num; \
CERR( "" ); \
num_temp = 0; \
if( num < 0 || num >= problems_size ){ \
CERR( "" << problems_size - 1 << "" ); \
CERR( "" ); \
CERR( "" ); \
return -1; \
} \
int LibrarySearch( int num = -1 )
{
vector<string> problems{};
int problems_size = 13;
int num_temp = 0;
string reply{};
if( num == -1 ){
CERR( "[y/n]" );
cin >> reply;
if( reply == "n" ){
CERR( "" );
CERR( "" );
return 0;
} else if( reply != "y" ){
CERR( "y/n" );
CERR( "" );
CERR( "" );
return -1;
}
CERR( "" );
CERR( "" );
ASK_DETAILS(
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
""
);
} else {
CERR( "" );
}
CEXPR( int , num_graph , 5 );
CEXPR( int , num_subsequence_sum , 6 );
CEXPR( int , num_game , 8 );
if( num == num_temp++ ){
CERR( "[y/n]" );
cin >> reply;
CERR( "" );
if( reply == "y" ){
CERR( "OEIS" );
CERR( "https://oeis.org/?language=japanese" );
CERR( "" );
CERR( "" );
CERR( "- 調" );
CERR( "- p使" );
CERR( "- pp" );
CERR( " " );
CERR( "" );
} else if( reply == "n" ){
ASK_DETAILS(
"" ,
"" ,
"" ,
""
);
if( num == num_temp++ ){
CERR( "" );
CERR( "- 調" );
CERR( "- " );
CERR( "- " );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "- " );
CERR( "- " );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "- " );
CERR( "- " );
CERR( "- " );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "Sa" );
CERR( "- si" );
CERR( " a[i]<=si" );
CERR( "- ia[i]Ss" );
CERR( " a[i]<=ss" );
CERR( "" );
}
} else {
CERR( "y/n" );
CERR( "" );
CERR( "" );
return -1;
}
CERR( "" );
CERR( "[y/n]" );
cin >> reply;
CERR( "" );
if( reply == "y" ){
CERR( "N" );
CERR( "使" );
CERR( "TLE" );
CERR( "" );
CERR( "static" );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( "- " );
CERR( "- " );
CERR( "" );
} else if( reply == "n" ){
CERR( "" );
} else {
CERR( "y/n" );
CERR( "" );
CERR( "" );
return -1;
}
CERR( "" );
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
"" ,
"" ,
"" ,
""
);
if( num == num_temp++ ){
ASK_DETAILS(
"+使" ,
"使" ,
"*使" ,
"*使" ,
"(*,\\cdot)使" ,
"(+,\\cdot)使" ,
"max使"
);
if( num == num_temp++ ){
CERR( "- BIT" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\Template" );
CERR( "- " );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template" );
CERR( "- " );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\Tree\\DifferenceSeqeuence" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "- BIT" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\IntervalMax\\Template" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "- BIT" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\Template\\Monoid" );
CERR( "- " );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\Monoid" );
CERR( "- " );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SegmentTree" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "- " );
CERR( " \\Mathematics\\Function\\Encoder" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "- " );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\Dual" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "- " );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\LazyEvaluation" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "max" );
CERR( "調max調" );
CERR( "" );
CERR( "" );
CERR( "maxmax調" );
CERR( "maxmax" );
CERR( "調" );
CERR( "調" );
CERR( "" );
CERR( "max{0,1}" );
CERR( "使" );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "B_qmax(A_i,B_q)" );
CERR( "- A'={(A_i,i)|i}O(N log N)" );
CERR( "- (B_q,q)_qB'O(Q log Q)" );
CERR( "- NC=(0,...,0)O(N)" );
CERR( "B'(B_q,q)" );
CERR( "A'A_i<B_qi" );
CERR( "- A'(A_i,i)O(N)" );
CERR( "- A_i0O(N log N)" );
CERR( "- C_i1O(log N)" );
CERR( "- A+C×B_qO(log N)" );
CERR( "O((N + Q)log N + Q log Q)" );
}
} else if( num == num_temp++ ){
CERR( "fx" );
CERR( "- ixX(i)" );
CERR( "- ixi+1xdX(i)" );
CERR( "" );
CERR( "- O(sum_i X(i) dX(i))fxO(1)ix" );
CERR( "- O(N log_2 X(N))" );
CERR( " - fxO(N)x調x" );
CERR( " - fxO(N/x)x" );
CERR( "- O(N log_2 N)xfxO(log_2 N)" );
CERR( " x" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- " );
CERR( " " );
CERR( "- " );
CERR( " " );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "gcdmax" );
CERR( "" );
} else if( num == num_temp++ ){
return LibrarySearch( num = num_subsequence_sum );
}
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
""
);
if( num == num_temp++ ){
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( " - O(N)" );
CERR( " - O(N)" );
CERR( "- " );
CERR( " \\Utility\\String\\RollingHash" );
CERR( "- Z" );
CERR( " https://qiita.com/Pro_ktmr/items/16904c9570aa0953bf05" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- O(N^2)" );
CERR( "- O(N^2)Manacher" );
CERR( " https://snuke.hatenablog.com/entry/2014/12/02/235837" );
CERR( "" );
}
} else if( num == num_temp++ ){
CERR( "" );
CERR( "" );
CERR( "- O(N^3)" );
CERR( "- O(N 2^N)" );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "- O(N^2)" );
CERR( "- O(N log_2 N)BIT" );
CERR( " \\Mathematics\\Combinatorial\\Permutation" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT" );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "i<j" );
CERR( "" );
CERR( "" );
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
"" ,
""
);
if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_graph );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- 調" );
CERR( "- " );
CERR( "- " );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- O(HW)" );
CERR( "- O(HW)" );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( "" );
}
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
"" ,
"" ,
""
);
if( num == num_temp++ ){
CERR( "" );
CERR( "" );
CERR( "- BFSDijkstra" );
CERR( " \\Utility\\Search\\BreadthFirst" );
CERR( " \\Utility\\Search\\Dijkstra" );
CERR( "- " );
CERR( " - O(V^3)FloydWarshall" );
CERR( " \\Utility\\Search\\FloydWarshall" );
CERR( " - maxO(E(log_2 E + α(V)))UnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "HeldKarp" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "\\Utility\\Search\\DepthFirst" );
CERR( "\\Utility\\VLTree" );
} else if( num == num_temp++ ){
CERR( "- 0UnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "- " );
CERR( " \\Utility\\Search\\DepthFirst" );
CERR( "- " );
CERR( "" );
}
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
""
);
if( num == num_temp++ ){
CERR( "NWV" );
CERR( "- B=∞" );
CERR( "- B<∞O(2^N)" );
CERR( "- B<∞O(N 2^{N/2})" );
CERR( "- B<∞O(NV)[B-V,B+V]" );
CERR( " " );
CERR( " https://stackoverflow.com/a/18949218" );
CERR( "- W10^5O((N+W)log_2 W)" );
CERR( " " );
CERR( " \\Mathematics\\Polynomial" );
CERR( "- O(N 2^N)bit" );
} else if( num == num_temp++ ){
CERR( "NW" );
CERR( "- O(2^N)" );
CERR( "- O(2^N)" );
CERR( "- O(2^{N/2}N)" );
CERR( " " );
CERR( "- W10^5O((N+W)log_2 W)" );
CERR( " " );
CERR( " \\Mathematics\\Polynomial" );
}
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( "- " );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- " );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace" );
CERR( "- UnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "" );
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
""
);
if( num == num_temp++ ){
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_graph );
}
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
""
);
if( num == num_temp++ ){
CERR( "NTK" );
CERR( "- O((N + T)log_2 K)" );
CERR( " \\Mathematics\\Function\\Iteration\\Doubling" );
CERR( "- O(TN)" );
CERR( " \\Mathematics\\Function\\Iteration\\LoopDetection" );
CERR( "- O(N)" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_graph );
}
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
"" ,
"" ,
""
);
if( num == num_temp++ ){
CERR( "p" );
} else if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_graph );
} else if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_game );
} else if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_game );
}
}
CERR( "" );
CERR( "" );
CERR( "" );
return -1;
}
//
// (1) (T,m_T:T^2->T,e_T:1->T)bool operator<(const T&,const T&)
// (2) de_T()infty
// (3) inftye_T()size_max
//
// O(size_max^3)
template <typename T , T m_T(const T&,const T&) , const T& e_T() , int size_max>
void FloydWarshall( const T ( &d )[size_max][size_max] , T ( &weight )[size_max][size_max] , const int& size , const T& infty );
template <typename T , T m_T(const T&,const T&) , const T& e_T() , int size_max>
void FloydWarshall( const T ( &d )[size_max][size_max] , T ( &weight )[size_max][size_max] , const int& size , const T& infty )
{
for( int i = 0 ; i < size ; i++ ){
T ( &weight_i )[size_max] = weight[i];
const T ( &d_i )[size_max] = d[i];
for( int j = 0 ; j < size ; j++ ){
weight_i[j] = d_i[j];
}
}
for( int k = 0 ; k < size ; k++ ){
T ( &weight_k )[size_max] = weight[k];
for( int i = 0 ; i < size ; i++ ){
T ( &weight_i )[size_max] = weight[i];
const T& weight_ik = weight_i[k];
if( weight_ik != infty ){
for( int j = 0 ; j < size ; j++ ){
const T& weight_kj = weight_k[j];
if( weight_kj != infty ){
T& weight_ij = weight_i[j];
const T weight_curr = m_T( weight_ik , weight_kj );
if( weight_ij == infty ? true : weight_ij > weight_curr ){
weight_ij = weight_curr;
}
}
}
}
}
}
return;
}
inline double add( const double& t0 , const double& t1 ) { return t0 + t1; }
inline const double& zero() { static const double z = 0.0; return z; }
int main()
{
UNTIE;
LIBRARY_SEARCH;
// DEXPR( int , bound_T , 100000 , 100 );
// CIN_ASSERT( T , 1 , bound_T );
// REPEAT( T ){
// }
CEXPR( int , bound_N , 150 );
// DEXPR( int , bound_N , 100000 , 100 ); // 05
// CEXPR( int , bound_N , 1000000000 ); // 09
// CEXPR( ll , bound_N , 1000000000000000000 ); // 018
CIN_ASSERT( N , 2 , bound_N );
DEXPR( int , bound_M , 200000 , 100 ); // 05
// CEXPR( int , bound_M , 1000000000 ); // 09
// CEXPR( ll , bound_M , 1000000000000000000 ); // 018
CIN_ASSERT( M , 1 , bound_M );
CEXPR( int , bound_xy , 10000 );
pair<int,int> xy[bound_N * 2];
int N2 = N * 2;
FOR( i , 0 , N2 ){
CIN_ASSERT( xi , -bound_xy , bound_xy );
CIN_ASSERT( yi , -bound_xy , bound_xy );
xy[i] = { xi , yi };
}
pair<int,int> ab[bound_M * 2];
int M2 = M * 2;
FOR( i , 0 , M2 ){
CIN_ASSERT( ai , 1 , N );
CIN_ASSERT( bi , 1 , 2 );
ab[i] = { --ai , --bi };
}
double d[bound_N*2][bound_N*2];
double infty = -1.0;
FOR( i , 0 , N2 ){
pair<int,int>& xyi = xy[i];
double( &d_i )[bound_N*2] = d[i];
FOR( j , i + 1 , N2 ){
pair<int,int>& xyj = xy[j];
pair<int,int> dij = { xyj.first - xyi.first , xyj.second - xyi.second };
bool connected = true;
FOR( k , 0 , N ){
pair<int,int>& xyk0 = xy[2 * k];
pair<int,int>& xyk1 = xy[2 * k + 1];
pair<int,int> dik0 = { xyk0.first - xyi.first , xyk0.second - xyi.second };
pair<int,int> dik1 = { xyk1.first - xyi.first , xyk1.second - xyi.second };
pair<int,int> dk0k1 = { xyk1.first - xyk0.first , xyk1.second - xyk0.second };
pair<int,int> djk0 = { xyk0.first - xyj.first , xyk0.second - xyj.second };
ll t0 = dij.first * dik0.second - dij.second * dik0.first;
ll t1 = dij.first * dik1.second - dij.second * dik1.first;
ll t2 = dk0k1.first * dik0.second - dk0k1.second * dik0.first;
ll t3 = dk0k1.first * djk0.second - dk0k1.second * djk0.first;
if( t0 * t1 < 0 && t2 * t3 < 0 ){
connected = false;
break;
}
}
d_i[j] = d[j][i] = connected ? sqrt( dij.first * dij.first + dij.second * dij.second ) : infty;
CERR( i << "," << j << "," << d_i[j] );
}
}
double weight[bound_N*2][bound_N*2];
FloydWarshall<double,add,zero,bound_N*2>( d , weight , N * 2 , infty );
SET_PRECISION( 6 );
FOR( i , 0 , M ){
pair<int,int>& ab_i0 = ab[2 * i];
pair<int,int>& ab_i1 = ab[2 * i + 1];
COUT( weight[2 * ab_i0.first + ab_i0.second][2 * ab_i1.first + ab_i1.second] );
}
// CEXPR( ll , P , 998244353 );
// CEXPR( ll , P , 1000000007 );
// DEXPR( int , bound_Q , 100000 , 100 );
// CIN_ASSERT( Q , 1 , bound_Q );
// REPEAT( Q ){
// COUT( N );
// }
// ll answer = 0;
// RETURN( answer );
QUIT;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0