結果
| 問題 | No.3091 Empty |
| ユーザー |
 taiton_k
|
| 提出日時 | 2022-04-01 22:00:24 |
| 言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 23,537 bytes |
| コンパイル時間 | 8,401 ms |
| コンパイル使用メモリ | 211,884 KB |
| 実行使用メモリ | 6,816 KB |
| 最終ジャッジ日時 | 2024-04-30 14:00:26 |
| 合計ジャッジ時間 | 7,762 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
ソースコード
// メイン部分(salve関数)は一番下
// 最適化
#ifndef LOCAL
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2")
#endif
//
//# Includes ####################################################################
#include <bits/stdc++.h>
#include <unistd.h>
#define USE_ACL
#ifdef USE_ACL
#include <atcoder/all>
#endif
#define USE_BOOST
#ifdef USE_BOOST
//#define USE_BOOST_GRAPH
//#define USE_BOOST_MULTIPRECISION
//#define USE_BOOST_GEOMETRY
#endif
//# Main function ###############################################################
void salve(void);
int main(void){
salve();
return 0;
}
namespace taiton {
//# Type traits #################################################################
using swallow = std::initializer_list<bool>;
template<bool B>using enabler = std::enable_if_t<B,std::nullptr_t>;
template<class T>
struct is_container {
template<class U>static constexpr auto check(U&&) -> decltype(std::begin(std::declval<U>()),std::true_type{});
static constexpr auto check(...) -> std::false_type;
static constexpr bool value = decltype(check(std::declval<T>()))::value;
};
template<class T>constexpr bool is_container_v = is_container<T>::value;
template<class T>
struct is_multi_dimensional_container {
template<class U>static constexpr auto check(U&&) -> decltype(std::begin(std::declval<typename U::value_type>()),std::true_type{});
static constexpr auto check(...) -> std::false_type;
static constexpr bool value = decltype(check(std::declval<T>()))::value;
};
template<class T>constexpr bool is_multi_dimensional_container_v = is_multi_dimensional_container<T>::value;
template<class T>using is_one_dimensional_container = std::conjunction<is_container<T>,std::negation<is_multi_dimensional_container<T>>>;
template<class T>constexpr bool is_one_dimensional_container_v = is_one_dimensional_container<T>::value;
template<class T>
struct has_emplace_back {
template<class U>static constexpr auto check(U&& a) -> decltype(a.emplace_back(),std::true_type{});
static constexpr auto check(...) -> std::false_type;
static constexpr bool value = decltype(check(std::declval<T>()))::value;
};
template<class T>constexpr bool has_emplace_back_v = has_emplace_back<T>::value;
template<class T>
struct has_emplace {
template<class U>static constexpr auto check(U&& a) -> decltype(a.emplace(),std::true_type{});
static constexpr auto check(...) -> std::false_type;
static constexpr bool value = decltype(check(std::declval<T>()))::value;
};
template<class T>constexpr bool has_emplace_v = has_emplace<T>::value;
//# Input Utility ###############################################################
template<size_t BufferSize>
class FastInput {
public:
template<typename ...Args>
inline void operator () (Args& ...args) noexcept {
static_cast<void>(swallow{(input(args),false)...});
}
inline void update() noexcept {
read_buf();
}
private:
inline void read_char(char& c) noexcept {
if(counter_ == readsize_){
read_buf();
}
c = buffer_[counter_];
++counter_;
}
inline void read_buf() noexcept {
readsize_ = read(0,buffer_,BufferSize);
counter_ = 0;
}
inline void input(std::string& s) noexcept {
char c;
read_char(c);
while(c == ' ' or c == '\n'){
read_char(c);
}while(!(c == ' ' or c == '\n')){
s += c;
read_char(c);
}
}
inline void input(char& c) noexcept {
read_char(c);
while(c == ' ' or c == '\n'){
read_char(c);
}
}
template<typename T,size_t N>
inline void input(std::array<T,N>& a) noexcept {
for(auto&& i : a){
input(i);
}
}
template<typename T,typename U>
inline void input(std::pair<T,U>& p) noexcept {
input(p.first);
input(p.second);
}
template<typename T>
inline void input(T& a) noexcept {
if constexpr (std::is_integral_v<T>) {
a = 0;
char c;
bool minus = false;
do{
read_char(c);
}while(c < '0' and '9' < c and
c != '-' and
c !='+');
if(c == '-'){
minus = true;
}else{
a += c-'0';
}
read_char(c);
while('0' <= c and c <= '9'){
a *= 10;
a += c-'0';
read_char(c);
}
if(minus){
a *= -1;
}
}else if constexpr (is_container_v<T>) {
for(auto&& i : a){
input(i);
}
}else{
std::string s;
input(s);
std::istringstream iss(s);
iss >> a;
}
}
static inline char buffer_[BufferSize];
size_t readsize_ = 0;
size_t counter_ = 0;
};
inline FastInput<1024*1024> input;
//# Output Utility ##############################################################
class FastOutput {
public:
virtual void write_char(char) noexcept = 0;
virtual void write_chars(const char*,size_t) noexcept = 0;
inline void output(const char c) noexcept {
write_char(c);
}
inline virtual void output(const char* s) noexcept {
while(*s != '\0'){
write_char(*s);
++s;
}
}
inline void output(const std::string& s) noexcept {
write_chars(s.c_str(),s.size());
}
template<typename T,typename U>
inline void output(const std::pair<T,U>& p) noexcept {
output(p.first);
output(' ');
output(p.second);
}
template<typename T,size_t N>
inline void output(std::array<T,N>& a) noexcept {
for(auto&& i : a){
output(i);
}
}
#ifdef USE_ACL
template<int M>
void output(atcoder::static_modint<M> x) noexcept {
output(x.val());
}
#endif
template<typename T>
inline void output(const T& a) noexcept {
if constexpr (std::is_integral_v<T>) {
T x = a;
if(x == 0){
write_char('0');
}else{
if(x < 0){
write_char('-');
x = -x;
}
static char num[19];
int i;
for(i=0;x!=0;++i){
num[i] = '0' + x % 10;
x /= 10;
}
for(;i>0;--i){
write_char(num[i-1]);
}
}
}else if constexpr (std::is_floating_point_v<T>) {
std::ostringstream oss;
oss << std::fixed << std::setprecision(12) << a;
output(oss.str());
}else if constexpr (is_one_dimensional_container_v<T>) {
for(auto&& i : a){
output(i);
output(' ');
}
output('\n');
}else if constexpr (is_multi_dimensional_container_v<T>) {
for(auto& i : a){
for(auto&& j : i){
output(j);
output(' ');
}
output('\n');
}
}else{
std::ostringstream oss;
oss << a;
output(oss.str());
}
}
};
template<size_t BufferSize>
class FastStdOut : private FastOutput {
public:
inline ~FastStdOut() noexcept {
flush();
}
template<typename... Args>
inline void operator () (const Args&... args) noexcept {
static_cast<void>(swallow{(output(args),false)...});
}
inline void flush() noexcept {
ssize_t state = write(1,buffer_,counter_);
if(state == -1){
// Todo : print error state;
exit(errno);
}
counter_ = 0;
}
private:
inline void write_char(char c) noexcept override {
if(counter_ == BufferSize){
flush();
}
buffer_[counter_] = c;
++counter_;
}
inline void write_chars(const char *c,size_t s) noexcept override {
if(s != 0){
if(counter_ + s >= BufferSize){
//memcpy(buffer_+counter_,c,BufferSize-counter_);
flush();
//s -= BufferSize-counter_;
}
memcpy(buffer_+counter_,c,s);
counter_ += s;
}
}
static inline char buffer_[BufferSize];
size_t counter_;
};
inline FastStdOut<1024*1024> print;
//# Debug print ##################################################################
#ifdef LOCAL
class FastStdErr : private FastOutput {
public:
template<typename ...Args>
inline void operator () (const Args& ...args) noexcept {
output("\e[1m\e[33m");
static_cast<void>(swallow{(output(args),false)...});
output("\e[0m");
}
private:
inline void write_char(char c) noexcept override {
ssize_t state;
state = write(2,&c,1);
if(state == -1){
std::exit(errno);
}
}
inline void write_chars(const char *s,size_t len) noexcept override {
if(s != 0){
ssize_t state = write(2,s,len);
if(state == -1){
std::exit(errno);
}
}
}
};
inline FastStdErr debug;
#else
inline void debug(...) noexcept {}
#endif
//# Utilities ####################################################################
#ifdef USE_ACL
template<int M,int O>
constexpr inline bool operator < (const atcoder::static_modint<M>& a,const atcoder::static_modint<O>& b) noexcept {
return a.val() < b.val();
}
template<int M,int O>
constexpr inline bool operator > (const atcoder::static_modint<M>& a,const atcoder::static_modint<O>& b) noexcept {
return a.val() > b.val();
}
template<int M,int O>
constexpr inline bool operator <= (const atcoder::static_modint<M>& a,const atcoder::static_modint<O>& b) noexcept {
return a.val() <= b.val();
}
template<int M,int O>
constexpr inline bool operator >= (const atcoder::static_modint<M>& a,const atcoder::static_modint<O>& b) noexcept {
return a.val() >= b.val();
}
#endif
template<typename T>
constexpr inline int ilog10(T x) noexcept {
int res = 0;
while(x >= 10){
x /= 10;
++res;
}
return res;
}
constexpr inline int64_t ipow(int64_t x,int64_t y) noexcept {
int64_t res=1;
while(y!=0){
if(y % 2 == 1){
res *= x;
}
y /= 2;
x *= x;
}
return res;
}
template<typename T>
constexpr inline int64_t sum(T a) noexcept {
return a*(a+1)/2;
}
template<typename T>
constexpr inline int64_t sum(T a,T b) noexcept {
int64_t res = sum(b)-sum(a-1);
if(res >= 0){
return res;
}else{
return -res;
}
}
template<int M = 1000000007>
constexpr inline int mod_sum(int64_t a) noexcept {
return ((a % M) * ((a+1) % M) / 2) % M;
}
template<int M = 1000000007>
constexpr inline int mod_sum(int64_t a,int64_t b) noexcept {
if(a > b){
std::swap(a,b);
}
int res = mod_sum<M>(b) - mod_sum<M>(a-1);
return res;
}
template<typename T>
constexpr inline double rad2deg(const T& rad) noexcept {
return rad * (180.0 / M_PIl);
}
template<typename T>
constexpr inline double deg2rad(const T& deg) noexcept {
return deg / (180.0 / M_PIl);
}
template<typename T,typename U>
constexpr inline bool chmax(T& a,const U& b) noexcept {
if(a < b){
a = b;
return true;
}else{
return false;
}
}
template<typename T>
constexpr inline bool chmin(T& a,const T& b) noexcept {
if(a > b){
a = b;
return true;
}else{
return false;
}
}
template<typename To,typename From>
constexpr inline To cast(From&& a) noexcept {
return static_cast<To>(a);
}
[[noreturn]] inline void yes() noexcept {
print("Yes",'\n');
std::exit(0);
}
[[noreturn]] inline void no() noexcept {
print("No",'\n');
std::exit(0);
}
inline void yorn(bool flag) noexcept {
print(flag ? "Yes" : "No",'\n');
}
//# Own allocater ################################################################
//# Container utility ############################################################
template<class T>
class container_emplaceer {
public:
container_emplaceer(T& cont):container_(cont){}
template<typename ...Args>
container_emplaceer<T>& operator () (const Args&& ...args){
if constexpr (has_emplace_back_v<T>) {
container_.emplace_back(args...);
}else if constexpr (has_emplace_v<T>) {
container_.emplace(args...);
}else{
static_assert([]()constexpr{return false;}());
}
return *this;
}
private:
T& container_;
};
template<class T>
constexpr container_emplaceer<T> emplace(T& container){
return container_emplaceer<T>{container};
}
//# STL Functions overload #######################################################
#ifdef USE_BOOST
}
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/algorithm_ext.hpp>
namespace taiton {
#else
// いらなくね？
template<class Container,class Function = std::less<>>
inline auto sort(Container&& a,Function&& compare = std::less{}){return std::sort(std::begin(a),std::end(a),compare);}
template<class Container,typename T,class Function = std::less<>>
inline auto lower_bound(Container&& a,T&& x,Function&& compare = std::less{}){return std::lower_bound(std::begin(a),std::end(a),x,compare);}
template<class Container,typename T,class Function = std::less<>>
inline auto upper_bound(Container&& a,T&& x,Function&& compare = std::less{}){return std::upper_bound(std::begin(a),std::end(a),x,compare);}
template<class Container,typename T>
inline auto accumlate(Container&& a,T&& init){return std::accumulate(std::begin(a),std::end(a),init);}
template<class Container,typename T,class Function>
inline auto accumlate(Container&& a,T&& init,Function&& op){return std::accumulate(std::begin(a),std::end(a),init,op);}
#endif
//# Graph ########################################################################
#ifdef USE_BOOST_GRAPH
}
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
namespace taiton {
template<class ifDirected,class EdgeProperty = boost::no_property>
using graph_t_impl = boost::adjacency_list<boost::vecS,boost::vecS,ifDirected,boost::no_property,EdgeProperty>;
using directed_graph_t = graph_t_impl<boost::directedS>;
using undirected_graph_t = graph_t_impl<boost::undirectedS>;
using graph_t = undirected_graph_t;
using vertex_t = graph_t::vertex_descriptor;
using edge_t = graph_t::edge_descriptor;
#endif
//# Geometry #####################################################################
#ifdef USE_BOOST_GEOMETRY
}
#include <boost/geometry.hpp>
namespace taiton {
template<typename T>
using point2_t = boost::geometry::model::d2::point_xy<T>;
#if BOOST_VERSION < 107800
}
#include <boost/geometry/algorithms/detail/azimuth>
namespace taiton {
template<class Point1,class Point2>
inline long double azimuth(const Point1 &p1,const Point2 &p2){
return azimuth<long double>(p1,p2);
}
template<typename T>
class point3_t : public boost::geometry::model::point<T,3,boost::geometry::cs::cartesian> {
public:
constexpr inline T x() noexcept {
return this->get<0>();
}
constexpr inline T y() noexcept {
return this->get<1>();
}
constexpr inline T z() noexcept {
return this->get<2>();
}
};
#else
template<typename T>
using point3_t = boost::geometry::model::d3::point_xyz<T>;
#endif
template<class Point>
using segment_t = boost::geometry::model::segment<Point>;
template<class Point>
inline Point rotate(Point geo,double deg){
boost::geometry::strategy::transform::rotate_transformer<boost::geometry::degree,long double,2,2> translate{deg};
boost::geometry::transform(geo,geo,translate);
return geo;
}
template<class Point>
inline Point rotate(Point geo,const Point& org,double deg){
boost::geometry::set<0>(geo,boost::geometry::get<0>(geo) - boost::geometry::get<0>(org));
boost::geometry::set<1>(geo,boost::geometry::get<1>(geo) - boost::geometry::get<1>(org));
geo = rotate(geo,deg);
boost::geometry::set<0>(geo,boost::geometry::get<0>(geo) + boost::geometry::get<0>(org));
boost::geometry::set<1>(geo,boost::geometry::get<1>(geo) + boost::geometry::get<1>(org));
return geo;
}
#endif
//# Multiprecision ###############################################################
#ifdef USE_BOOST_MULTIPRECISION
}
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
namespace taiton {
namespace mp = boost::multiprecision;
using cint = mp::cpp_int;
using lfloat = mp::number<mp::cpp_dec_float<12>>;
#endif
//# Type alias ###################################################################
using ll = int64_t;
using uint = uint32_t;
using ull = uint64_t;
using ldouble = long double;
using str = std::string;
//template<typename T>using vec = std::vector<T>;
template<typename T>
class vec : public std::vector<T> {
using Base = std::vector<T>;
public:
vec(size_t size):Base(size){}
vec(size_t size,const T& init):Base(size,init){}
vec(const std::initializer_list<T>& list):Base(list){}
};
using ivec = vec<int>;
using llvec = vec<ll>;
using bvec = vec<bool>;
using fvec = vec<float>;
using dvec = vec<double>;
using ldvec = vec<ldouble>;
using cvec = vec<char>;
using svec = vec<str>;
template<typename T,typename U>using pvec = vec<std::pair<T,U>>;
template<typename ...Args>using tvec = vec<std::tuple<Args...>>;
template<typename T>
class vvec : public std::vector<std::vector<T>> {
using Base = std::vector<std::vector<T>>;
public:
vvec(size_t n):Base(n){}
vvec(size_t h,size_t w):Base(h,std::vector<T>(w)){}
vvec(size_t h,size_t w,const T& init):Base(h,std::vector<T>(w,init)){}
};
using ivvec = vvec<int>;
using llvvec = vvec<ll>;
using bvvec = vvec<bool>;
using fvvec = vvec<float>;
using dvvec = vvec<double>;
using ldvvec = vvec<ldouble>;
using cvvec = vvec<char>;
using svvec = vvec<str>;
template<typename T,typename U>using pvvec = vvec<std::pair<T,U>>;
template<typename ...Args>using tvvec = vvec<std::tuple<Args...>>;
using iset = std::set<int>;
using llset = std::set<ll>;
using bset = std::set<bool>;
using fset = std::set<float>;
using dset = std::set<double>;
using ldset = std::set<ldouble>;
using cset = std::set<char>;
using sset = std::set<str>;
template<typename T,typename U>using pset = std::set<std::pair<T,U>>;
template<typename T>using mset = std::multiset<T>;
using imset = mset<int>;
using llmset = mset<ll>;
using bmset = mset<bool>;
using fmset = mset<float>;
using dmset = mset<double>;
using ldmset = mset<ldouble>;
using cmset = mset<char>;
using smset = mset<str>;
template<typename T>using deq = std::deque<T>;
using ideq = deq<int>;
using lldeq = deq<ll>;
using bdeq = deq<bool>;
using fdeq = deq<float>;
using ddeq = deq<double>;
using lddeq = deq<ldouble>;
using cdeq = deq<char>;
using sdeq = deq<str>;
template<typename T,size_t N>using arr = std::array<T,N>;
template<size_t N>using iarr = arr<int,N>;
template<size_t N>using llarr = arr<ll,N>;
template<size_t N>using barr = arr<bool,N>;
template<size_t N>using farr = arr<float,N>;
template<size_t N>using darr = arr<double,N>;
template<size_t N>using ldarr = arr<ldouble,N>;
template<size_t N>using carr = arr<char,N>;
template<size_t N>using sarr = arr<str,N>;
template<typename T>using initlist = std::initializer_list<T>;
#ifdef USE_ACL
using mint = atcoder::modint1000000007;
using mint2 = atcoder::modint998244353;
using mivec = vec<mint>;
using mi2vec = vec<mint2>;
#endif
}
using namespace taiton;
using namespace std;
#ifdef USE_ACL
using namespace atcoder;
#endif
#ifdef USE_BOOST
using namespace boost::range;
#ifdef USE_BOOST_GRAPH
using namespace boost::graph;
#endif
#ifdef USE_BOOST_GEOMETRY
using namespace boost::geometry;
#endif
namespace bst = boost;
#endif
#define rep_overload(i,n,m, REP, ...) REP
#define rep_0(n) for(int repeatCounter=static_cast<int>(n);repeatCounter;--repeatCounter)
#define rep_1(i,n) for(int i=0,repeatCounter=static_cast<int>(n);i < repeatCounter;++i)
#define rep_2(i,a,n) for(int i=a,repeatCounter=static_cast<int>(n);i < repeatCounter;++i)
#define rep(...) rep_overload(__VA_ARGS__,rep_2,rep_1,rep_0)(__VA_ARGS__)
#define drep_0(n) for(int i=0;i < static_cast<int>(n);++i)
#define drep_1(i,n) for(int i=0;i < static_cast<int>(n);++i)
#define drep_2(i,a,n) for(int i=static_cast<int>(n);i < static_cast<int>(n);++i)
#define drep(...) rep_overload(__VA_ARGS__,drep_2,drep_1,drep_0)(__VA_ARGS__) // 'd' means dynamic
#define fore(p,arr) for(auto& p : arr)
constexpr char spc = ' ';
constexpr char lend = '\n';
void salve(void){
}