7K12B blog

猫でも分かる何か

テンプレート

  • 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>;
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/dynamic_bitset.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/range/adaptors.hpp>
using namespace boost;
using mpi=multiprecision::cpp_int;
using mpf=multiprecision::cpp_dec_float_100;
#endif

using ll=long long; using ld=long double; using ch=char; using bo=bool;
using cll=const ll; using cld=const ld; using cch=const ch; using cbo=const bo;
using ull=unsigned long long; using str=string; using bit=dynamic_bitset<>;
using cull=const ull; using cstr=const str; using cbit=const bit;
template<class T, class U>struct tuple2 { T a; U b; tuple2():a(),b(){} tuple2(T c, U d) { a=c,b=d; } auto operator<=>(const tuple2&) const=default; tuple2& operator=(const pair<T,U>& r) { a=r.first,b=r.second; return *this; } tuple2(pair<T,U> p):a(p.first),b(p.second){} operator pair<T,U>() const { return pair<T,U>{a,b}; } };
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 tr=tuple3<T1,T2,T3>; template<class T1, class T2, class T3, class T4>using qu=tuple4<T1,T2,T3,T4>;
using pall=pa<ll,ll>; using pasl=pa<str,ll>;
using trlll=tr<ll,ll,ll>; using qullll=qu<ll,ll,ll,ll>;
template<class T>using vec=vector<T>; template<class T>using deq=deque<T>;
template<class T>using uset=unordered_set<T>; template<class A, class B> using umap=unordered_map<A,B>;
using vel=vec<ll>; using ves=vec<str>; using veb=vec<bit>; using vepall=vec<pall>;
using del=deq<ll>; using dec=deq<ch>; using des=deq<str>;
using sel=set<ll>; using sec=set<ch>; using ses=set<str>;
using mall=map<ll,ll>; using malb=map<ll,bo>; using macc=map<ch,ch>; using macl=map<ch,ll>; using mass=map<str,str>;
using vevel=vec<vel>;
struct edge { ll vj=ll(); ll ey=ll(); }; using graph=vec<vec<edge>>;
#define all(c) (c).begin(),(c).end()                             // begin to end
#define allr(c) (c).rbegin(),(c).rend()                          // begin to end reverse
#define debug(...) cerr<<#__VA_ARGS__<<'=';DEBUG(__VA_ARGS__);   // debug
#define fori(i,f,l) for(ll i=f;i<l;i++)                          // for
#define forx(x,c) for(auto& x:c)                                 // for each x
#define forxy(x,y,c) for(auto& [x,y]:c)                          // for each xy
#define forxyz(x,y,z,c) for(auto& [x,y,z]:c)                     // for each xyz
#define forir(i,f,l) for(ll i=f;i>l;i--)                         // for reverse
#define forxr(x,c) for(auto& x:adaptors::reverse(c))             // for each x reverse
#define forxyr(x,y,c) for(auto& [x,y]:adaptors::reverse(c))      // for each xy reverse
#define forxyzr(x,y,z,c) for(auto& [x,y,z]:adaptors::reverse(c)) // for each xyz reverse
#define nlb [&]{                                                 // nameless lambda begin
#define nle }()                                                  // nemeless lambda end
#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 instr(...) str __VA_ARGS__; IN(__VA_ARGS__);                       // input str
#define invel(name,sz) vel name(sz); IN(name);                             // input vel
#define inves(name,sz) ves name(sz); IN(name);                             // input ves
#define invevel(name,y,x) vevel name(y,vel(x)); IN(name);                  // input vevell
#define invepall(name,sz,afix,bfix) vepall name(sz); INVP(name,afix,bfix); // input vepall
#define in_graph(name,vsz,esz,vifix) graph name(vsz); ING(name,esz,vifix);                         // input graph
#define in_directed_graph(name,vsz,esz,vifix) graph<ll> name(vsz); INDG(name,esz,vifix);           // input directed graph
#define in_weighted_graph(name,vsz,esz,vifix) graph<ll> name(ndsz); INWG(name,esz,vifix);          // input weighted graph
#define in_weighted_directed_graph(name,vsz,esz,vifix) graph<ll> name(vsz); INWDG(name,esz,vifix); // input weighted directed graph 
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()
ll bcnt(ll x, bo b); bo bget(ll x, ll i); ll blen(ll x); void bset(ll&x, ll i, bo b);
vel degin(graph& g); vel degout(graph& g);
template<class C>ll lower_bound_index(C& c, auto x); template<class C>auto lower_bound_value(C& c, auto x); template<class C>ll upper_bound_index(C& c, auto x); template<class C>auto upper_bound_value(C& c, auto x);
ll ldiv(ll a, ll b, bo ceil); ll llog(ll a, ll b, bool u); ll lpow(ll x, ll n); template <class T> ll lsz(T& c);
bo orange(auto& c, ll x); bo orange(auto& c, ll y, ll x);
template<class T>void debug2d(T& vv);
str tostr(ll x); str tolower(const str& s); str toupper(const str& 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...>>;
ll bcnt(ll x, bo b) { return (b)?popcount((ull)x):llog(2,x,true)-popcount((ull)x); }
bo bget(ll x, ll i) { return (62<i)?0:x&(1ll<<i); }
ll blen(ll x) { return llog(2,x,true); }
void bset(ll& x, ll i, bo b) { (b)?(x|=(1ll<<i)):(x&=~(1ll<<i)); }
vel degin(graph& g) { vel deg(lsz(g)); fori(i,0,lsz(g)) forxy(vj,ey,g[i]) deg[vj]++; return deg; }
vel degout(graph& g) { vel deg(lsz(g)); fori(i,0,lsz(g)) deg[i]+=lsz(g[i]); return deg; }
template<class C>ll lower_bound_index(C& c, auto x) { return lower_bound(all(c),x)-c.begin(); }
template<class C>auto lower_bound_value(C& c, auto x) { if constexpr(IST<set,C>::value) return *c.lower_bound(x); else return *lower_bound(all(c),x); }
template<class C>ll upper_bound_index(C& c, auto x) { return upper_bound(all(c),x)-c.begin(); }
template<class C>auto upper_bound_value(C& c, auto x) { if constexpr(IST<set,C>::value) return *c.upper_bound(); else return *upper_bound(all(c),x); }
void DEBUG(void) { cerr<<en; }
void DEBUG(auto x) { cerr<<x<<en; }
template<class H, class ... T>void DEBUG(H head, T ... tail){ cerr<<fixed<<setprecision(8)<<head<<','; DEBUG(tail...); }
template <class C> void debugsp(C& c){ for(auto& e:c) cerr<<e<<sp; DEBUG(); }
template <class C> void debugen(C& c){ for(auto& e:c) cerr<<e<<en; DEBUG(); }
template<class T>void debug2d(T& c){ fori(y,0,lsz(c)) fori(x,0,lsz(c[y])+1) (x==lsz(c[y]))?cerr<<endl:cerr<<c[y][x]; }
template<class C>bo findb(C& c, auto x) { if constexpr(is_same_v<str,C>) { str p=x; return search(all(c),boyer_moore_searcher(all(p)))!=c.end(); } else if constexpr(IST<set,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<str,C>) { str 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 tr<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 qu<T1,T2,T3,T4>& q) { return (i==0)?q.a:(i==1)?q.b:(i==2)?q.c:q.d; }
ll gi(auto& c, ll i) { return i<0?lsz(c)+i+abs(abs(i+1)/lsz(c))*lsz(c):i-(i/lsz(c))*lsz(c); }
ll gir(auto& c, ll i) { return i<0?(abs(i)-1)-((abs(i)-1)/lsz(c))*lsz(c):lsz(c)-1-(i-(i/lsz(c))*lsz(c)); }
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 ldiv(ll a, ll b, bo ceil){ return (ceil)?(a+b-1)/b:a/b; }
ll lfind(auto& c, auto x) { return (c.find(x)==c.end())?0:1; }
ll llog(ll a, ll b, bo ceil) { ll now = 1, res = (ceil) ? 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; fori(i,0,n) z*=x; return z; }
template <class T> ll lsz(T& t){ return (ll)t.size(); }
ll llen(ll x){ return (ll)tostr(x).size(); }
bo orange(auto& c, ll x) { return x<0||lsz(c)<=x; }
bo orange(auto& c, ll y, ll x) { return y<0||lsz(c)<=y||x<0||lsz(c[y])<=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<<fixed<<setprecision(8)<<e<<sp; out(); }
template <class C> void outen(C& c){ for(auto& e:c) cout<<fixed<<setprecision(8)<<e<<en; out(); }
template<class T>auto pop(T& c, ll i=inf){ if(i==inf) { auto r=c.back(); c.pop_back(); return r; } auto r=c[min(lsz(c)-1,i)]; fori(j,i+1,lsz(c)) c[j-1]=c[j]; c.pop_back(); return r; }
template<class T>void push(T& c, auto x, ll i=inf){ if constexpr(IST<set,T>::value) c.insert(x); else c.insert(c.begin()+min(lsz(c),i),x); }
char toch(ll x) { return char(x+48); }
str tostr(ll x) { return to_string(x); }
ll toll(ch c) { return ll(c)-48; }
ll toll(string& s) { return stoll(s); }
str tolower (const str& s){ str res; for(auto& e:s) res.push_back(tolower(e)); return res; }
str toupper(const str& s){ str res; for(auto& e:s) res.push_back(toupper(e)); return res; }
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); fori(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); fori(y,0,ys) cc[y].resize(xs,x); }
auto reverse_graph(graph& g) { graph res(lsz(g)); fori(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)); fori(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>& p){ cin>>p.a>>p.b; }
template<class T>void IN(vec<T>& v){ forx(e,v) IN(e); }
void INVP(auto& v, auto afix, auto bfix){ forx(e,v) IN(e.a,e.b),e.a+=afix,e.b+=bfix; }
void ING(graph& g, ll esz, ll vifix) { ll vi,nvi; fori(e,0,esz) cin>>vi>>nvi,push(g[vi+vifix],edge{nvi+vifix,1}),push(g[nvi+vifix],edge{vi+vifix,1}); }
void INDG(graph& g, ll edsz, ll ndfix) { fori(e,0,edsz) { ll i,j; cin>>i>>j,i+=ndfix,j+=ndfix,g[i].push_back({j,1});} }
void INWG(graph& g, ll edsz, ll ndfix) { fori(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& g, ll edsz, ll ndfix) { fori(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 {};