テンプレート

型

• primitive

using ll=long long; using ld=long double; using bo=bool; using ch=char; using st=string; using bi=bitset<1>; using ull=unsigned long long;

• container

template<class T>using ve=vector<T>; template<class T>using de=deque<T>; template<class T>using se=set<T>;

• vector

using vl=ve<ll>; using vd=ve<ld>; using vc=ve<ch>; using vs=ve<st>; using vb=ve<bi>;

c++のbool型vectorはカスなことで有名なのでbitset型vectorで代用

• pair, triple, quadruple

template<class T1, class T2>struct tuple2{ T1 a; T2 b; tuple2():a(),b(){} tuple2(T1 c, T2 d) { a=c,b=d; } auto operator<=>(const tuple2&) const=default; };
template<class T1, class T2, class T3>struct tuple3{ T1 a; T2 b; T3 c; tuple3():a(),b(),c(){} tuple3(T1 d, T2 e, T3 f) { a=d,b=e,c=f; } auto operator<=>(const tuple3&) const=default; };
template<class T1, class T2, class T3, class T4>struct tuple4{ T1 a; T2 b; T3 c; T4 d; tuple4():a(),b(),c(),d(){} tuple4(T1 e, T2 f, T3 g, T4 h) { a=e,b=f,c=g,d=h; } auto operator<=>(const tuple4&) const=default; };
template<class T1, class T2>using pa=tuple2<T1,T2>; template<class T1, class T2, class T3>using tri=tuple3<T1,T2,T3>; template<class T1, class T2, class T3, class T4>using quad=tuple4<T1,T2,T3,T4>;

マクロ

#define all(c) (c).begin(),(c).end()                      // begin to end
#define allr(c) (c).rbegin(),(c).rend()                   // rbegin to rend
#define rep(i,b,e) for(ll i=b;i<e;i++)                    // repeat
#define repr(i,b,e) for(ll i=b;e<i;i--)                   // repeat reverse
#define each(e,c) for(auto& e:c)                          // each for
#define nf [&]()                                          // nameless function
#define lf(name,...) auto name=[&](__VA_ARGS__)           // lambda function
#define inll(...) ll __VA_ARGS__; in(__VA_ARGS__);        // input ll
#define inld(...) ld __VA_ARGS__; in(__VA_ARGS__);        // input ld
#define inch(...) ch __VA_ARGS__; in(__VA_ARGS__);        // input ch
#define inst(...) st __VA_ARGS__; in(__VA_ARGS__)         // input st
#define invl(name,sz) vl name(sz); in(name)               // input vl
#define invs(name,sz) vs name(sz); in(name)               // input vs
#define invpll(name,sz) vpll name(sz); invp(name)         // input vpll
#define invpdd(name,sz) vpdd name(sz); invp(name)         // input vpdd
#define invvl(name,y,x) vvl name(y,vl(x)); in(name)       // input vvll
#define invvc(name,y,x) vvc name(y,vc(x)); in(name)       // input vvc
#define in_graph(name,ndsz,edsz,ndfix) graph name(ndsz); ing(name,ndsz,edsz,ndfix)
#define in_weighted_graph(name,ndsz,edsz,ndfix) graph name(ndsz); inwg(name,ndsz,edsz,ndfix)
#define in_directed_graph(name,ndsz,edsz,ndfix) graph name(ndsz); indg(name,vsz,edsz,ndfix)
#define in_weighted_directed_graph(name,vsz,esz,ndfix) graph name(ndsz); indwg(name,ndsz,edsz,ndfix)

関数

• at

template<class T>auto at(T& c, ll i, ll r=0){ if(r==-1) return (i<0)?c[-i-1]:c[lsize(c)-1-i]; return (i<0)?c[lsize(c)+i]:c[i]; }
template<class T>auto atr(T& c, ll i, ll r=0){ return (r==-1)?at(c,i):at(c,-i-1); }

pythonを参考にコンテナを負のインデックスで取得出来るようにした関数
auto at(T& c, ll i, ll r=0): r=0のとき先頭[0]末尾[-1]として取得しr=1のとき末尾[0]先頭[-1]として取得する
auto atr(T& c, ll i, ll r=0): r=0のとき先頭[-1]末尾[0]として取得しr=1のとき先頭[0]末尾[-1]として取得する

• bit

ll bpopcnt(ll x){ return popcount((unsigned long long)x); }
bo btest(ll x, ll i){ return (62<i)?0:x&(1ll<<i); }
void bset(ll& x, ll i, bo b){ (b)?x|=(1ll<<i):x&=~(1ll<<i); }

ll bpopcnt(ll x); C++20のpopcountと同じだが引数をll型で受け取ることが出来る
bo btest(ll x, ll i); 整数xのi番目ビットが0か1か返す
void bset(ll& x, ll i, bo b); 整数xのi番目ビットをb=0/1にセットする

• get

template<ll i, class T1, class T2>auto& get(const pa<T1,T2>& p) { return (i==0)?p.a:p.b; }
template<ll i, class T1, class T2, class T3>auto& get(const tri<T1,T2,T3>& t) { return (i==0)?t.a:(i==1)?t.b:t.c; }
template<ll i, class T1, class T2, class T3, class T4>auto& get(const quad<T1,T2,T3,T4>& q) { return (i==0)?q.a:(i==1)?q.b:(i==2)?q.c:q.d; }

pa, tri, quad型のi番目の要素を取得する（std::getのオーバーロード）

• in

void in(){}
template<class H, class ... T>void in(H& head, T& ... tail){ cin >> head; in(tail...); }
template<class T, class U>void in(pa<T,U>& t){ cin>>t.a>>t.b; }
template<class T>void in(ve<T>& v){ for(auto& e:v) in(e); }
template<class T, class U>void invp(ve<pa<T,U>>& v){ for(auto& e:v) in(e.a,e.b); }
void ing(graph<ll>& g, ll ndsz, ll edsz, ll ndfix) { g.resize(ndsz); rep(e,0,edsz) { ll i,j; cin>>i>>j,i+=ndfix,j+=ndfix,g[i].push_back({j,1}),g[j].push_back({i,1}); } }
void indg(graph<ll>& g, ll ndsz, ll edsz, ll ndfix) { g.resize(ndsz); rep(e,0,edsz) { ll i,j; cin>>i>>j,i+=ndfix,j+=ndfix,g[i].push_back({j,1});} }
void inwg(graph<ll>& g, ll ndsz, ll edsz, ll ndfix) { g.resize(ndsz); rep(e,0,edsz) { ll i,j,c; cin>>i>>j>>c,i+=ndfix,j+=ndfix,g[i].push_back({j,c}),g[j].push_back({i,c}); } }
void inwdg(graph<ll>& g, ll ndsz, ll edsz, ll ndfix) { g.resize(ndsz); rep(e,0,edsz) { ll i,j,c; cin>>i>>j>>c,i+=ndfix,j+=ndfix,g[i].push_back({j,c}); } }

某レッドコーダーのコードを写経した
pythonのように変数宣言と入力を同時に可能にした関数でマクロから呼び出す

• orange

template <class T> bool orange(ll x, ve<T>& v) { return (x<0||ll(v.size())<= x); }
template <class T> bool orange(ll y, ll x, ve<ve<T>>& v) { return (y<0||ll(v.size())<=y||x<0||ll(v[y].size())<=x); }

一次元または二次元コンテナに対してインデックス[y][x]が範囲外かどうかチェックする

• out

void out(){ cout<<en; }
template<class H, class ... T>void out(H head, T ... tail){ cout<<fixed<<setprecision(8)<<head; out(tail...); }
template <class C> void outsp(C& c){ for(auto& e:c) cout<<e<<sp; cout<<en; }
template <class C> void outel(C& c){ for(auto& e:c) cout<<e<<en; }

コンテナの内容を一括して出力する

• pop, push

auto pop(auto& c, ll i=inf){ auto r=c[(i==inf)?lsize(c)-1:i]; if(i!=inf)rep(j,i+1,lsize(c)) c[j-1]=c[j]; c.pop_back(); return r; }
void push(auto& c, auto x, ll i=inf){ return (i!=inf)?(void)c.insert(c.begin()+i,x):c.push_back(x); }

C++のpopは不便なのでpopと同時に値も取得できるようにした
auto pop(auto& c, ll i=inf): cのi番目要素をpopする
（iをsize以上に指定したときはpopbackでO(1)、それ以外はデータ構造依存の計算量）
void push(auto& c, auto x, ll i=inf): cのi番目に値xをpushする
（iをsize以上に指定したときはpushbackでO(1)、それ以外はデータ構造依存の計算量）

• tsort

template<ll i, class T>void tsort(T b, T e) { sort(b,e,[&](const auto& l, const auto& r){return get<i>(l)<get<i>(r);}); }

tuple型コンテナに対してi番目の要素に着目してソートする

• trim

template <class T> T trim(T& c, ll l, ll r) { T t; umin(r,lsize(c)); rep(i,l,r) push(t,c[i]); return t; }

半開区間[l,r)でコンテナをトリミングして返す

ソースコード

#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
#define BOOST
#ifdef BOOST
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
using namespace boost;
using mpi=multiprecision::cpp_int;
using mpf=multiprecision::cpp_dec_float_100;
#endif

using ll=long long; using ull=unsigned long long; using ld=long double; 
using ch=char; using st=string; using bo=bool; using bi=bitset<1>; 
template<class T>using ve=vector<T>; template<class T>using vve=ve<ve<T>>; template<class T>using vvve=ve<vve<T>>;
using vl=ve<ll>; using vd=ve<ld>; using vc=ve<ch>; using vs=ve<st>; using vb=ve<bi>;
using vvl=ve<vl>; using vvd=ve<vd>; using vvc=ve<vc>; using vvs=ve<vs>; using vvb=ve<vb>;
template<class T>using de=deque<T>; template<class T>using se=set<T>; template<class T, class S>using ma=map<T,S>;
using dl=de<ll>; using dc=de<ch>; using ds=de<st>;
using sl=se<ll>; using sc=se<ch>; using ss=se<st>;
using mll=ma<ll,ll>; using mcc=ma<ch,ch>; using mss=ma<st,st>; using mcl=ma<ch,ll>;
template<class T1, class T2>struct tuple2 { T1 a; T2 b; tuple2():a(),b(){} tuple2(T1 c, T2 d) { a=c,b=d; } auto operator<=>(const tuple2&) const=default; };
template<class T1, class T2, class T3>struct tuple3 { T1 a; T2 b; T3 c; tuple3():a(),b(),c(){} tuple3(T1 d, T2 e, T3 f) { a=d,b=e,c=f; } auto operator<=>(const tuple3&) const=default; };
template<class T1, class T2, class T3, class T4>struct tuple4 { T1 a; T2 b; T3 c; T4 d; tuple4():a(),b(),c(),d(){} tuple4(T1 e, T2 f, T3 g, T4 h) { a=e,b=f,c=g,d=h; } auto operator<=>(const tuple4&) const=default; };
template<class T1, class T2>using pa=tuple2<T1,T2>; template<class T1, class T2, class T3>using tri=tuple3<T1,T2,T3>; template<class T1, class T2, class T3, class T4>using quad=tuple4<T1,T2,T3,T4>;
using pll=pa<ll,ll>; using pdd=pa<ld,ld>; using psl=pa<st,ll>;
using vpll=ve<pll>; using vvpll=ve<vpll>; using dpll=de<pll>; using spll=set<pll>;
using vpdd=ve<pdd>; using vvpdd=ve<vpdd>; using dpdd=de<pdd>; using spdd=set<pdd>;
template<class T>using graph=vve<pa<ll,T>>;
#define all(c) (c).begin(),(c).end()                      // begin to end
#define allr(c) (c).rbegin(),(c).rend()                   // begin to end reverse
#define rep(i,b,e) for(ll i=b;i<e;i++)                    // repeat
#define repr(i,b,e) for(ll i=b;e<i;i--)                   // repeat reverse
#define each(e,c) for(auto& e:c)                          // each for
#define nfb [&]{                                          // nameless function begin
#define nfe }()                                           // nemeless function end
#define lf(name,...) auto name=[&](__VA_ARGS__)           // lambda function
#define inll(...) ll __VA_ARGS__; IN(__VA_ARGS__);        // input ll
#define inld(...) ld __VA_ARGS__; IN(__VA_ARGS__);        // input ld
#define inch(...) ch __VA_ARGS__; IN(__VA_ARGS__);        // input ch
#define inst(...) st __VA_ARGS__; IN(__VA_ARGS__)         // input st
#define invl(name,sz) vl name(sz); IN(name)               // input vl
#define invs(name,sz) vs name(sz); IN(name)               // input vs
#define invpll(name,sz,fix) vpll name(sz); INVP(name,fix) // input vpll
#define invpdd(name,sz) vpdd name(sz); INVP(name)         // input vpdd
#define invvl(name,y,x) vvl name(y,vl(x)); IN(name)       // input vvll
#define invvc(name,y,x) vvc name(y,vc(x)); IN(name)       // input vvc
#define in_graph(name,ndsz,edsz,ndfix) graph<ll> name(ndsz); ING(name,ndsz,edsz,ndfix)
#define in_weighted_graph(name,ndsz,edsz,ndfix) graph<ll> name(ndsz); INWG(name,ndsz,edsz,ndfix)
#define in_directed_graph(name,ndsz,edsz,ndfix) graph<ll> name(ndsz); INDG(name,vsz,edsz,ndfix)
#define in_weighted_directed_graph(name,vsz,esz,ndfix) graph<ll> name(ndsz); INWDG(name,ndsz,edsz,ndfix)
const ch en='\n';                       // endl
const ch sp=' ';                        // space
const ll inf=2000000000000000000;       // infinity 2e18
const ll abc_max=26;                    // alphabet max size
const ll llong_max=9223372036854775807; // 9e18
const ld pi=numbers::pi;                // 3.14
const ll mint1=1000000007;              // mod int 1e9+7
const ll mint9=998244353;               // mod int 998244353
const size_t str_not_find=string::npos; // string::find()
auto at(auto& c, ll i, bo r=false);
ll bpopcnt(ll x); bo btest(ll x, ll i);
ll lceildiv(ll a, ll b); ll llog(ll a, ll b, bool u); ll lpow(ll x, ll n); template <class T> ll lsz(T& c);
template <class T> bo orange(ll x, ve<T>& v); template <class T> bool orange(ll y, ll x, ve<ve<T>>& v);
template<class T>void debug2d(T& vv);
st tost(ll x); st tolower(const st& s); st toupper(const st& s);
void IN(); template<class H, class...T>void IN(H& head, T&...tail);
template<template<class...>class TE, class TY>struct IST;
template<template<class...>class TE, class...A>struct IST<TE,TE<A...>>;
auto at(auto& c, ll i, bo r) { if(r) return (i<0)?c[-i-1]:c[lsz(c)-1-i]; return (i<0)?c[lsz(c)+i]:c[i]; }
template<class C>ll boundli(C& c, auto x) { return lower_bound(all(c),x)-c.begin(); }
template<class C>auto boundlv(C& c, auto x) { if constexpr(IST<se,C>::value) { return *c.upper_bound(); } else return *upper_bound(all(c),x); }
template<class C>ll boundui(C& c, auto x) { return lower_bound(all(c),x)-c.begin(); }
template<class C>auto bounduv(C& c, auto x) { if constexpr(IST<se,C>::value) { return *c.upper_bound(); } else return *upper_bound(all(c),x); }
ll bpopcnt(ll x){ return popcount((unsigned long long)x); }
ll bsz(ll x) { return llog(2, x, true); }
bo btest(ll x, ll i){ return (62<i)?0:x&(1ll<<i); }
void bset(ll& x, ll i, bo b){ (b)?x|=(1ll<<i):x&=~(1ll<<i); }
void debug(){ cout<<en; }
template<class H, class ... T>void debug(H head, T ... tail){ cout<<fixed<<setprecision(8)<<head<<sp; debug(tail...); }
template <class C> void debugsp(C& c){ for(auto& e:c) cout<<e<<sp; debug(); }
template <class C> void debugel(C& c){ for(auto& e:c) cout<<e<<en; debug(); }
template<class T>void debug2d(T& c){ rep(y,0,lsz(c))rep(x,0,lsz(c[y])+1) (x==lsz(c[y]))?cout<<endl:cout<<c[y][x]; }
template<class C>bo findb(C& c, auto x) { if constexpr(is_same_v<st,C>) { st p=x; return search(all(c),boyer_moore_searcher(all(p)))!=c.end(); } else if constexpr(IST<se,C>::value) return c.find()!=c.end(); else return find(all(c),x)!=c.end(); }
template<class C>ll findi(C& c, auto x) { if constexpr(is_same_v<st,C>) { st p=x; auto i=search(all(c),boyer_moore_searcher(all(p))); return (i==c.end())?inf:i-c.begin(); } else { auto i=find(all(c),x); return (i==c.end())?inf:i-c.begin(); } }
template<ll i, class T1, class T2>auto& get(const pa<T1,T2>& p) { return (i==0)?p.a:p.b; }
template<ll i, class T1, class T2, class T3>auto& get(const tri<T1,T2,T3>& t) { return (i==0)?t.a:(i==1)?t.b:t.c; }
template<ll i, class T1, class T2, class T3, class T4>auto& get(const quad<T1,T2,T3,T4>& q) { return (i==0)?q.a:(i==1)?q.b:(i==2)?q.c:q.d; }
template <class T, class S> void fillvv(T b, T e, S x) { for(auto it=b;it!=e;it++) std::fill(all((*it)),x); }
template <class C> ll lcnt(C& c) { return ll(c.count()); }
template <class C, class X> ll lcnt(C& c, X x) { return ll(count(all(c), x)); }
ll lceildiv(ll a, ll b){ return (a+b-1)/b; }
ll llog(ll a, ll b, bool u) { ll now = 1, res = (u) ? 1 : 0; while (now < b) res++, now *= a; return (now != b) ? res - 1 : res; }
ll lpow(ll x, ll n) { if (x == 2) return (1ll << n); ll z = 1; rep(i, 0, n) z *= x; return z; }
template <class T> ll lsz(T& c){ return (ll)c.size(); }
ll lsz(ll x){ st s=tost(x); return lsz(s); }
template <class T> bool orange(ll x, ve<T>& v) { return (x<0||ll(v.size())<= x); }
template <class T> bool orange(ll y, ll x, ve<ve<T>>& v) { return (y<0||ll(v.size())<=y||x<0||ll(v[y].size())<=x); }
void out(){ cout<<en; exit(0); }
template<class H, class...T>void out(H head, T ... tail){ cout<<fixed<<setprecision(8)<<head; out(tail...); }
template <class C> void outsp(C& c){ for(auto& e:c) cout<<e<<sp; out(); }
template <class C> void outen(C& c){ for(auto& e:c) cout<<e<<en; out(); }
auto pop(auto& c, ll i=inf){ auto r=c[min(lsz(c)-1,i)]; rep(j,i+1,lsz(c)) c[j-1]=c[j]; c.pop_back(); return r; }
template<class C>void push(C& c, auto x, ll i=inf){ if constexpr(IST<set,C>::value) c.insert(x); else c.insert(c.begin()+min(lsz(c),i),x); }
char toch(ll x) { return char(x+48); }
string tost(ll x) { return to_string(x); }
ll toll(ch c) { return ll(c)-48; }
ll toll(string& s) { return stoll(s); }
string tolower(const st& s){ string res; for(auto& e:s) res.push_back(tolower(e)); return res; }
string toupper(const st& s){ string res; for(auto& e:s) res.push_back(toupper(e)); return res; }
template <class T> void fix_c(T& c, ll fix) { for (auto& e : c) e += fix; }
template <class T> void fix_cp(ll fix1, ll fix2, T& c) { for (auto& e : c) { if (fix1 != 0) e.pf += fix1; if (fix2 != 0) e.ps += fix2; } }
template <class T> void itr_next(T& itr, ll INF) { if (*itr != INF) ++itr; }
template <class T> void itr_prev(T& itr, ll INF) { if (*itr != INF) --itr; }
template<class T>void make2d(T& cc, ll ys, ll xs) { cc.resize(ys); rep(y,0,ys) cc[y].resize(xs); }
template<class T, class X>void make2d(T& cc, ll ys, ll xs, X x) { cc.resize(ys); rep(y,0,ys) cc[y].resize(xs,x); }
template<class T>auto reverse_graph(graph<T>& g) { graph<T> res(lsz(g)); rep(i,0,lsz(g)) for(auto& [j,c]:g[i]) res[j].push_back({i,c}); return res; }
template <class T1, class ... T2> bool umax(T1& x, T2 ... args) { x=max({x,args...}); return !(max({args...})<x); }
template <class T1, class ... T2> bool umin(T1& x, T2 ... args) { x=min({x,args...}); return !(x<min({args...}));}
template <class T> T trim(T& c, ll l, ll r) { T t=T(); umin(r,lsz(c)); rep(i,l,r) push(t,c[i]); return t; }
template<ll i>void tsort(auto b, auto e) { sort(b,e,[&](const auto& l, const auto& r){return get<i>(l)<get<i>(r);}); }
void IN(){}
template<class H, class ... T>void IN(H& head, T& ... tail){ cin>>head; in(tail...); }
template<class T, class U>void IN(pa<T,U>& t){ cin>>t.a>>t.b; }
template<class T>void IN(ve<T>& v){ for(auto& e:v) in(e); }
template<class T, class U, class V>void INVP(ve<pa<T,U>>& v, V fix){ for(auto& e:v) in(e.a,e.b),e.a+=fix,e.b+=fix; }
void ING(graph<ll>& g, ll ndsz, ll edsz, ll ndfix) { g.resize(ndsz); rep(e,0,edsz) { ll i,j; cin>>i>>j,i+=ndfix,j+=ndfix,g[i].push_back({j,1}),g[j].push_back({i,1}); } }
void INDG(graph<ll>& g, ll ndsz, ll edsz, ll ndfix) { g.resize(ndsz); rep(e,0,edsz) { ll i,j; cin>>i>>j,i+=ndfix,j+=ndfix,g[i].push_back({j,1});} }
void INWG(graph<ll>& g, ll ndsz, ll edsz, ll ndfix) { g.resize(ndsz); rep(e,0,edsz) { ll i,j,c; cin>>i>>j>>c,i+=ndfix,j+=ndfix,g[i].push_back({j,c}),g[j].push_back({i,c}); } }
void INWDG(graph<ll>& g, ll ndsz, ll edsz, ll ndfix) { g.resize(ndsz); rep(e,0,edsz) { ll i,j,c; cin>>i>>j>>c,i+=ndfix,j+=ndfix,g[i].push_back({j,c}); } }
template<template<class...>class TE, class TY>struct IST:std::false_type {};
template<template<class...>class TE, class...A>struct IST<TE,TE<A...>>:std::true_type {};

/**********************************/
/********** BEGIN OF LIB **********/
/**********************************/

namespace LIB {}
using namespace LIB;

/**********************************/
/*********** END OF LIB ***********/
/**********************************/

int main(void) {

	return 0;
}