結果

問題 No.275 中央値を求めよ
ユーザー 👑 p-adicp-adic
提出日時 2022-08-08 23:05:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 27 ms / 1,000 ms
コード長 35,299 bytes
コンパイル時間 994 ms
コンパイル使用メモリ 78,472 KB
最終ジャッジ日時 2025-01-30 19:32:13
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

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

#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:
// T0
inline VLArray();
template <typename Arg1 , typename... Arg2> inline VLArray( const Arg1& , const Arg2&... );
inline VLArray( const VLArray<T>& );
// T0使
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>;
// *thisconstconst_iteratoriteratorconst
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{};
// backfront使
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{};
// frontback使
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{};
// backfront使
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{};
// frontback使
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0