#786358 (C++17) No.275 中央値を求めよ

提出ソース
結果

問題	No.275 中央値を求めよ
ユーザー	👑 p-adic
提出日時	2022-08-08 23:05:15
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	3 ms / 1,000 ms
コード長	35,299 bytes
コンパイル時間	865 ms
コンパイル使用メモリ	79,216 KB
実行使用メモリ	4,348 KB
最終ジャッジ日時	2023-10-19 11:03:01
合計ジャッジ時間	2,317 ms
ジャッジサーバーID （参考情報）	judge13 / judge15
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	2 ms 4,348 KB
testcase_04	AC	2 ms 4,348 KB
testcase_05	AC	2 ms 4,348 KB
testcase_06	AC	2 ms 4,348 KB
testcase_07	AC	3 ms 4,348 KB
testcase_08	AC	2 ms 4,348 KB
testcase_09	AC	2 ms 4,348 KB
testcase_10	AC	2 ms 4,348 KB
testcase_11	AC	2 ms 4,348 KB
testcase_12	AC	2 ms 4,348 KB
testcase_13	AC	2 ms 4,348 KB
testcase_14	AC	2 ms 4,348 KB
testcase_15	AC	3 ms 4,348 KB
testcase_16	AC	2 ms 4,348 KB
testcase_17	AC	3 ms 4,348 KB
testcase_18	AC	2 ms 4,348 KB
testcase_19	AC	2 ms 4,348 KB
testcase_20	AC	2 ms 4,348 KB
testcase_21	AC	2 ms 4,348 KB
testcase_22	AC	2 ms 4,348 KB
testcase_23	AC	2 ms 4,348 KB
testcase_24	AC	2 ms 4,348 KB
testcase_25	AC	3 ms 4,348 KB
testcase_26	AC	3 ms 4,348 KB
testcase_27	AC	2 ms 4,348 KB
testcase_28	AC	2 ms 4,348 KB
testcase_29	AC	2 ms 4,348 KB
testcase_30	AC	2 ms 4,348 KB
testcase_31	AC	2 ms 4,348 KB
testcase_32	AC	2 ms 4,348 KB
testcase_33	AC	2 ms 4,348 KB
testcase_34	AC	2 ms 4,348 KB
testcase_35	AC	2 ms 4,348 KB
testcase_36	AC	2 ms 4,348 KB
testcase_37	AC	2 ms 4,348 KB
testcase_38	AC	2 ms 4,348 KB
testcase_39	AC	2 ms 4,348 KB
testcase_40	AC	2 ms 4,348 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <iostream>
#include <list>
#include <vector>
#include <string>
#include <stdio.h>
#include <stdint.h>
using namespace std;

using uint = unsigned int;
using ll = long long;

#define CIN( LL , A ) LL A; cin >> A 
#define GETLINE( A ) string A; getline( cin , A ) 

// 自分のライブラリ（https://github.com/p-adic/cpp）よりソースコードをコピーして編集している。
template <typename T> class VLArray;
template <typename T> class IteratorOfVLArray;
template <typename T> class ConstIteratorOfVLArray;

template <typename T>
class EntryOfVLArray
{

  friend VLArray<T>;
  friend IteratorOfVLArray<T>;
  friend ConstIteratorOfVLArray<T>;

private:
  T m_t;
  EntryOfVLArray<T>* m_prev;
  EntryOfVLArray<T>* m_next;
  
private:
  inline EntryOfVLArray();
  template <typename Arg> inline EntryOfVLArray( const Arg& );
  template <typename Arg> inline EntryOfVLArray( const Arg& , EntryOfVLArray<T>* const& , EntryOfVLArray<T>* const& );

};

template <typename T> inline EntryOfVLArray<T>::EntryOfVLArray() : m_t() , m_prev( this ) , m_next( this ) {}
template <typename T> template <typename Arg> inline EntryOfVLArray<T>::EntryOfVLArray( const Arg& t ) : m_t( t ) , m_prev( this ) , m_next( this ) {}
template <typename T> template <typename Arg> inline EntryOfVLArray<T>::EntryOfVLArray( const Arg& t , EntryOfVLArray<T>* const& prev , EntryOfVLArray<T>* const& next ) : m_t( t ) , m_prev( prev ) , m_next( next ) {}

template <typename T> class EntryOfVLArray;
template <typename T> class ConstIteratorOfVLArray;
template <typename T> class VLArray;

template <typename T>
class IteratorOfVLArray
{

  friend ConstIteratorOfVLArray<T>;
  friend VLArray<T>;

private:
  // ++の実装のためにはm_pをポインタへの参照にできない。
  EntryOfVLArray<T>* m_p;
  
public:
  inline IteratorOfVLArray( EntryOfVLArray<T>* const& ) noexcept;
  inline IteratorOfVLArray( const IteratorOfVLArray<T>& ) noexcept;

  // inline T& Access() const;
  inline T& operator*() const;
  inline T* operator->() const;
  IteratorOfVLArray<T>& operator=( const IteratorOfVLArray<T>& ) noexcept;
  inline void operator++( int );
  inline void operator--( int );

};

template <typename T>
class ConstIteratorOfVLArray
{

  friend VLArray<T>;

private:
  const EntryOfVLArray<T>* m_p;
  
public:
  inline ConstIteratorOfVLArray( EntryOfVLArray<T>* const& ) noexcept;
  inline ConstIteratorOfVLArray( const ConstIteratorOfVLArray<T>& ) noexcept;
  inline ConstIteratorOfVLArray( const IteratorOfVLArray<T>& ) noexcept;

  inline const T& operator*() const;
  inline const T* operator->() const;
  ConstIteratorOfVLArray<T>& operator=( const ConstIteratorOfVLArray<T>& ) noexcept;
  ConstIteratorOfVLArray<T>& operator=( const IteratorOfVLArray<T>& ) noexcept;
  inline void operator++( int );
  inline void operator--( int );
  
  static inline bool Equal( const IteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;
  static inline bool Equal( const ConstIteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;
  static inline bool Equal( const IteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;
  static inline bool Equal( const ConstIteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;

};

template <typename T> inline bool operator==( const IteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;
template <typename T> inline bool operator!=( const IteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;

template <typename T> inline bool operator==( const ConstIteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;
template <typename T> inline bool operator!=( const ConstIteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;

template <typename T> inline bool operator==( const IteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;
template <typename T> inline bool operator!=( const IteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;

template <typename T> inline bool operator==( const ConstIteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;
template <typename T> inline bool operator!=( const ConstIteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;

// IteratorOfVLArray
template <typename T> inline IteratorOfVLArray<T>::IteratorOfVLArray( EntryOfVLArray<T>* const& p ) noexcept : m_p( p ) {}
template <typename T> inline IteratorOfVLArray<T>::IteratorOfVLArray( const IteratorOfVLArray<T>& itr ) noexcept : m_p( itr.m_p ) {}

// template <typename T> inline T& IteratorOfVLArray<T>::Access() const { return Access( m_p ).m_t; }
template <typename T> inline T& IteratorOfVLArray<T>::operator*() const { return ( *m_p ).m_t; }
template <typename T> inline T* IteratorOfVLArray<T>::operator->() const { return &( *( *this ) ); }

template <typename T>
IteratorOfVLArray<T>& IteratorOfVLArray<T>::operator=( const IteratorOfVLArray<T>& itr ) noexcept
{

  m_p = itr.m_p;
  return *this;
  
}

template <typename T> inline void IteratorOfVLArray<T>::operator++( int ){ m_p = ( *m_p ).m_next; }
template <typename T> inline void IteratorOfVLArray<T>::operator--( int ){ m_p = ( *m_p ).m_prev; }

// ConstIteratorOfVLArray
template <typename T> inline ConstIteratorOfVLArray<T>::ConstIteratorOfVLArray( EntryOfVLArray<T>* const& p ) noexcept : m_p( p ) {}
template <typename T> inline ConstIteratorOfVLArray<T>::ConstIteratorOfVLArray( const ConstIteratorOfVLArray<T>& itr ) noexcept : m_p( itr.m_p ) {}
template <typename T> inline ConstIteratorOfVLArray<T>::ConstIteratorOfVLArray( const IteratorOfVLArray<T>& itr ) noexcept : m_p( itr.m_p ) {}

template <typename T> inline const T& ConstIteratorOfVLArray<T>::operator*() const { return ( *m_p ).m_t; };
template <typename T> inline const T* ConstIteratorOfVLArray<T>::operator->() const { return &( *( *this ) ); }

template <typename T>
ConstIteratorOfVLArray<T>& ConstIteratorOfVLArray<T>::operator=( const ConstIteratorOfVLArray<T>& itr ) noexcept
{

  m_p = itr.m_p;
  return *this;

}

template <typename T>
ConstIteratorOfVLArray<T>& ConstIteratorOfVLArray<T>::operator=( const IteratorOfVLArray<T>& itr ) noexcept
{

  m_p = itr.m_p;
  return *this;

}

template <typename T> inline void ConstIteratorOfVLArray<T>::operator++( int ) { m_p = ( *m_p ).m_next; }
template <typename T> inline void ConstIteratorOfVLArray<T>::operator--( int ) { m_p = ( *m_p ).m_prev; }

template <typename T> inline bool ConstIteratorOfVLArray<T>::Equal( const IteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { return itr0.m_p == itr1.m_p; }
template <typename T> inline bool ConstIteratorOfVLArray<T>::Equal( const ConstIteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { return itr0.m_p == itr1.m_p; }
template <typename T> inline bool ConstIteratorOfVLArray<T>::Equal( const IteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { return itr0.m_p == itr1.m_p; }
template <typename T> inline bool ConstIteratorOfVLArray<T>::Equal( const ConstIteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { return itr0.m_p == itr1.m_p; }

template <typename T> inline bool operator==( const IteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { return ConstIteratorOfVLArray<T>::Equal( itr0 , itr1 ); }
template <typename T> inline bool operator!=( const IteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { return !( itr0 == itr1 );}

template <typename T> inline bool operator==( const ConstIteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { return ConstIteratorOfVLArray<T>::Equal( itr0 , itr1 ); }
template <typename T> inline bool operator!=( const ConstIteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { return !( itr0 == itr1 );}

template <typename T> inline bool operator==( const IteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { return ConstIteratorOfVLArray<T>::Equal( itr0 , itr1 ); }
template <typename T> inline bool operator!=( const IteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { return !( itr0 == itr1 );}

template <typename T> inline bool operator==( const ConstIteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { return ConstIteratorOfVLArray<T>::Equal( itr0 , itr1 ); }
template <typename T> inline bool operator!=( const ConstIteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { return !( itr0 == itr1 );}

template <typename T>
class SingletonType
{

protected:
  SingletonType() = default;
  SingletonType( const SingletonType& ) = default;
  virtual ~SingletonType() = default;
  SingletonType& operator=( const SingletonType& ) = default;

public:
  static T& GetUniqueObject();
  
};

template <typename T>
class SingletonOf :
  public SingletonType<SingletonOf<T> >
{

  friend SingletonType<SingletonOf<T> >;

private:
  SingletonOf() = default;
  SingletonOf( const SingletonOf& ) = default;
  ~SingletonOf() = default;
  SingletonOf& operator=( const SingletonOf& ) = default;

public:
  using type = T;

};

// Replace TYPE_NAME by a suitable typename.
/*
class TYPE_NAME :
  public SingletonType<TYPE_NAME>
{

  friend SingletonType<TYPE_NAME>;

private:
  TYPE_NAME() = default;
  TYPE_NAME( const TYPE_NAME& ) = default;
  ~TYPE_NAME() = default;
  TYPE_NAME& operator=( const TYPE_NAME& ) = default;

};
*/

template <typename T> T& Object();

#include <typeinfo>

template <typename T>
T& SingletonType<T>::GetUniqueObject()
{

    static T t;
    return t;

}

template <typename T>
T& Object()
{

  // if( ! is_base_of<SingletonType<T>,T>::value ){

  //   ERR_IMPUT( typeid( T ) );
    
  // }

  return T::GetUniqueObject();

}


template <int i>
class WrappedInt :
  public SingletonType<WrappedInt<i> >
{
  
  friend class SingletonType<WrappedInt<i> >;

private:
  WrappedInt() = default;
  WrappedInt( const WrappedInt& ) = default;
  WrappedInt& operator=( const WrappedInt& ) = default;
  static const int m_i;

public:
  static int Get();

};

template <uint i>
class WrappedUInt :
  public SingletonType<WrappedUInt<i> >
{

  friend class SingletonType<WrappedUInt<i> >;

private:
  WrappedUInt() = default;
  WrappedUInt( const WrappedUInt& ) = default;
  WrappedUInt& operator=( const WrappedUInt& ) = default;
  static const uint m_i;

public:
  static uint Get();

};

template <int i> const WrappedInt<i>& Wrap();
template <uint i> const WrappedUInt<i>& WrapU();


template <int i>
const int WrappedInt<i>::m_i = i;

template <uint i>
const uint WrappedUInt<i>::m_i = i;

template <int i>
int WrappedInt<i>::Get()
{

  return m_i;

}

template <uint i>
uint WrappedUInt<i>::Get()
{

  return m_i;

}

template <int i>
const WrappedInt<i>& Wrap()
{

  return Object<WrappedInt<i> >();

}

template <uint i>
const WrappedUInt<i>& WrapU()
{

  return Object<WrappedUInt<i> >();

}


class EmptySet
{

private:
  EmptySet();
  EmptySet( const EmptySet& );
  EmptySet& operator=( const EmptySet& );

};


template <typename T> class VLArray;

template <typename N , typename T> class VLMatrix_Body;

template <typename T>
class VLMatrix_Body<WrappedUInt<1>,T>
{

public:
  using type = VLArray<T>;

};

template <typename T>
class VLMatrix_Body<WrappedUInt<2>,T>
{

public:
  using type = VLArray<typename VLMatrix_Body<WrappedUInt<1>,T>::type>;

};

template <typename T>
class VLMatrix_Body<WrappedUInt<3>,T>
{

public:
  using type = VLArray<typename VLMatrix_Body<WrappedUInt<2>,T>::type>;

};

template <uint N , typename T>
using VLMatrix = typename VLMatrix_Body<WrappedUInt<N>,T>::type;


template <typename T> class IteratorOfVLArray;
template <typename T> class ConstIteratorOfVLArray;
template <typename Arg> class WrappedType;

template <typename T>
class VLArray
{

private:
  EntryOfVLArray<T> m_e;
  EntryOfVLArray<T>* const m_p_e;
  uint m_size;
  
public:
  // Tは引数0のコンストラクタを持つクラスのみ許容。
  inline VLArray();
  template <typename Arg1 , typename... Arg2> inline VLArray( const Arg1& , const Arg2&... );
  inline VLArray( const VLArray<T>& );

  // Tが引数0のコンストラクタを持たないクラスの場合に使用。
  template <typename Arg> inline VLArray( const WrappedType<Arg>& t );
  
  virtual ~VLArray();
  
  VLArray<T>& operator=( const VLArray<T>& );
  
  inline const uint& size() const noexcept;
  inline void clear();
  inline bool empty() const noexcept;
  T& front();
  const T& front() const;
  T& back();
  const T& back() const;
  
  template <typename Arg> void push_back( const Arg& );
  template <typename... Args> void push_back( const Args&... );
  template <typename Arg> void push_front( const Arg& );
  // 前から順にpush_frontする。
  template <typename... Args> void push_front( const Args&... );
  void pop_back();
  void pop_front();

  template <typename... Args> inline void Concatenate( const Args&... );
  template <typename Arg> void Concatenate_back( const Arg& );
  template <typename... Args> void Concatenate_back( const Args&... );
  template <typename Arg> void Concatenate_front( const Arg& );
  // 前から順にConcatenate_frontする。
  template <typename... Args> void Concatenate_front( const Args&... );

  using iterator = IteratorOfVLArray<T>;
  using const_iterator = ConstIteratorOfVLArray<T>;

  // *thisがconstである場合に確実にconst_iterator返しをするために、iterator返しは非constにする必要がある。
  inline iterator begin() noexcept;
  inline const_iterator begin() const noexcept;
  inline iterator end() noexcept;
  inline const_iterator end() const noexcept;
  template <typename Arg> void insert( const iterator& , const Arg& );
  template <typename Arg> void insert_front( const iterator& , const Arg& );
  template <typename Arg> void insert_back( const iterator& , const Arg& );
  iterator erase( iterator& );
  iterator erase_back( iterator& );
  iterator erase_front( iterator& );

  T& operator[]( const uint& );
  const T& operator[]( const uint& ) const;
  VLArray<T> GetInitialSegment( const int& ) const;
  VLArray<T> GetFinalSegment( const int& ) const;

  bool CheckContain( const iterator& ) const noexcept;
  bool CheckContain( const const_iterator& ) const noexcept;

  string Display() const;

private:
  template <typename Arg> inline int push_back_int( const Arg& );
  template <typename Arg> inline int push_front_int( const Arg& );
  template <typename Arg> inline int Concatenate_back_int( const Arg& );
  template <typename Arg> inline int Concatenate_front_int( const Arg& );

  template <typename... Args> static inline void ExpandParameterPack( const Args&... ) noexcept;

};


template <typename T> bool operator==( const VLArray<T>& , const VLArray<T>& );
template <typename T> inline bool operator!=( const VLArray<T>& , const VLArray<T>& );

template <typename T> VLArray<T> to_VLArray( const uint& , const T& );
template <typename T> inline VLMatrix<1,T> to_VLMatrix( const uint& , const T& );
template <typename T> inline VLMatrix<2,T> to_VLMatrix( const uint& , const uint& , const T& );
template <typename T> inline VLMatrix<3,T> to_VLMatrix( const uint& , const uint& , const uint& , const T& );

template <typename T , typename... Arg> VLArray<T> Frown( const Arg&... );
template <typename T> T Sum( const VLArray<T>& );


template <typename Arg>
class WrappedType
{

private:
  Arg m_t;

public:
  template <typename... ARGS> inline WrappedType( const ARGS&... args );
  inline void Set( const Arg& t );
  inline const Arg& Get() const noexcept;

};

template <typename... Types>
class WrappedTypes
{};

template <typename Arg> template <typename... ARGS> inline WrappedType<Arg>::WrappedType( const ARGS&... args ) : m_t( args... ) {}

template <typename Arg> inline void WrappedType<Arg>::Set( const Arg& t ){ m_t = t; }
template <typename Arg> inline const Arg& WrappedType<Arg>::Get() const noexcept { return m_t; }

template <typename T> inline VLArray<T>::VLArray() : m_e() , m_p_e( &m_e ) , m_size( 0 ) {}
template <typename T> template <typename Arg1 , typename... Arg2> inline VLArray<T>::VLArray( const Arg1& t0 , const Arg2&... t1 ) : VLArray() { push_back( t0 , t1... ); }
template <typename T> inline VLArray<T>::VLArray( const VLArray<T>& a ) : m_e( a.m_e.m_t ) , m_p_e( &m_e ) , m_size( 0 ) { Concatenate( a ); }
template <typename T> template <typename Arg> inline VLArray<T>::VLArray( const WrappedType<Arg>& t ) : m_e( t.Get() ) , m_p_e( &m_e ) , m_size( 0 ) {}

template <typename T> VLArray<T>::~VLArray() { clear(); }

template <typename T>
VLArray<T>& VLArray<T>::operator=( const VLArray<T>& a )
{

  if( this != &a ){
    
    clear();
    Concatenate( a );
  
  }

  return *this;

}

template <typename T> inline const uint& VLArray<T>::size() const noexcept { return m_size; }
template <typename T> inline void VLArray<T>::clear(){ while( m_size > 0 ) pop_back(); }
template <typename T> inline bool VLArray<T>::empty() const noexcept { return m_size == 0; }

template <typename T>
T& VLArray<T>::front()
{

  // if( m_size == 0 ){

  //   ERR_CALL;
    
  // }
  
  return m_e.m_next->m_t;

}

template <typename T>
const T& VLArray<T>::front() const
{

  // if( m_size == 0 ){

  //   ERR_CALL;
    
  // }

  return m_e.m_next->m_t;

}

template <typename T>
T& VLArray<T>::back()
{

  // if( m_size == 0 ){

  //   ERR_CALL;
    
  // }

  return m_e.m_prev->m_t;

}

template <typename T>
const T& VLArray<T>::back() const
{

  // if( m_size == 0 ){

  //   ERR_CALL;
    
  // }

  return m_e.m_prev->m_t;

}

template <typename T> template <typename Arg>
void VLArray<T>::push_back( const Arg& t )
{
  
  EntryOfVLArray<T>* p_e_prev = m_e.m_prev;
  auto p = new EntryOfVLArray<T>( t , p_e_prev , m_p_e );
    
  m_e.m_prev = p;
  p_e_prev->m_next = p;
  
  m_size++;
  return;

}


template <typename T> template <typename... Args>
void VLArray<T>::push_back( const Args&... args )
{

  VLArray<T> copy{};

  // 関数の処理は後ろからなのでbackではなくfrontを使う。
  ExpandParameterPack( copy.push_front_int( args )... );
  Concatenate_back( copy );
  return;
  
}

template <typename T> template <typename Arg> inline int VLArray<T>::push_back_int( const Arg& t ) { push_back( t ); return 0; }

template <typename T> template <typename Arg>
void VLArray<T>::push_front( const Arg& t )
{

  EntryOfVLArray<T>* p_b = m_e.m_next;
  auto p = new EntryOfVLArray<T>( t , m_p_e , p_b );
    
  p_b->m_prev = p;
  m_e.m_next = p;
  
  m_size++;
  return;

}

template <typename T> template <typename... Args>
void VLArray<T>::push_front( const Args&... args )
{

  VLArray<T> copy{};

  // 関数の処理は後ろからなのでfrontではなくbackを使う。
  ExpandParameterPack( copy.push_back_int( args )... );
  Concatenate_front( copy );
  return;

}

template <typename T> template <typename Arg> inline int VLArray<T>::push_front_int( const Arg& t ) { push_front( t ); return 0; }

template <typename T>
void VLArray<T>::pop_back()
{

  // if( m_size == 0 ){

  //   ERR_CALL;
    
  // }
  
  EntryOfVLArray<T>* p_e_prev = m_e.m_prev;
  EntryOfVLArray<T>* p_e_prev_prev = p_e_prev->m_prev;

  m_e.m_prev = p_e_prev_prev;
  p_e_prev_prev->m_next = m_p_e;
  
  delete p_e_prev;
  m_size--;
  return;
  
}

template <typename T>
void VLArray<T>::pop_front()
{

  // if( m_size == 0 ){

  //   ERR_CALL;
    
  // }

  EntryOfVLArray<T>* p_b = m_e.m_next;
  EntryOfVLArray<T>* p_b_next = ( *p_b ).m_next;

  p_b_next->m_prev = m_p_e;
  m_e.m_next = p_b_next;
  
  delete p_b;  
  m_size--;
  return;
  
}

template <typename T> template <typename... Args> inline void VLArray<T>::Concatenate( const Args&... args ) { Concatenate_back( args... ); }

template <typename T> template <typename Arg>
void VLArray<T>::Concatenate_back( const Arg& a )
{
  
  const EntryOfVLArray<T>* p = a.m_p_e;
  const uint& N = a.m_size;
    
  for( uint n = 0 ; n < N ; n++ ){

    p = p->m_next;
    push_back( p->m_t );

  }

  return;

}

template <typename T> template <typename... Args>
void VLArray<T>::Concatenate_back( const Args&... args )
{

  VLArray<T> copy{};

  // 関数の処理は後ろからなのでbackではなくfrontを使う。
  ExpandParameterPack( copy.Concatenate_front_int( args )... );
  Concatenate_back( copy );
  return;

}

template <typename T> template <typename Arg> inline int VLArray<T>::Concatenate_back_int( const Arg& a ) { Concatenate( a ); return 0; }

template <typename T> template <typename Arg>
void VLArray<T>::Concatenate_front( const Arg& a )
{
  
  const EntryOfVLArray<T>* p = a.m_p_e;
  const uint& N = a.m_size;
    
  for( uint n = 0 ; n < N ; n++ ){

    p = p->m_prev;
    push_front( p->m_t );

  }

  return;

}

template <typename T> template <typename... Args>
void VLArray<T>::Concatenate_front( const Args&... args )
{

  VLArray<T> copy{};

  // 関数の処理は後ろからなのでfrontではなくbackを使う。
  ExpandParameterPack( copy.Concatenate_back_int( args )... );
  Concatenate_front( copy );
  return;

}

template <typename T> template <typename Arg> inline int VLArray<T>::Concatenate_front_int( const Arg& a ) { Concatenate_front( a ); return 0; }


template <typename T> inline typename VLArray<T>::iterator VLArray<T>::begin() noexcept { return IteratorOfVLArray<T>( m_e.m_next ); }
template <typename T> inline typename VLArray<T>::const_iterator VLArray<T>::begin() const noexcept { return ConstIteratorOfVLArray<T>( m_e.m_next ); }
template <typename T> inline typename VLArray<T>::iterator VLArray<T>::end() noexcept { return IteratorOfVLArray<T>( m_p_e ); }
template <typename T> inline typename VLArray<T>::const_iterator VLArray<T>::end() const noexcept { return ConstIteratorOfVLArray<T>( m_p_e ); }

template <typename T> template <typename Arg> inline void VLArray<T>::insert( const typename VLArray<T>::iterator& itr , const Arg& t ) { insert_back( itr , t ); }

template <typename T> template <typename Arg>
void VLArray<T>::insert_front( const typename VLArray<T>::iterator& itr , const Arg& t )
{

  // if( ! CheckContain( itr ) ){

  //   ERR_IMPUT( itr , t );
    
  // }

  if( itr == begin() ){

    push_front( t );

  } else {

    EntryOfVLArray<T>* p1 = itr.m_p;
    EntryOfVLArray<T>* p0 = p1->m_prev;
    auto p = new EntryOfVLArray<T>( t , p0 , p1 );
  
    p0->m_next = p;
    p1->m_prev = p;
  
    m_size++;

  }
  
  return;

}

template <typename T> template <typename Arg>
void VLArray<T>::insert_back( const typename VLArray<T>::iterator& itr , const Arg& t )
{

  // if( ! CheckContain( itr ) ){

  //   ERR_IMPUT( itr , t );
    
  // }
  
  EntryOfVLArray<T>* p0 = itr.m_p;
  EntryOfVLArray<T>* p1 = p0->m_next;
  auto p = new EntryOfVLArray<T>( t , p0 , p1 );
  
  p1->m_prev = p;
  p0->m_next = p;
  
  m_size++;
  return;

}

template <typename T> inline typename VLArray<T>::iterator VLArray<T>::erase( typename VLArray<T>::iterator& itr ) { return erase_back( itr ); }

template <typename T>
typename VLArray<T>::iterator VLArray<T>::erase_back( typename VLArray<T>::iterator& itr )
{
  
  // if( ! CheckContain( itr ) ){

  //   ERR_IMPUT( itr );
    
  // }

  EntryOfVLArray<T>* p = itr.m_p;
  EntryOfVLArray<T>* p0 = p->m_prev;
  EntryOfVLArray<T>* p1 = p->m_next;
  
  p0->m_next = p1;
  p1->m_prev = p0;
  itr++;
  
  delete p;
  m_size--;
  return itr;

}

template <typename T>
typename VLArray<T>::iterator VLArray<T>::erase_front( typename VLArray<T>::iterator& itr )
{
  
  // if( ! CheckContain( itr ) ){

  //   ERR_IMPUT( itr );
    
  // }

  EntryOfVLArray<T>* p = itr.m_p;
  EntryOfVLArray<T>* p0 = p->m_prev;
  EntryOfVLArray<T>* p1 = p->m_next;
  
  p0->m_next = p1;
  p1->m_prev = p0;
  itr--;
  
  delete p;
  m_size--;
  return itr;

}

template <typename T>
T& VLArray<T>::operator[]( const uint& i )
{

  // if( i >= m_size ){

  //   ERR_IMPUT( i );

  // }

  if( i < m_size / 2 ){

    EntryOfVLArray<T>* p = m_e.m_next;

    for( uint n = 0 ; n < i ; n++ ){

      p = p->m_next;

    }

    return p->m_t;

  }

  EntryOfVLArray<T>* p = m_e.m_prev;

  for( uint n = m_size - 1 ; n > i ; n-- ){

    p = p->m_prev;

  }

  return p->m_t;

}

template <typename T>
const T& VLArray<T>::operator[]( const uint& i ) const
{

  // if( i >= m_size ){

  //   ERR_IMPUT( i );

  // }

  if( i < m_size / 2 ){

    EntryOfVLArray<T>* p = m_e.m_next;

    for( uint n = 0 ; n < i ; n++ ){

      p = p->m_next;

    }

    return p->m_t;

  }

  EntryOfVLArray<T>* p = m_e.m_prev;

  for( uint n = m_size - 1 ; n > i ; n-- ){

    p = p->m_prev;

  }

  return p->m_t;

}

template <typename T>
VLArray<T> VLArray<T>::GetInitialSegment( const int& n ) const
{

  const int N = (int)m_size;
  int M;

  if( N <= n ){

    M = N;

  } else {
    
    if( 0 <= n ){

      M = n;
      
    } else {

      M = N + n;

    }

  }

  VLArray<T> b{};
  const_iterator itr = begin();

  for( int m = 1 ; m <= M ; m++ ){

    b.push_back( *itr );
    itr++;

  }

  return b;

}

template <typename T>
VLArray<T> VLArray<T>::GetFinalSegment( const int& n ) const
{

  const int N = (int)m_size;
  int M;

  if( N <= n ){

    M = N;

  } else {
    
    if( 0 <= n ){

      M = n;
      
    } else {

      M = N + n;

    }
  
  }

  VLArray<T> b{};
  const_iterator itr = end();

  for( int m = 1 ; m <= M ; m++ ){

    itr--;
    b.push_front( *itr );

  }

  return b;

}

template <typename T>
bool VLArray<T>::CheckContain( const iterator& itr ) const noexcept
{

  for( auto itr_b = begin() , itr_e = end() ; itr_b != itr_e ; itr_b++ ){

    if( itr == itr_b ){

      return true;

    }
    
  }

  return false;

}

template <typename T>
bool VLArray<T>::CheckContain( const const_iterator& itr ) const noexcept
{

  for( auto itr_b = begin() , itr_e = end() ; itr_b != itr_e ; itr_b++ ){

    if( itr == itr_b ){

      return true;

    }
    
  }

  return false;

}

template <typename T>
string VLArray<T>::Display() const
{

  string s = "(";
  EntryOfVLArray<T>* p = m_p_e;
  
  for( uint n = 0 ; n < m_size ; n++ ){

    p = p->m_next;
    
    if( n > 0 ){

      s += ",";

    }
    
    s += to_string( p->m_t );

  }

  s += ")";

  return s;

}

template <typename T> template <typename... Args> inline void VLArray<T>::ExpandParameterPack( const Args&... ) noexcept {};

template <typename T>
bool operator==( const VLArray<T>& a1 , const VLArray<T>& a2 )
{

  auto itr1 = a1.begin();
  auto end1 = a1.end();
  auto itr2 = a2.begin();
  auto end2 = a2.end();

  while( itr1 != end1 && itr2 != end2 ){

    if( *itr1 != *itr2 ){

      return false;

    }

    itr1++;
    itr2++;

  }

  return ( itr1 == end1 ) && ( itr2 == end2 );

}

template <typename T> inline bool operator!=( const VLArray<T>& a1 , const VLArray<T>& a2 ) { return !( a1 == a2 ); }


template <typename T> VLArray<T> to_VLArray( const uint& N , const T& t )
{

  auto a = VLArray<T>();

  for( uint n = 0 ; n < N ; n++ ){

    a.push_back( t );

  }

  return a;
  
}

template <typename T> inline VLMatrix<1,T> to_VLMatrix( const uint& N , const T& t ){ return to_VLArray( N , t ); }

template <typename T> inline VLMatrix<2,T> to_VLMatrix( const uint& N0 , const uint& N1 , const T& t ){ return to_VLArray( N1 , to_VLArray( N0 , t ) ); }

template <typename T> inline VLMatrix<3,T> to_VLMatrix( const uint& N0 , const uint& N1 , const uint& N2 , const T& t){ return to_VLArray( N2 , to_VLMatrix( N0 , N1 , t ) ); }

template <typename T , typename... Arg>
VLArray<T> Frown( const Arg&... args )
{

  VLArray<T> a{};
  a.Concatenate( args... );
  return a;

}

template <typename T> T Sum( const VLArray<T>& a )
{
  
  T t{};
  for( auto itr = a.begin() , end = a.end() ; itr != end ; itr++ ){

    t += *itr;

  }

  return t;

}

template <typename T>
void Sort( VLArray<T>& a , const string& method = "normal" , const VLArray<int>& option = VLArray<int>() );


template <typename T>
void NormalSort( VLArray<T>& a , const VLArray<int>& option = VLArray<int>() );

template <typename T>
void NormalSortNoCut( VLArray<T>& a );

template <typename T>
void NormalSortCut( VLArray<T>& a , const uint& cut_length , const bool& cut_large );


template <typename T>
void MergeSort( VLArray<T>& a , const VLArray<int>& option = VLArray<int>() );

template <typename T>
void MergeSortNoCut( VLArray<T>& a );

template <typename T>
void MergeSortCut( VLArray<T>& a , const uint& cut_length , const bool& cut_large , const uint& normal_method_length = 2 );


template <typename T>
void Sort( VLArray<T>& a , const string& method , const VLArray<int>& option )
{

  if( method == "merge" ){

    MergeSort( a , option );

  } else {

    NormalSort( a , option );

  }

  return;
  
}

template <typename T>
void NormalSort( VLArray<T>& a , const VLArray<int>& option )
{

  if( ! option.empty() ){

    const uint& cut_length_signed = option[0];

    if( cut_length_signed != 0 ){

      if( cut_length_signed > 0 ){

	NormalSortCut<T>( a , (uint)cut_length_signed , true );

      } else {

	NormalSortCut<T>( a , (uint)( - cut_length_signed ) , false );

      }

      return;

    }

  }

  NormalSortNoCut<T>( a );
  return;

}

template <typename T>
void NormalSortNoCut( VLArray<T>& a )
{

  auto itr0 = a.begin() , end0 = a.end();

  while( itr0 != end0 ){

    const T& t = *itr0;
    auto itr1 = itr0;
    itr1--;
    auto itr_ins = end0;
    bool changing = false;
    
    while( itr1 != end0 ){

      if( *itr1 > t ){

	if( ! changing ){

	  changing = true;

	}
	
	itr1--;

      } else {

	if( changing ){

	  itr_ins = itr1;

	}

	itr1 = end0;

      }

    }

    if( changing ){

      a.insert_back( itr_ins , t );
      a.erase_back( itr0 );

    } else {
	
      itr0++;

    }

  }

  return;

}

template <typename T>
void NormalSortCut( VLArray<T>& a , const uint& cut_length , const bool& cut_large )
{

  using type = typename VLArray<T>::iterator;
  using incr_type = void( type::* )( int );
  using ins_type = void( VLArray<T>::* )( const type& , const T& );
  using er_type = type( VLArray<T>::* )( type& );
  
  uint length = 0;
  type itr0 = a.end() , end0 = itr0;
  incr_type incr;
  incr_type decr;
  ins_type ins;
  er_type er;

  if( cut_large ){

    itr0 = a.begin();
    incr = &type::operator++;
    decr = &type::operator--;
    ins = &VLArray<T>::insert_back;
    er = &VLArray<T>::erase_back;

  } else {

    itr0--;
    incr = &type::operator--;
    decr = &type::operator++;
    ins = &VLArray<T>::insert_front;
    er = &VLArray<T>::erase_front;

  }

  while( itr0 != end0 ){

    const T& t = *itr0;
    auto itr1 = itr0;
    ( itr1.*decr )( 0 );
    auto itr_ins = end0;
    bool changing = false;
    
    while( itr1 != end0 ){
      
      if( *itr1 > t ){

	if( ! changing ){

	  changing = true;

	}
	
	( itr1.*decr )( 0 );

      } else {

	if( changing ){

	  itr_ins = itr1;

	}

	itr1 = end0;

      }

    }

    if( changing ){

      ( a.*ins )( itr_ins , t );
      ( a.*er )( itr0 );

      if( length < cut_length ){

	length++;

      } else {

	auto itr2 = itr0;
	( itr2.*decr )( 0 );
	( a.*er )( itr2 );

      }

    } else {

      ( itr0.*incr )( 0 );

    }

  }

  return;

}

template <typename T>
void MergeSort( VLArray<T>& a , const VLArray<int>& option )
{

  const uint& size = option.size();
  
  if( size > 0 ){

    const uint& cut_length_signed = option[0];

    if( cut_length_signed != 0 ){

      uint cut_length;
      bool cut_large;

      if( cut_length_signed > 0 ){

	cut_length = (uint)cut_length_signed;
	cut_large = true;

      } else {

	cut_length = (uint)( - cut_length_signed );
	cut_large = false;

      }

      if( size > 1 ){

	const int& normal_method_length = option[1];

	if( normal_method_length > 0 ){

	  MergeSortCut<T>( a , cut_length , cut_large , (uint)( normal_method_length ) );
	  return;
	}

      }
      
      MergeSortCut<T>( a , cut_length , cut_large );
      return;

    }

  }

  MergeSortNoCut<T>( a );
  return;

}

template <typename T>
void MergeSortNoCut( VLArray<T>& a )
{

  const uint& size_a = a.size();

  if( size_a <= 2 ){

    NormalSortNoCut( a );
    return;

  }
  
  const uint half_size_a = size_a / 2;

  auto itr = a.begin();
  VLArray<T> b{};
  
  for( uint i = 0 ; i < half_size_a ; i++ ){

    b.push_back( *itr );
    a.erase( itr );

  }

  MergeSortNoCut<T>( a );
  MergeSortNoCut<T>( b );

  itr = a.begin();
  auto end = a.end();
  const uint& size_b = b.size();

  while( size_b != 0 ){

    const T& t = b.front();
    bool not_inserted = true;
    
    while( itr != end && not_inserted ){

      if( t < *itr ){

	a.insert_front( itr , t );
	not_inserted = false;

      } else {

	itr++;

      }

    }

    if( not_inserted ){

      a.push_back( t );

    }

    b.pop_front();

  }

  return;

}

template <typename T>
void MergeSortCut( VLArray<T>& a , const uint& cut_length , const bool& cut_large , const uint& normal_method_length )
{

  const uint& size_a = a.size();

  if( size_a <= normal_method_length ){

    if( size_a <= cut_length ){

      NormalSortNoCut<T>( a );

    } else {

      NormalSortCut<T>( a , cut_length , cut_large );

    }

    return;

  }
  
  const uint half_size_a = size_a / 2;

  using type = typename VLArray<T>::iterator;
  type itr = a.begin();
  VLArray<T> b{};
  
  for( uint i = 0 ; i < half_size_a ; i++ ){

    b.push_back( *itr );
    a.erase( itr );

  }

  MergeSortCut<T>( a , cut_length , cut_large , normal_method_length );
  MergeSortCut<T>( b , cut_length , cut_large , normal_method_length  );

  uint i = 0;
  type end = a.end();
  const uint& size_b = b.size();

  using incr_type = void( type::* )( int );
  using front_type = const T&( VLArray<T>::* )() const;
  using ins_type = void( VLArray<T>::* )( const type& , const T& );
  using push_type = void( VLArray<T>::* )( const T& );
  using pop_type = void( VLArray<T>::* )();
  
  incr_type incr;
  front_type fr;
  ins_type ins;
  push_type push;
  pop_type pop_fr;
  pop_type pop_ba;

  if( cut_large ){

    itr = a.begin();
    fr = &VLArray<T>::front;
    incr = &type::operator++;
    ins = &VLArray<T>::insert_front;
    push = &VLArray<T>::push_back;
    pop_fr = &VLArray<T>::pop_front;
    pop_ba = &VLArray<T>::pop_back;

  } else {

    itr = end;
    itr--;
    fr = &VLArray<T>::back;
    incr = &type::operator--;
    ins = &VLArray<T>::insert_back;
    push = &VLArray<T>::push_front;
    pop_fr = &VLArray<T>::pop_back;
    pop_ba = &VLArray<T>::pop_front;

  }

  while( size_b != 0 && i <= cut_length ){

    const T& t = ( b.*fr )();
    bool not_inserted = true;
    
    while( itr != end && not_inserted ){

      if( t < *itr ){

	( a.*ins )( itr , t );
	not_inserted = false;

      } else {

	( itr.*incr )( 0 );

      }

      i++;
      
    }

    if( not_inserted ){

      ( a.*push )( t );

    }

    ( b.*pop_fr )();

  }

  while( size_a > cut_length ){

    ( a.*pop_ba )();

  }

  return;

}

int main()
{

  CIN( ll , N );
  ll a;
  VLArray<ll> A{};

  for( ll i = 0 ; i < N ; i++ ){

    cin >> a;
    A.push_back( a );

  }

  Sort( A , "merge" );
  double answer;
  if( N % 2 == 0 ){

    answer = ( A[ N / 2 - 1] + A[ N / 2 ] ) / 2.0;

  } else {

    answer = A[ N / 2 ];

  }

  cout << answer << endl;
  return 0;

}
yukicoder

結果

テストケース

ソースコード
