My C++ template, incl. fancy colorized debug printouts↵
==================↵
↵
Use [this template](https://github.com/dcclyde/coding_puzzles/blob/master/templates/template.cpp) and you'll gain 350 rating right away! OK maybe not, but it has a bunch of cool features I built up while climbing from 1800 to 2150 in February-May of this year, and I bet some of them can be helpful to others too. Please, comment with feedback/suggestions/feature requests about how to make the template more useful :)↵
↵
Before I get into details about the template's functionality, here are links to the [current template version on GitHub](https://github.com/dcclyde/coding_puzzles/blob/master/templates/template.cpp) and the [version as of posting this blog](https://github.com/dcclyde/coding_puzzles/blob/ea1ef2ab073f22dd8a69c5c11d71e3adda5c411a/templates/template.cpp). I think my debug printouts setup is the most novel and cool feature in the template, so I've also prepared a [minimal version that adds only the dbg() functionality](https://github.com/dcclyde/coding_puzzles/blob/master/templates/dbg_demo.cpp).↵
↵
<spoiler summary="Finally, here's an embedded copy in case someone prefers to see the template without leaving Codeforces.">↵
↵
~~~~~↵
#pragma region↵
#ifdef _OPENMP↵
#include <omp.h>↵
#endif↵
#if defined(DCCLYDE_LOCAL) && __has_include("/home/dcclyde/puzzles/code/templates/superheader.h")↵
#include "/home/dcclyde/puzzles/code/templates/superheader.h"↵
#else↵
#define NDEBUG // don't bother with assertions on the judge server.↵
#include <tgmath.h>↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
#endif↵
using namespace std;↵
using namespace __gnu_pbds;↵
↵
#define CLEAN 0↵
#define CF 1↵
#define GCJ 2↵
↵
using ll = long long;↵
using db = long double; // or double, if TL is tight↵
using str = string; // yay python!↵
↵
// pairs↵
using pi = pair<int,int>;↵
using pl = pair<ll,ll>;↵
using pd = pair<db,db>;↵
//// I'm not used to the defs above.↵
using pii = pair<int,int>;↵
using pll = pair<ll,ll>;↵
using pdd = pair<db,db>;↵
#define mp make_pair↵
#define MP make_pair↵
#define MT make_tuple↵
#define f first↵
#define s second↵
↵
#define tcT template<class T↵
#define tcTU tcT, class U↵
// ^ lol this makes everything look weird but I'll try it↵
tcT> using V = vector<T>;↵
tcT, size_t SZ> using AR = array<T,SZ>;↵
using vi = V<int>;↵
using vb = V<bool>;↵
using vl = V<ll>;↵
using vll = V<ll>;↵
using vd = V<db>;↵
using vs = V<str>;↵
using vpi = V<pii>;↵
using vpii = V<pii>;↵
using vpl = V<pll>;↵
using vpll = V<pll>;↵
using vpd = V<pdd>;↵
↵
// vectors↵
// size(x), rbegin(x), rend(x) need C++17↵
#define sz(x) int((x).size())↵
#define bg(x) begin(x)↵
#define all(x) bg(x), end(x)↵
#define rall(x) x.rbegin(), x.rend()↵
#define sor(x) sort(all(x))↵
#define rsz resize↵
#define ins insert↵
#define pb push_back↵
#define eb emplace_back↵
#define emp emplace↵
#define ft front()↵
#define bk back()↵
↵
//// #define lb lower_bound↵
//// #define ub upper_bound↵
//// tcT> int lwb(V<T>& a, const T& b) { return int(lb(all(a),b)-bg(a)); }↵
//// tcT> int upb(V<T>& a, const T& b) { return int(ub(all(a),b)-bg(a)); }↵
↵
// bitwise ops↵
// also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html↵
constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set bits_set↵
constexpr ll pct(ll x) { return __builtin_popcountll(x); }↵
constexpr int bigbit(int x) { // assert(x >= 0); // make C++11 compatible until USACO updates ...↵
return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x))↵
constexpr int bigbitll(ll x) { // assert(x >= 0); // make C++11 compatible until USACO updates ...↵
return x == 0 ? 0 : 63-__builtin_clzll(x); } // floor(log2(x))↵
constexpr int p2(int x) { return 1<<x; }↵
constexpr int msk2(int x) { return p2(x)-1; }↵
↵
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up↵
ll fdiv(auto a, auto b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down↵
↵
ll powll(ll b, ll e) {↵
ll out = 1;↵
while (e) {↵
if (e&1) {out *= b;}↵
b *= b; e >>= 1;↵
}↵
return out;↵
}↵
ll powmod(ll b, ll e, ll mod) {↵
ll out = 1;↵
while (e) {↵
if (e&1) {out *= b; out %= mod;}↵
b *= b; b %= mod; e >>= 1;↵
}↵
return out;↵
}↵
↵
tcTU> bool ckmin(T& a, const U& b) {↵
return (T)b < a ? a = (T)b, 1 : 0; } // set a = min(a,b)↵
tcTU> bool ckmax(T& a, const U& b) {↵
return a < (T)b ? a = (T)b, 1 : 0; } // set a = max(a,b)↵
↵
int maxi(int a, int b) {return max((int)a, (int)b);}↵
int mini(int a, int b) {return min((int)a, (int)b);}↵
ll maxll(ll a, ll b) {return max((ll)a, (ll)b);}↵
ll minll(ll a, ll b) {return min((ll)a, (ll)b);}↵
↵
↵
template <typename, typename = void>↵
constexpr bool is_iterable_v{};↵
↵
template <typename T>↵
constexpr bool is_iterable_v<↵
T,↵
std::void_t< decltype(std::declval<T>().begin()),↵
decltype(std::declval<T>().end())↵
>↵
> = true;↵
↵
template <typename, typename=void>↵
constexpr bool is_tuplelike_v{};↵
↵
template <typename T>↵
constexpr bool is_tuplelike_v<↵
T,↵
void_t<↵
decltype(std::get<0>(declval<T>())),↵
decltype(std::tuple_size_v<T>)↵
>↵
> = true;↵
↵
// Safe hash maps. See https://codeforces.net/blog/entry/62393↵
struct custom_hash {↵
static uint64_t splitmix64(uint64_t x) {↵
// http://xorshift.di.unimi.it/splitmix64.c↵
x += 0x9e3779b97f4a7c15;↵
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;↵
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;↵
return x ^ (x >> 31);↵
}↵
↵
size_t operator()(uint64_t x) const {↵
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();↵
return splitmix64(x + FIXED_RANDOM);↵
}↵
template<class T, class U>↵
size_t operator()(const pair<T,U>& x) const {↵
uint64_t a = (*this)(x.first);↵
uint64_t b = (*this)(x.second);↵
return a + 3*b;↵
}↵
↵
template<class T, size_t k>↵
void op_tuplehelper(size_t& out, T t) const {↵
out += (*this)(get<k>(t)) * (k+1)*(k+1);↵
if constexpr (k < tuple_size_v<T> - 1) {↵
op_tuplehelper<T, k+1>(out, t);↵
}↵
}↵
template <typename X>↵
typename enable_if<is_tuplelike_v<X>, size_t>::type operator()(const X& t) const {↵
size_t out = 0;↵
op_tuplehelper<X, 0>(out, t);↵
return out;↵
}↵
↵
template <typename A>↵
typename enable_if<is_iterable_v<A>, size_t>::type operator()(const A& v) const {↵
uint64_t out = 0;↵
uint64_t offset = 1;↵
for (const auto& x : v) {↵
uint64_t curr = (*this)(x);↵
out ^= curr * offset;↵
offset *= 3;↵
}↵
return out;↵
}↵
};↵
↵
template<class A, class B> using umap = gp_hash_table<A,B,custom_hash>;↵
// template<class A, class B> using umap = unordered_map<A,B,custom_hash>; // slower?↵
// template<class A, class B> using umap = map<A,B>; // ok for tiny cases?↵
// template<class A, class B> using umap = unordered_map<A,B>; // slower and unsafe?↵
↵
template<class A> using uset = gp_hash_table<A,null_type,custom_hash>;↵
// template<class A> using uset = unordered_set<A, custom_hash>;↵
// template<class A> using uset = set<A>;↵
// template<class A> using uset = unordered_set<A>;↵
↵
#define unordered_map DCCLYDE_REMINDER_DONT_USE_UNPROTECTED_HASH_MAP↵
#define unordered_set DCCLYDE_REMINDER_DONT_USE_UNPROTECTED_HASH_SET↵
↵
↵
// loops↵
#define CONCAT_INNER(a, b) a ## b↵
#define CONCAT(a, b) CONCAT_INNER(a, b)↵
#define FORll(i,a,b) for (ll i = ((ll)a); i < ((ll)b); ++i)↵
#define FORint(i,a,b) for (int i = ((int)a); i < ((int)b); ++i)↵
// #define FOR3(i,a,b) for (int i = (a); i < (b); ++i)↵
#define FOR3(i,a,b) FORll(i,a,b)↵
#define F0R(i,a) FOR(i,0,a)↵
#define FOR2(i,a) FOR(i,0,a)↵
#define ROFll(i,a,b) for (ll i = ((ll)b)-1; i >= ((ll)a); --i)↵
#define ROFint(i,a,b) for (int i = ((int)b)-1; i >= ((int)a); --i)↵
// #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)↵
#define ROF(i,a,b) ROFll(i,a,b)↵
#define R0F(i,a) ROF(i,0,a)↵
#define rep(a) F0R(CONCAT(_,__LINE__),a)↵
#define each(a,x) for (auto& a: x)↵
#define foreach(a,x) each(a,x)↵
↵
#define FOR1(x) for(auto x)↵
#if __cplusplus >= 202002L↵
auto stepped_iota(ll start, ll end, ll step=1) {↵
ll iter_count = cdiv(end-start, step);↵
ckmax(iter_count, 0);↵
return std::ranges::views::iota(0LL, iter_count) |↵
std::ranges::views::transform([=](ll x) { return x * step + start; });↵
}↵
#define FOR4(i,s,e,step) for(auto i : stepped_iota(s, e, step))↵
#else↵
#define FOR4(i,s,e,step) for(ll i = s; i != e && ((i<e) == (s<e)) ; i += step)↵
#endif↵
↵
// just as an example of how to iterate in reverse order↵
// for(auto& x : dat | views::reverse) {}↵
↵
#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME↵
#define FOR(...) GET_MACRO(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)↵
↵
#pragma region // rangeint↵
V<int> rangeint(int start, int end, int inc=1) {↵
V<int> out;↵
if (inc > 0) {↵
for(int curr = start; curr < end; curr += inc) {↵
out.push_back(curr);↵
}↵
return out;↵
} else {↵
for(int curr = start; curr > end; curr += inc) {↵
out.push_back(curr);↵
}↵
return out;↵
}↵
}↵
#pragma endregion↵
↵
// const int MX = 2e5+5;↵
const ll BIG = 1e18; // not too close to LLONG_MAX↵
const db PI = acos((db)-1);↵
//// const int dx[4]{1,0,-1,0}, dy[4]{0,1,0,-1}; // for every grid problem!!↵
vector<pii> stepsOrthogonal = {{1,0},{0,1},{-1,0},{0,-1}};↵
vector<pii> stepsDiagonal = {{1,1},{1,-1},{-1,-1},{-1,1}};↵
vector<pii> steps8dirs = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};↵
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());↵
#pragma region // rng examples↵
// std::uniform_real_distribution<db> rand_dbl(0, 1); // [L, R)↵
// db ard = unif_db(rng);↵
// std::uniform_int_distribution<int> rand_int(1, 2); // inclusive↵
// int ri = rand_int(rng);↵
#pragma endregion↵
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;↵
↵
tcT> ll fstTrue(ll lo, ll hi, T f) {↵
++hi; assert(lo <= hi); // assuming f is increasing↵
while (lo < hi) { // find first index such that f is true↵
ll mid = lo+(hi-lo)/2;↵
f(mid) ? hi = mid : lo = mid+1;↵
}↵
return lo;↵
}↵
tcT> ll lstTrue(ll lo, ll hi, T f) {↵
--lo; assert(lo <= hi); // assuming f is decreasing↵
while (lo < hi) { // find first index such that f is true↵
ll mid = lo+(hi-lo+1)/2;↵
f(mid) ? lo = mid : hi = mid-1;↵
}↵
return lo;↵
}↵
tcT> void remDup(vector<T>& v) { // sort and remove duplicates↵
sort(all(v)); v.erase(unique(all(v)),end(v)); }↵
tcTU> void erase(T& t, const U& u) { // don't erase element that doesn't exist from (multi)set↵
auto it = t.find(u); assert(it != end(t));↵
t.erase(it); }↵
↵
// use like sumv(all(dat))↵
template<class ForwardIt>↵
auto sumv(ForwardIt first, ForwardIt last)↵
{↵
/**↵
Careful: accumulation in int could overflow.↵
Therefore, make `out` an ll if the data is any integer type.↵
Otherwise, out is the same type as the data.↵
*/↵
typename std::conditional<↵
std::is_integral<typename std::iterator_traits<ForwardIt>::value_type>::value,↵
ll,↵
typename std::iterator_traits<ForwardIt>::value_type↵
>::type out {};↵
for (; first != last; ++first) {↵
out += *first;↵
}↵
return out;↵
}↵
template<class T> auto sumv(T&& data) {return sumv(all(data));}↵
template<class T> auto max_element(T&& data) {return *max_element(all(data));}↵
template<class T> auto min_element(T&& data) {return *min_element(all(data));}↵
↵
↵
#define tcTUU tcT, class ...U↵
↵
inline namespace Helpers {↵
// is_readable↵
tcT, class = void> struct is_readable : false_type {};↵
tcT> struct is_readable<T,↵
typename std::enable_if_t<↵
is_same_v<decltype(cin >> declval<T&>()), istream&>↵
>↵
> : true_type {};↵
tcT> constexpr bool is_readable_v = is_readable<T>::value;↵
↵
// is_printable↵
// // https://nafe.es/posts/2020-02-29-is-printable/↵
tcT, class = void> struct is_printable : false_type {};↵
tcT> struct is_printable<T,↵
typename std::enable_if_t<↵
is_same_v<decltype(cout << declval<T>()), ostream&>↵
>↵
> : true_type {};↵
tcT> constexpr bool is_printable_v = is_printable<T>::value;↵
↵
↵
tcT> typename enable_if<!is_iterable_v<T> && !is_tuplelike_v<T>, void>::type increment_one(T& x, int inc) {x += inc;}↵
tcT> typename enable_if<is_tuplelike_v<T>, void>::type increment_one(T& t, int inc);↵
tcT> typename enable_if<is_iterable_v<T>, void>::type increment_one(T& t, int inc) { for(auto&& x : t) {increment_one(x, inc);} }↵
↵
template<class T, size_t k>↵
void increment_one_tuplehelper(T& t, int inc) {↵
increment_one(get<k>(t), inc);↵
if constexpr (k < tuple_size_v<T> - 1) {↵
increment_one_tuplehelper<T, k+1>(t, inc);↵
}↵
}↵
tcT> typename enable_if<is_tuplelike_v<T>, void>::type increment_one(T& t, int inc) {↵
increment_one_tuplehelper<T,0>(t, inc);↵
}↵
↵
void increment() {} // add one to each, for output. BE CAREFUL TO UNDO MODIFICATIONS↵
tcTUU> void increment(T& t, U&... u) { increment_one(t,+1); increment(u...); }↵
void decrement() {} // subtract one from each, for input. MODIFICATION IS THE GOAL↵
tcTUU> void decrement(T& t, U&... u) { increment_one(t,-1); decrement(u...); }↵
}↵
↵
inline namespace Input {↵
tcT> constexpr bool needs_input_v = !is_readable_v<T> && is_iterable_v<T>;↵
↵
tcTUU> void re(T& t, U&... u);↵
tcTU> void re(pair<T,U>& p); // pairs↵
↵
// re: read↵
tcT> typename enable_if<is_readable_v<T>,void>::type re(T& x) { cin >> x; } // default↵
tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; } // complex↵
tcT> typename enable_if<needs_input_v<T>,void>::type re(T& i); // ex. vectors, arrays↵
tcTU> void re(pair<T,U>& p) { re(p.first,p.second); }↵
template<class A,class B,class C> void re(tuple<A,B,C>& t) {auto& [a,b,c]=t; re(a,b,c);}↵
template<class A,class B,class C, class D> void re(tuple<A,B,C,D>& t) {auto& [a,b,c,d]=t; re(a,b,c,d);}↵
template<class A,class B,class C, class D, class E> void re(tuple<A,B,C>& t) {auto& [a,b,c,d,e]=t; re(a,b,c,d,e);}↵
template<class A,class B,class C, class D, class E, class F> void re(tuple<A,B,C>& t) {auto& [a,b,c,d,e,f]=t; re(a,b,c,d,e,f);}↵
tcT> typename enable_if<needs_input_v<T>,void>::type re(T& i) {↵
each(x,i) re(x); }↵
tcTUU> void re(T& t, U&... u) { re(t); re(u...); } // read multiple↵
↵
// rv: resize and read vectors↵
void rv(size_t) {}↵
tcTUU> void rv(size_t N, V<T>& t, U&... u);↵
template<class...U> void rv(size_t, size_t N2, U&... u);↵
tcTUU> void rv(size_t N, V<T>& t, U&... u) {↵
t.resize(N); re(t);↵
rv(N,u...); }↵
template<class...U> void rv(size_t, size_t N2, U&... u) {↵
rv(N2,u...); }↵
void rv1(size_t) {}↵
tcTUU> void rv1(size_t N, V<T>& t, U&... u) {↵
t.resize(N); re(t); for(auto& x : t) decrement(x);↵
rv1(N,u...); }↵
↵
↵
// dumb shortcuts to read in ints↵
#define ints(...) int __VA_ARGS__; re(__VA_ARGS__);↵
#define int1(...) ints(__VA_ARGS__); decrement(__VA_ARGS__);↵
#define chars(...) char __VA_ARGS__; re(__VA_ARGS__);↵
#define lls(...) ll __VA_ARGS__; re(__VA_ARGS__);↵
#define ll1(...) lls(__VA_ARGS__); decrement(__VA_ARGS__);↵
#define strings(...) string __VA_ARGS__; re(__VA_ARGS__);↵
}↵
↵
inline namespace ToString {↵
tcT> constexpr bool needs_output_v = !is_printable_v<T> && is_iterable_v<T>;↵
↵
// ts: string representation to print↵
tcT> typename enable_if<is_printable_v<T>,str>::type ts(T v) {↵
stringstream ss; ss << fixed << setprecision(15) << v;↵
return ss.str(); } // default↵
tcT> str bit_vec(T t) { // bit vector to string↵
str res = "{"; F0R(i,sz(t)) res += ts(t[i]);↵
res += "}"; return res; }↵
str ts(V<bool> v) { return bit_vec(v); }↵
template<size_t SZ> str ts(bitset<SZ> b) { return bit_vec(b); } // bit vector↵
tcTU> str ts(pair<T,U> p); // pairs↵
tcT> typename enable_if<needs_output_v<T>,str>::type ts(T v); // vectors, arrays↵
tcTU> str ts(pair<T,U> p) { return "("+ts(p.first)+", "+ts(p.second)+")"; }↵
tcT> typename enable_if<is_iterable_v<T>,str>::type ts_sep(T v, str sep) {↵
// convert container to string w/ separator sep↵
bool fst = 1; str res = "";↵
for (const auto& x: v) {↵
if (!fst) res += sep;↵
fst = 0; res += ts(x);↵
}↵
return res;↵
}↵
tcT> typename enable_if<needs_output_v<T>,str>::type ts(T v) {↵
return "{"+ts_sep(v,", ")+"}"; }↵
↵
// for nested DS↵
template<int, class T> typename enable_if<!needs_output_v<T>,vs>::type↵
ts_lev(const T& v) { return {ts(v)}; }↵
template<int lev, class T> typename enable_if<needs_output_v<T>,vs>::type↵
ts_lev(const T& v) {↵
if (lev == 0 || !sz(v)) return {ts(v)};↵
vs res;↵
for (const auto& t: v) {↵
if (sz(res)) res.back() += ",";↵
vs tmp = ts_lev<lev-1>(t);↵
res.insert(end(res),all(tmp));↵
}↵
F0R(i,sz(res)) {↵
str bef = " "; if (i == 0) bef = "{";↵
res[i] = bef+res[i];↵
}↵
res.back() += "}";↵
return res;↵
}↵
}↵
↵
inline namespace Output {↵
template<class T, size_t k>↵
void tsish_tuplehelper(T& t, string& out) {↵
out += ts(get<k>(t)); out.push_back(' ');↵
if constexpr (k < tuple_size_v<T> - 1) { tsish_tuplehelper<T, k+1>(t, out); }↵
}↵
tcT> typename enable_if<is_tuplelike_v<T>, string>::type tsish(T& t) {↵
string out; tsish_tuplehelper<T,0>(t, out); out.pop_back(); return out;↵
}↵
tcT> typename enable_if<!is_tuplelike_v<T>, string>::type tsish(T& t) { return ts(t); }↵
↵
template<class T> void pr_sep(ostream& os, str, const T& t) { os << tsish(t); }↵
template<class T, class... U> void pr_sep(ostream& os, str sep, const T& t, const U&... u) {↵
pr_sep(os,sep,t); os << sep; pr_sep(os,sep,u...); }↵
template<class T> void pr_sep1(ostream& os, str, T& t) { increment(t); os << tsish(t); decrement(t); }↵
template<class T, class... U> void pr_sep1(ostream& os, str sep, T& t, U&... u) {↵
pr_sep1(os,sep,t); os << sep; pr_sep1(os,sep,u...); }↵
// print w/ no spaces↵
template<class ...T> void pr(const T&... t) { pr_sep(cout,"",t...); }↵
// print w/ spaces, end with newline↵
void ps() { cout << "\n"; }↵
template<class ...T> void ps(const T&... t) { pr_sep(cout," ",t...); ps(); }↵
void ps1() { cout << "\n"; }↵
template<class ...T> void ps1(T&... t) { pr_sep1(cout," ",t...); ps1(); }↵
void pso() {}↵
template<class ...T> void pso(const T&... t) { pr_sep(cout," ",t...); pso(); }↵
void pso1() {}↵
template<class ...T> void pso1(T&... t) { pr_sep1(cout," ",t...); pso1(); }↵
↵
template<class T>↵
void pv(T& dat) {bool f=1; for(auto&& x : dat) {if (!f) {cout<<' ';} f=0; cout << tsish(x);} cout<<'\n';}↵
template<class T>↵
void pv1(T& dat) {bool f=1; increment(dat); for(auto&& x : dat) {if (!f) {cout<<' ';} f=0; cout << tsish(x);} cout<<'\n'; decrement(dat);}↵
template<class T>↵
void pvn(T& dat) {bool f=1; for(auto&& x : dat) {if (!f) {cout<<'\n';} f=0; cout << tsish(x);} cout<<'\n';}↵
template<class T>↵
void pvn1(T& dat) {bool f=1; increment(dat); for(auto&& x : dat) {if (!f) {cout<<'\n';} f=0; cout << tsish(x);} cout<<'\n'; decrement(dat);}↵
// * Remove debug code; I'll use the tourist+me amalgamation instead.↵
↵
#ifndef _OPENMP↵
const clock_t beg = clock();↵
#define dbg_time() dbg((db)(clock()-beg)/CLOCKS_PER_SEC)↵
db TIME() {return (db)(clock()-beg)/CLOCKS_PER_SEC;}↵
#else↵
const db beg = omp_get_wtime();↵
db TIME() {return omp_get_wtime() - beg;}↵
#endif↵
void flush() {std::cout << std::flush;}↵
}↵
↵
inline namespace FileIO {↵
void setIn(str s) { if ( !freopen(s.c_str(),"r",stdin) ) assert(false); }↵
void setOut(str s) { if ( freopen(s.c_str(),"w",stdout) ) assert(false); }↵
void setIO(str s = "") {↵
cin.tie(0)->sync_with_stdio(0); // unsync C / C++ I/O streams↵
cout.tie(0);↵
cin.exceptions(cin.failbit);↵
// throws exception when do smth illegal↵
// ex. try to read letter into int↵
if (sz(s)) setIn(s+".in"), setOut(s+".out"); // for old USACO↵
}↵
}↵
↵
#pragma region // debugging↵
// * debug setup mostly stolen from tourist. https://codeforces.net/contest/1540/submission/120602670↵
// * dcclyde added line numbers, colors, probably some other stuff.↵
↵
template <typename A, typename B>↵
string to_string(pair<A, B> p);↵
↵
template <typename X>↵
typename enable_if<is_tuplelike_v<X>, string>::type to_string(X p);↵
↵
string to_string(const string& s) {↵
return '"' + s + '"';↵
}↵
↵
string to_string(char c) {↵
return "'" + string(1, c) + "'";↵
}↵
↵
string to_string(const char* s) {↵
return to_string((string) s);↵
}↵
↵
string to_string(bool b) {↵
return (b ? "true" : "false");↵
}↵
↵
string to_string(vector<bool> v) {↵
bool first = true;↵
string res = "{";↵
for (int i = 0; i < static_cast<int>(v.size()); i++) {↵
if (!first) {↵
res += ", ";↵
}↵
first = false;↵
res += to_string(v[i]);↵
}↵
res += "}";↵
return res;↵
}↵
↵
template <size_t N>↵
string to_string(bitset<N> v) {↵
string res = "";↵
for (size_t i = 0; i < N; i++) {↵
res += static_cast<char>('0' + v[i]);↵
}↵
return res;↵
}↵
↵
template <typename A>↵
typename enable_if<is_iterable_v<A>, string>::type to_string(A v) {↵
bool first = true;↵
string res = "{";↵
for (const auto &x : v) {↵
if (!first) {↵
res += ", ";↵
}↵
first = false;↵
res += to_string(x);↵
}↵
res += "}";↵
return res;↵
}↵
↵
template<typename T>↵
V<T> pqueue_to_iterable(priority_queue<T> PQ) { // PASS BY VALUE!↵
V<T> working;↵
while (!PQ.empty()) {working.push_back(PQ.top()); PQ.pop();}↵
reverse(all(working));↵
return working;↵
}↵
↵
template <typename T>↵
string to_string(priority_queue<T>&& PQ) {↵
return to_string(pqueue_to_iterable(PQ));↵
}↵
↵
template <typename A, typename B>↵
string to_string(pair<A, B> p) {↵
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";↵
}↵
↵
template<class T, size_t k>↵
void to_string_tuplehelper(string& out, T& t) {↵
out += ", " + to_string(get<k>(t));↵
if constexpr (k < tuple_size_v<T> - 1) {↵
to_string_tuplehelper<T, k+1>(out, t);↵
}↵
}↵
template <typename X>↵
typename enable_if<is_tuplelike_v<X>, string>::type to_string(X p) {↵
string out = "(" + to_string(get<0>(p));↵
to_string_tuplehelper<X, 1>(out, p);↵
out += ")";↵
return out;↵
}↵
↵
↵
// helpers for debugging complicated objects↵
template<class T, class S>↵
string print_details_helper_general(T&& q, S f, ll MAX) {↵
string out;↵
ll ctr = 0;↵
bool trimmed = false;↵
for ( auto&& x : q ) {↵
if (ctr == MAX) {trimmed = true; break;}↵
out.push_back('\t');↵
out += to_string(ctr) + ":\t" + to_string(f(x)) + "\n";↵
++ctr;↵
}↵
// string prefix = "\tlen " + to_string(q.size());↵
string prefix = "";↵
if (trimmed) {↵
// prefix += ", trimmed to " + to_string(MAX);↵
out.pop_back();↵
out = prefix + "\n" + out + "\n\t... (full length " + to_string(q.size()) + ")";↵
out.push_back('\n');↵
} else {↵
out = prefix + "\n" + out;↵
}↵
return out;↵
}↵
↵
#define PDH_DEFAULT_MAX 10'000↵
template<class T>↵
string print_details_helper(T&& q, ll MAX=PDH_DEFAULT_MAX) {↵
return print_details_helper_general(q, [&](auto x) {return x;}, MAX);↵
}↵
string print_details_helper(V<bool>&& q, ll MAX=PDH_DEFAULT_MAX) {↵
return print_details_helper_general(q, [&](auto x) {return static_cast<bool>(x);}, MAX);↵
}↵
template<class T>↵
string print_details_helper(priority_queue<T>&& PQ, ll MAX=PDH_DEFAULT_MAX) {↵
return print_details_helper(pqueue_to_iterable(PQ), MAX);↵
}↵
#define pdh print_details_helper↵
↵
template<class T, class S>↵
string print_details_helper_func(T&& q, S f, ll MAX=PDH_DEFAULT_MAX) {↵
return print_details_helper_general(q, f, MAX);↵
}↵
template<class S>↵
string print_details_helper_func(V<bool>&& q, S f, ll MAX=PDH_DEFAULT_MAX) {↵
return print_details_helper_general(q, [&](auto x) {return f(static_cast<bool>(x));}, MAX);↵
}↵
template<class T, class S>↵
string print_details_helper_func(priority_queue<T>&& PQ, S f, ll MAX=PDH_DEFAULT_MAX) {↵
return print_details_helper_general(pqueue_to_iterable(PQ), f, MAX);↵
}↵
#define pdh_func print_details_helper_func↵
#define pdhf print_details_helper_func↵
↵
↵
↵
template<class T>↵
string print_tsv_helper(T&& q) {↵
string out = "\n";↵
for ( auto&& x : q ) {↵
bool first = true;↵
for ( auto& v : x ) {↵
if ( !first ) {↵
out += '\t';↵
}↵
out += to_string(v);↵
first = false;↵
}↵
out += '\n';↵
}↵
return out;↵
}↵
#define pth print_tsv_helper↵
↵
↵
void debug_out() {}↵
↵
template <typename Head, typename... Tail>↵
void debug_out(Head H, Tail... T) {↵
// mostly no difference unless there's a background color.↵
// std::cerr << to_string(H) << " ";↵
// debug_out(T...);↵
std::cerr << ' ' << to_string(H) << ' ';↵
if (sizeof...(T)) {↵
std::cerr << " ";↵
debug_out(T...);↵
}↵
}↵
↵
// #define BOLD_MAYBE "" // NOT bold↵
#define BOLD_MAYBE ";1" // YES bold↵
↵
#define OUT_RESET "\033[0m"↵
#define OUT_BOLD "\033[;1m"↵
#define OUT_RED "\033[31" "m"↵
#define OUT_CYAN "\033[36" BOLD_MAYBE "m"↵
// #define OUT_GREEN "\033[32" << BOLD_MAYBE << "m"↵
#define OUT_GREEN "\033[32" "m"↵
#define OUT_BLUE "\033[34" BOLD_MAYBE "m"↵
#define OUT_WHITE "\033[97" "m"↵
#define OUT_MARK "\033[0;30;41;1m"↵
#define OUT_YELLOW "\033[33" BOLD_MAYBE "m"↵
#define OUT_PURPLE "\033[35" BOLD_MAYBE "m"↵
↵
↵
#define dbgc(...) ;↵
#define dbg(...) ;↵
#define el ;↵
#define dbgBold(...) ;↵
#define dbgcBold(...) ;↵
#define dbgY(...) ;↵
#define dbgcY(...) ;↵
#define dbgP(...) ;↵
#define dbgcP(...) ;↵
#define dbgR(...) ;↵
#define dbgcR(...) ;↵
#define dbgB(...) ;↵
#define dbgcB(...) ;↵
#define dbgW(...) ;↵
#define dbgcW(...) ;↵
#define dbg_only(...) ;↵
#define local_run (false)↵
#ifdef DCCLYDE_LOCAL↵
// dbgc = "debug with comment"↵
#define dbgcbase(A, B, C, ARGTEXT, ...) std::cout << std::flush; \↵
std::cerr << OUT_BOLD << B \↵
<< std::right << setw(20) << C << ' ' \↵
<< OUT_RESET << OUT_BOLD << OUT_RED \↵
<< std::right << setw(7) << __LINE__ \↵
<< OUT_BOLD << " : " << OUT_RESET \↵
<< A << "[ " << ARGTEXT << " ]" \↵
<< OUT_BOLD << " : " << OUT_RESET \↵
<< B, debug_out(__VA_ARGS__); \↵
std::cerr << OUT_RESET << std::endl;↵
↵
#undef dbgBold↵
#define dbgBold(...) dbgcbase(OUT_GREEN, OUT_MARK, "", #__VA_ARGS__, __VA_ARGS__)↵
#undef dbgcBold↵
#define dbgcBold(MSG, ...) dbgcbase(OUT_GREEN, OUT_MARK, MSG, #__VA_ARGS__, __VA_ARGS__)↵
↵
#undef dbg↵
#define dbg(...) dbgcbase(OUT_GREEN, OUT_CYAN, "", #__VA_ARGS__, __VA_ARGS__)↵
#undef dbgc↵
#define dbgc(MSG, ...) dbgcbase(OUT_GREEN, OUT_CYAN, MSG, #__VA_ARGS__, __VA_ARGS__)↵
↵
#undef dbgY↵
#define dbgY(...) dbgcbase(OUT_GREEN, OUT_YELLOW, "", #__VA_ARGS__, __VA_ARGS__)↵
#undef dbgcY↵
#define dbgcY(MSG, ...) dbgcbase(OUT_GREEN, OUT_YELLOW, MSG, #__VA_ARGS__, __VA_ARGS__)↵
↵
#undef dbgP↵
#define dbgP(...) dbgcbase(OUT_GREEN, OUT_PURPLE, "", #__VA_ARGS__, __VA_ARGS__)↵
#undef dbgcP↵
#define dbgcP(MSG, ...) dbgcbase(OUT_GREEN, OUT_PURPLE, MSG, #__VA_ARGS__, __VA_ARGS__)↵
↵
#undef dbgR↵
#define dbgR(...) dbgcbase(OUT_GREEN, OUT_RED, "", #__VA_ARGS__, __VA_ARGS__)↵
#undef dbgcR↵
#define dbgcR(MSG, ...) dbgcbase(OUT_GREEN, OUT_RED, MSG, #__VA_ARGS__, __VA_ARGS__)↵
↵
#undef dbgB↵
#define dbgB(...) dbgcbase(OUT_GREEN, OUT_BLUE, "", #__VA_ARGS__, __VA_ARGS__)↵
#undef dbgcB↵
#define dbgcB(MSG, ...) dbgcbase(OUT_GREEN, OUT_BLUE, MSG, #__VA_ARGS__, __VA_ARGS__)↵
↵
#undef dbgW↵
#define dbgW(...) dbgcbase(OUT_GREEN, OUT_WHITE, "", #__VA_ARGS__, __VA_ARGS__)↵
#undef dbgcW↵
#define dbgcW(MSG, ...) dbgcbase(OUT_GREEN, OUT_WHITE, MSG, #__VA_ARGS__, __VA_ARGS__)↵
↵
#undef dbg_only↵
#define dbg_only(...) __VA_ARGS__;↵
↵
#undef el↵
#define el std::cerr << std::flush; std::cerr << '\n'; // in my head I say "error line"↵
↵
#undef local_run↵
#define local_run (true)↵
#endif↵
#pragma endregion↵
↵
#define timebomb(a) dbg_only({static int _bomb = 0; if(++_bomb>=a) {dbgc("boom!", a);exit(1);}});↵
↵
#define YES ps("YES");↵
#define NO ps("NO");↵
#define Yes ps("Yes");↵
#define No ps("No");↵
#define IMPOSSIBLE ps("IMPOSSIBLE");↵
↵
const ll INF_ll = ll(2e18) + 1;↵
const int INF_i = int(2e9) + 1;↵
↵
// const int MOD = 1'000'000'007;↵
// const int MOD = 998'244'353;↵
↵
#pragma endregion↵
↵
// ! ---------------------------------------------------------------------------↵
↵
↵
↵
↵
↵
↵
void solve() {↵
lls(N);↵
V<ll> dat;↵
rv(N, dat);↵
dbgR(N, dat);↵
el;↵
↵
// ! Read the sample cases AND EXPLANATIONS before writing code for nontrivial problems!↵
↵
↵
↵
return;↵
}↵
↵
// ! Do something instead of nothing: write out small cases, code bruteforce↵
// ! Check bounds even if I have a solution - are they letting through simpler versions?↵
// ! If stuck on a "should be easy" problem for 10 mins, reread statement, check bounds↵
↵
#define PROBLEM_STYLE CF↵
// #define SINGLE_CASE // ! Uncomment this for one-case problems.↵
#pragma region // main↵
#if PROBLEM_STYLE == CF || PROBLEM_STYLE == GCJ↵
int main() {↵
setIO();↵
↵
int T = 1;↵
#ifndef SINGLE_CASE↵
dbgc("loading num cases!!!"); std::cin >> T;↵
#endif↵
for ( int CASE = 1 ; CASE <= T ; ++CASE ) {↵
#if PROBLEM_STYLE == GCJ↵
cout << "Case #" << CASE << ": ";↵
#endif↵
el;↵
#ifndef DCCLYDE_BRUTEFORCE↵
dbgcBold("CASE" , CASE );↵
solve();↵
#else↵
dbgcBold("brute force" , CASE );↵
brute();↵
#endif↵
}↵
dbgR(TIME());↵
return 0;↵
}↵
#else↵
// PROBLEM_STYLE is CLEAN or undefined.↵
int main() {↵
#ifdef _OPENMP↵
ll num_procs = omp_get_num_procs();↵
ll max_threads = omp_get_max_threads();↵
dbgBold(num_procs, max_threads);↵
omp_set_num_threads(num_procs - 4);↵
#endif↵
solve();↵
dbgR(TIME());↵
return 0;↵
}↵
#endif↵
#pragma endregion↵
~~~~~↵
↵
</spoiler>#### Links↵
* [Current template.cpp](https://github.com/dcclyde/coding_puzzles/blob/master/templates/template.cpp) — includes updates made after this blog was posted. This is the recommended version for most people.↵
* [Minimal version with debug printouts only](https://github.com/dcclyde/coding_puzzles/blob/master/templates/dbg_demo.cpp) — Stripped-down version that compiles faster while still providing the `dbg()` setup, which is IMO the most novel and cool feature in the template. Recommended if your computer is too slow to compile the main version. But please try the precompiled headers trick first, since that helps the compile times a lot!↵
↵
Specific cool tricks in the template↵
------------------↵
### Debug printouts↵
Here's an output screenshot:↵
↵
↵
...and here's the code I used↵
↵
[cut]↵
↵
:↵
↵
~~~~~↵
void solve() {↵
ll a = 14; double b = -3e-2; char c = '@'; string s = "Test String";↵
vector<ll> q = {1, 6, 4, 3, 5, 3, 1};↵
dbg(a, b, c, "", s, q);↵
dbgc("show this on left", make_pair(a, c)); // dbgc = "debug with 1st arg as comment"↵
dbgcP("diff colors", a, b); // uppercase letters change the color; all terminal colors are available↵
dbgc("expressions work too", 2*b, gcd(a, a+4));↵
el; // empty line↵
↵
// complex/nested data structures work too.↵
map<pair<ll,ll>, V<string>> dat = {↵
{{3, 5}, {"abc", "def"}},↵
{{4, -1}, {"apple", "peach", "banana"}},↵
{{-5, 0}, {"tourist", "jiangly", "um_nik", "slime", "ksun48"}}↵
};↵
dbgY(dat);↵
// that may be pretty messy to read all on one line though, so we can use:↵
dbg(pdh(dat));↵
el;↵
↵
// show how "regular output" lines look visibly different from dbg() lines.↵
cout << a << ' ' << b << ' ' << c << '\n';↵
↵
// what if we have a big object and we want to "get the idea" of its contents↵
// without printing the whole thing?↵
vector<pll> vbig; FOR(k, 0, 100) {vbig.emplace_back(k, -k*k);}↵
dbgR(pdh(vbig, 10)); // short for "print_details_helper"↵
↵
el;↵
// Advanced: pdhf lets me specify a function, so f(x) will be printed for each x in the structure.↵
dbg(pdhf(vbig, [&](auto x){return x.second;}, 5)); // pdhf = "print_details_helper_func"↵
↵
dbgcBold("done!");↵
return;↵
}↵
~~~~~↵
↵
#### Summary of key dbg() features↵
↵
* `dbg(a, b, c)` prints line number, exact text you passed in, and the values of all those variables/expressions/objects. Optional `dbgc` version uses the first argument as a marker or comment, which is placed to the left. All printouts are indented to keep them visually separate from the normal outputs to cout.↵
* Different color options so you can easily see which printouts came from which dbg() call without comparing line numbers every time. Default color is cyan if you just use dbg(); specify other colors with dbgP (purple), dbgY (yellow), and so on. All the ANSI terminal colors are provided except black; see the template code for the full list. dbgBold provides a special colorset with a bright red background.↵
* Handles pairs, tuples, and STL data structures including arbitrary nesting.↵
* **All `dbg()` and `el` stuff is removed at preprocessor stage if we didn't pass flag -DDCCLYDE_LOCAL when compiling.** That means I don't need to bother commenting out these lines before submitting to online judges. (That's a big upgrade from regular cerr printouts, which won't cause WA at most judges but can easily cause TLE.)↵
* pdh ("print details helper") functionality prints one entry per line; useful if we're printing a complex object since printing on one line can be hard to visually process. Template includes some extensions, demod above.↵
↵
#### Real-life example↵
The demo above may make it seem like the different colors are just visually noisy instead of useful. Here's an example of how I'd use the printouts in "real life" on a recent div2 C. (OK, in a real competition I wouldn't use this many comments or printouts unless the implementation was more complicated, but I want to make the example understandable by everyone who sees this blog.)↵
↵
[Submission link](https://codeforces.net/contest/1720/submission/169037463)↵
↵
<spoiler summary="Just the solve() function">↵
~~~~~↵
/**↵
Idea: After the very first step, it should always be possible to remove↵
exactly one 1 per step. So the plan is:↵
1) Choose the first step to remove smallest possible number of 1s↵
2) Answer will be 1 + num ones remaining after the first step↵
*/↵
↵
void solve() {↵
lls(R, C);↵
V<string> dat; rv(R, dat);↵
dbgR(MP(R,C), dat); // I usually dbg() the inputs so I can confirm I read them correctly.↵
el;↵
↵
// Step 1: Find smallest possible number of 1s deleted in first step.↵
ll fewest_deleted = 3;↵
FOR(r, 0, R-1) FOR(c, 0, C-1) {↵
ll ones_in_2x2 = 0;↵
FOR(j, 0, 2) FOR(k, 0, 2) {↵
if (dat[r + j][c + k] == '1') {++ones_in_2x2;}↵
}↵
ll ones_deleted_here = max(ones_in_2x2 - 1, 0LL);↵
ckmin(fewest_deleted, ones_deleted_here);↵
dbg(MP(r, c), ones_in_2x2, "", ones_deleted_here, fewest_deleted);↵
}↵
↵
ll ones_total = 0;↵
FOR(r, 0, R) FOR(c, 0, C) {↵
if (dat[r][c] == '1') {++ones_total;}↵
}↵
↵
ll out;↵
if (fewest_deleted == 0) {↵
// It's initially possible to pick an L shape that doesn't hit any 1s.↵
// That isn't a legal move though.↵
out = ones_total;↵
} else {↵
out = 1 + (ones_total - fewest_deleted);↵
}↵
dbgY(fewest_deleted, ones_total, out);↵
ps(out);↵
return;↵
}↵
~~~~~↵
</spoiler>↵
↵
Here's what I see when I run the sample test cases locally:↵
↵
↵
For short solutions, I normally just use random different colors for each printout. In more complicated programs I try to somewhat organize my color usage. For example, I sometimes use: Red = print out inputs as soon as I read them to confirm I loaded them correctly; Yellow = higher-level info, maybe printing out results of a big intermediate step or printing status once per outer loop cycle; Cyan (default) = less important stuff, or printouts coming from inside a work loop; Purple = printouts from inside a function call or nested loop.↵
↵
↵
### "Unhackable" and faster unordered_map and unordered_set replacements↵
`unordered_map` and `unordered_set` are notoriously hackable and so generally should not be used on Codeforces; see [classic blog post](https://codeforces.net/blog/entry/62393). Also, they are usually around 5x slower than the alternative `gp_hash_table`; see [another blog](https://codeforces.net/blog/entry/60737).↵
My template defines replacements `umap` and `uset` which fix both of those problems, basically by implementing the recommendations from those linked posts. Bonus: my versions also happily hash arbitrary pairs, tuples, or iterable STL objects. I make it easy to toggle which implementation is used by `umap` and `uset`. Caveat: pairs and tuples work well, but hashing more complex stuff like `std::vector`s can often lead to TLE.↵
↵
### Precompiled header↵
When compiling on judge server, the template uses a few includes:↵
↵
~~~~~↵
#include <tgmath.h>↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
~~~~~↵
When compiling locally, the template instead just uses `#include "/home/dcclyde/puzzles/code/templates/superheader.h"`. That's because [superheader.h](https://github.com/dcclyde/coding_puzzles/blob/master/templates/superheader.h) is a local file that has all those same includes, except I've set up a precompiled header which makes my compilations several seconds faster. The difference is approximately 6s -> 1.5s on my older laptop, but only 2.5s -> 1.0s on my current machine. Basically, depending on your computer this hack might be pretty important for keeping the compile time manageable despite all the template's #includes and #defines.↵
↵
I'm not recommending a specific guide for how to build a precompiled header because the correct steps may depend on your OS and machine configuration. However, I was able to make it work pretty quickly once I searched Google for `precompiled header C++ gcc ubuntu`, so I hope you'll have good luck here too.↵
↵
### I/O shortcuts↵
These aren't a huge deal, but they do save me from typing the same annoying lines of code in every problem.↵
↵
~~~~~↵
// INPUT↵
lls(R, C); // declare and read from stdin two long longs called R and C. Can also use ints, chars, strings to read those other datatypes.↵
ll1(a, b); // same as lls except decrement the variables by 1 after reading; useful when problems give 1-indexed inputs but I want to work with 0-indexed↵
V<int> q;↵
rv(R, q); // resize q to size R and then fill all entries from stdin↵
rv1(R, q); // same as rv except decrement by 1 after reading↵
↵
// OUTPUT↵
ps(a, b, R); // same as cout << a << ' ' << b << ' ' << R << '\n';↵
ps1(a, b); // same as cout << a+1 << ' ' << b+1 << '\n'; notice we ADD 1 when outputting.↵
pv(q); // output space-separated all on one line, with newline at the end↵
pv1(q); // same as pv but add 1 to each output↵
~~~~~↵
↵
Compilation and usage notes↵
------------------↵
Sample compile+run command: `g++ --std=c++20 -DDCCLYDE_LOCAL template.cpp && ./a.out`↵
↵
The template requires C++17 or higher. It also works better on 64-bit systems, just because lately I use `long long` instead of `int` by default due to the negligible speed difference on modern machines including online judges.↵
↵
I submit to Codeforces using `GNU C++20 (64)` and AtCoder using `C++ (GCC 9.2.1)`.↵
↵
The template will be nicer to use if your editor has a shortcut for code folding between `#pragma region` and `#pragma endregion`. I use VS Code and I have keyboard shortcuts bound for "Fold All Regions" and "Unfold All Regions". I also use the "Better Comments" extension, which explains why some of the comments have special flags at the start (they show up in different colors on my screen).↵
↵
↵
What a good template can (and can't) do for you↵
------------------↵
↵
The main things I think a template can help with are:↵
↵
1. Reduce repetitive typing: save 1-5 minutes on every problem by using small prewritten functions/macros for I/O, binary searches, etc. On CF this is pretty important, since getting problems A and B in 1-3 mins instead of 5-10 minutes helps my rating a lot. Less code typed for each problem also means less chances for typos, so it becomes a little easier to code correctly.↵
2. Make debugging faster and easier: even when the intermediate steps are producing complicated data structures, the dbg() functionality lets me track down unexpected/buggy behaviour very fast. Before I had this template I used to code new debug printouts on every problem, and coding the printouts would distract me from focusing fully on thinking through my logic to actually find the mistake.↵
↵
Overall, the template makes it way easier and faster for me to go from "having the right idea" to "getting AC". I always feel frustrated if I think of the correct plan but don't end up getting AC. My template makes the implementation process much smoother which helps me feel motivated and confident during contests and training, especially with new ideas/algorithms that I'm not very comfortable with.↵
↵
Unfortunately, a template can't help you have the right solution ideas in the first place. For that you can instead read the thousands of blogs that already exist with more general advice about how to train ;)↵
↵
I've read some CF blogs where strong coders say that a good coder shouldn't rely on a long template. I also see a very wide variety in template lengths even among LGMs. Overall, I think template size can just be personal preference, and you should experiment to see what feels best to you.↵
↵
Special thanks↵
------------------↵
↵
When creating my template, I started from [user:benq,2022-08-20]'s TemplateLong.cpp ([GitHub](https://github.com/bqi343/USACO/blob/master/Implementations/content/contest/TemplateLong.cpp)). My version is very different, but I still use lots of minor convenience features from his template.↵
↵
The dbg() functionality is my heavily modified version of ideas stolen from [user:tourist,2022-08-20] and [user:Livw08,2022-08-20], see [blog](https://codeforces.net/blog/entry/68809).↵
↵
Of course I've taken ideas or code from a ton of other sources too, mostly other CF blogs. Thanks everyone!↵
↵
Questions, suggestions, advice?↵
------------------↵
I'm very interested to hear to advice about how to accomplish the same things in a better way, or feature requests that would make the template easier to use or more helpful, or even just random questions about why I did things a certain way. Some of my "weird" decisions are made on purpose to get around non-obvious issues that I didn't discuss in this blog, and others may be just because I'm clumsy with some of the tools I'm using here, so even asking "silly" questions can be useful — either I'll explain something you didn't see, or I'll learn something from your idea.↵
↵
This is my first blog post after using Codeforces off and on for 6+ years, so I'm also interested to hear advice about how to make a more useful blog next time.
==================↵
↵
Use [this template](https://github.com/dcclyde/coding_puzzles/blob/master/templates/template.cpp) and you'll gain 350 rating right away! OK maybe not, but it has a bunch of cool features I built up while climbing from 1800 to 2150 in February-May of this year, and I bet some of them can be helpful to others too. Please, comment with feedback/suggestions/feature requests about how to make the template more useful :)↵
↵
↵
<spoiler summary="Finally, here's an embedded copy in case someone prefers to see the template without leaving Codeforces.">↵
↵
~~~~~↵
#pragma region↵
#ifdef _OPENMP↵
#include <omp.h>↵
#endif↵
#if defined(DCCLYDE_LOCAL) && __has_include("/home/dcclyde/puzzles/code/templates/superheader.h")↵
#include "/home/dcclyde/puzzles/code/templates/superheader.h"↵
#else↵
#define NDEBUG // don't bother with assertions on the judge server.↵
#include <tgmath.h>↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
#endif↵
using namespace std;↵
using namespace __gnu_pbds;↵
↵
#define CLEAN 0↵
#define CF 1↵
#define GCJ 2↵
↵
using ll = long long;↵
using db = long double; // or double, if TL is tight↵
using str = string; // yay python!↵
↵
// pairs↵
using pi = pair<int,int>;↵
using pl = pair<ll,ll>;↵
using pd = pair<db,db>;↵
//// I'm not used to the defs above.↵
using pii = pair<int,int>;↵
using pll = pair<ll,ll>;↵
using pdd = pair<db,db>;↵
#define mp make_pair↵
#define MP make_pair↵
#define MT make_tuple↵
#define f first↵
#define s second↵
↵
#define tcT template<class T↵
#define tcTU tcT, class U↵
// ^ lol this makes everything look weird but I'll try it↵
tcT> using V = vector<T>;↵
tcT, size_t SZ> using AR = array<T,SZ>;↵
using vi = V<int>;↵
using vb = V<bool>;↵
using vl = V<ll>;↵
using vll = V<ll>;↵
using vd = V<db>;↵
using vs = V<str>;↵
using vpi = V<pii>;↵
using vpii = V<pii>;↵
using vpl = V<pll>;↵
using vpll = V<pll>;↵
using vpd = V<pdd>;↵
↵
// vectors↵
// size(x), rbegin(x), rend(x) need C++17↵
#define sz(x) int((x).size())↵
#define bg(x) begin(x)↵
#define all(x) bg(x), end(x)↵
#define rall(x) x.rbegin(), x.rend()↵
#define sor(x) sort(all(x))↵
#define rsz resize↵
#define ins insert↵
#define pb push_back↵
#define eb emplace_back↵
#define emp emplace↵
#define ft front()↵
#define bk back()↵
↵
//// #define lb lower_bound↵
//// #define ub upper_bound↵
//// tcT> int lwb(V<T>& a, const T& b) { return int(lb(all(a),b)-bg(a)); }↵
//// tcT> int upb(V<T>& a, const T& b) { return int(ub(all(a),b)-bg(a)); }↵
↵
// bitwise ops↵
// also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html↵
constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set bits_set↵
constexpr ll pct(ll x) { return __builtin_popcountll(x); }↵
constexpr int bigbit(int x) { // assert(x >= 0); // make C++11 compatible until USACO updates ...↵
return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x))↵
constexpr int bigbitll(ll x) { // assert(x >= 0); // make C++11 compatible until USACO updates ...↵
return x == 0 ? 0 : 63-__builtin_clzll(x); } // floor(log2(x))↵
constexpr int p2(int x) { return 1<<x; }↵
constexpr int msk2(int x) { return p2(x)-1; }↵
↵
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up↵
ll fdiv(auto a, auto b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down↵
↵
ll powll(ll b, ll e) {↵
ll out = 1;↵
while (e) {↵
if (e&1) {out *= b;}↵
b *= b; e >>= 1;↵
}↵
return out;↵
}↵
ll powmod(ll b, ll e, ll mod) {↵
ll out = 1;↵
while (e) {↵
if (e&1) {out *= b; out %= mod;}↵
b *= b; b %= mod; e >>= 1;↵
}↵
return out;↵
}↵
↵
tcTU> bool ckmin(T& a, const U& b) {↵
return (T)b < a ? a = (T)b, 1 : 0; } // set a = min(a,b)↵
tcTU> bool ckmax(T& a, const U& b) {↵
return a < (T)b ? a = (T)b, 1 : 0; } // set a = max(a,b)↵
↵
int maxi(int a, int b) {return max((int)a, (int)b);}↵
int mini(int a, int b) {return min((int)a, (int)b);}↵
ll maxll(ll a, ll b) {return max((ll)a, (ll)b);}↵
ll minll(ll a, ll b) {return min((ll)a, (ll)b);}↵
↵
↵
template <typename, typename = void>↵
constexpr bool is_iterable_v{};↵
↵
template <typename T>↵
constexpr bool is_iterable_v<↵
T,↵
std::void_t< decltype(std::declval<T>().begin()),↵
decltype(std::declval<T>().end())↵
>↵
> = true;↵
↵
template <typename, typename=void>↵
constexpr bool is_tuplelike_v{};↵
↵
template <typename T>↵
constexpr bool is_tuplelike_v<↵
T,↵
void_t<↵
decltype(std::get<0>(declval<T>())),↵
decltype(std::tuple_size_v<T>)↵
>↵
> = true;↵
↵
// Safe hash maps. See https://codeforces.net/blog/entry/62393↵
struct custom_hash {↵
static uint64_t splitmix64(uint64_t x) {↵
// http://xorshift.di.unimi.it/splitmix64.c↵
x += 0x9e3779b97f4a7c15;↵
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;↵
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;↵
return x ^ (x >> 31);↵
}↵
↵
size_t operator()(uint64_t x) const {↵
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();↵
return splitmix64(x + FIXED_RANDOM);↵
}↵
template<class T, class U>↵
size_t operator()(const pair<T,U>& x) const {↵
uint64_t a = (*this)(x.first);↵
uint64_t b = (*this)(x.second);↵
return a + 3*b;↵
}↵
↵
template<class T, size_t k>↵
void op_tuplehelper(size_t& out, T t) const {↵
out += (*this)(get<k>(t)) * (k+1)*(k+1);↵
if constexpr (k < tuple_size_v<T> - 1) {↵
op_tuplehelper<T, k+1>(out, t);↵
}↵
}↵
template <typename X>↵
typename enable_if<is_tuplelike_v<X>, size_t>::type operator()(const X& t) const {↵
size_t out = 0;↵
op_tuplehelper<X, 0>(out, t);↵
return out;↵
}↵
↵
template <typename A>↵
typename enable_if<is_iterable_v<A>, size_t>::type operator()(const A& v) const {↵
uint64_t out = 0;↵
uint64_t offset = 1;↵
for (const auto& x : v) {↵
uint64_t curr = (*this)(x);↵
out ^= curr * offset;↵
offset *= 3;↵
}↵
return out;↵
}↵
};↵
↵
template<class A, class B> using umap = gp_hash_table<A,B,custom_hash>;↵
// template<class A, class B> using umap = unordered_map<A,B,custom_hash>; // slower?↵
// template<class A, class B> using umap = map<A,B>; // ok for tiny cases?↵
// template<class A, class B> using umap = unordered_map<A,B>; // slower and unsafe?↵
↵
template<class A> using uset = gp_hash_table<A,null_type,custom_hash>;↵
// template<class A> using uset = unordered_set<A, custom_hash>;↵
// template<class A> using uset = set<A>;↵
// template<class A> using uset = unordered_set<A>;↵
↵
#define unordered_map DCCLYDE_REMINDER_DONT_USE_UNPROTECTED_HASH_MAP↵
#define unordered_set DCCLYDE_REMINDER_DONT_USE_UNPROTECTED_HASH_SET↵
↵
↵
// loops↵
#define CONCAT_INNER(a, b) a ## b↵
#define CONCAT(a, b) CONCAT_INNER(a, b)↵
#define FORll(i,a,b) for (ll i = ((ll)a); i < ((ll)b); ++i)↵
#define FORint(i,a,b) for (int i = ((int)a); i < ((int)b); ++i)↵
// #define FOR3(i,a,b) for (int i = (a); i < (b); ++i)↵
#define FOR3(i,a,b) FORll(i,a,b)↵
#define F0R(i,a) FOR(i,0,a)↵
#define FOR2(i,a) FOR(i,0,a)↵
#define ROFll(i,a,b) for (ll i = ((ll)b)-1; i >= ((ll)a); --i)↵
#define ROFint(i,a,b) for (int i = ((int)b)-1; i >= ((int)a); --i)↵
// #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)↵
#define ROF(i,a,b) ROFll(i,a,b)↵
#define R0F(i,a) ROF(i,0,a)↵
#define rep(a) F0R(CONCAT(_,__LINE__),a)↵
#define each(a,x) for (auto& a: x)↵
#define foreach(a,x) each(a,x)↵
↵
#define FOR1(x) for(auto x)↵
#if __cplusplus >= 202002L↵
auto stepped_iota(ll start, ll end, ll step=1) {↵
ll iter_count = cdiv(end-start, step);↵
ckmax(iter_count, 0);↵
return std::ranges::views::iota(0LL, iter_count) |↵
std::ranges::views::transform([=](ll x) { return x * step + start; });↵
}↵
#define FOR4(i,s,e,step) for(auto i : stepped_iota(s, e, step))↵
#else↵
#define FOR4(i,s,e,step) for(ll i = s; i != e && ((i<e) == (s<e)) ; i += step)↵
#endif↵
↵
// just as an example of how to iterate in reverse order↵
// for(auto& x : dat | views::reverse) {}↵
↵
#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME↵
#define FOR(...) GET_MACRO(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)↵
↵
#pragma region // rangeint↵
V<int> rangeint(int start, int end, int inc=1) {↵
V<int> out;↵
if (inc > 0) {↵
for(int curr = start; curr < end; curr += inc) {↵
out.push_back(curr);↵
}↵
return out;↵
} else {↵
for(int curr = start; curr > end; curr += inc) {↵
out.push_back(curr);↵
}↵
return out;↵
}↵
}↵
#pragma endregion↵
↵
// const int MX = 2e5+5;↵
const ll BIG = 1e18; // not too close to LLONG_MAX↵
const db PI = acos((db)-1);↵
//// const int dx[4]{1,0,-1,0}, dy[4]{0,1,0,-1}; // for every grid problem!!↵
vector<pii> stepsOrthogonal = {{1,0},{0,1},{-1,0},{0,-1}};↵
vector<pii> stepsDiagonal = {{1,1},{1,-1},{-1,-1},{-1,1}};↵
vector<pii> steps8dirs = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};↵
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());↵
#pragma region // rng examples↵
// std::uniform_real_distribution<db> rand_dbl(0, 1); // [L, R)↵
// db ard = unif_db(rng);↵
// std::uniform_int_distribution<int> rand_int(1, 2); // inclusive↵
// int ri = rand_int(rng);↵
#pragma endregion↵
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;↵
↵
tcT> ll fstTrue(ll lo, ll hi, T f) {↵
++hi; assert(lo <= hi); // assuming f is increasing↵
while (lo < hi) { // find first index such that f is true↵
ll mid = lo+(hi-lo)/2;↵
f(mid) ? hi = mid : lo = mid+1;↵
}↵
return lo;↵
}↵
tcT> ll lstTrue(ll lo, ll hi, T f) {↵
--lo; assert(lo <= hi); // assuming f is decreasing↵
while (lo < hi) { // find first index such that f is true↵
ll mid = lo+(hi-lo+1)/2;↵
f(mid) ? lo = mid : hi = mid-1;↵
}↵
return lo;↵
}↵
tcT> void remDup(vector<T>& v) { // sort and remove duplicates↵
sort(all(v)); v.erase(unique(all(v)),end(v)); }↵
tcTU> void erase(T& t, const U& u) { // don't erase element that doesn't exist from (multi)set↵
auto it = t.find(u); assert(it != end(t));↵
t.erase(it); }↵
↵
// use like sumv(all(dat))↵
template<class ForwardIt>↵
auto sumv(ForwardIt first, ForwardIt last)↵
{↵
/**↵
Careful: accumulation in int could overflow.↵
Therefore, make `out` an ll if the data is any integer type.↵
Otherwise, out is the same type as the data.↵
*/↵
typename std::conditional<↵
std::is_integral<typename std::iterator_traits<ForwardIt>::value_type>::value,↵
ll,↵
typename std::iterator_traits<ForwardIt>::value_type↵
>::type out {};↵
for (; first != last; ++first) {↵
out += *first;↵
}↵
return out;↵
}↵
template<class T> auto sumv(T&& data) {return sumv(all(data));}↵
template<class T> auto max_element(T&& data) {return *max_element(all(data));}↵
template<class T> auto min_element(T&& data) {return *min_element(all(data));}↵
↵
↵
#define tcTUU tcT, class ...U↵
↵
inline namespace Helpers {↵
// is_readable↵
tcT, class = void> struct is_readable : false_type {};↵
tcT> struct is_readable<T,↵
typename std::enable_if_t<↵
is_same_v<decltype(cin >> declval<T&>()), istream&>↵
>↵
> : true_type {};↵
tcT> constexpr bool is_readable_v = is_readable<T>::value;↵
↵
// is_printable↵
// // https://nafe.es/posts/2020-02-29-is-printable/↵
tcT, class = void> struct is_printable : false_type {};↵
tcT> struct is_printable<T,↵
typename std::enable_if_t<↵
is_same_v<decltype(cout << declval<T>()), ostream&>↵
>↵
> : true_type {};↵
tcT> constexpr bool is_printable_v = is_printable<T>::value;↵
↵
↵
tcT> typename enable_if<!is_iterable_v<T> && !is_tuplelike_v<T>, void>::type increment_one(T& x, int inc) {x += inc;}↵
tcT> typename enable_if<is_tuplelike_v<T>, void>::type increment_one(T& t, int inc);↵
tcT> typename enable_if<is_iterable_v<T>, void>::type increment_one(T& t, int inc) { for(auto&& x : t) {increment_one(x, inc);} }↵
↵
template<class T, size_t k>↵
void increment_one_tuplehelper(T& t, int inc) {↵
increment_one(get<k>(t), inc);↵
if constexpr (k < tuple_size_v<T> - 1) {↵
increment_one_tuplehelper<T, k+1>(t, inc);↵
}↵
}↵
tcT> typename enable_if<is_tuplelike_v<T>, void>::type increment_one(T& t, int inc) {↵
increment_one_tuplehelper<T,0>(t, inc);↵
}↵
↵
void increment() {} // add one to each, for output. BE CAREFUL TO UNDO MODIFICATIONS↵
tcTUU> void increment(T& t, U&... u) { increment_one(t,+1); increment(u...); }↵
void decrement() {} // subtract one from each, for input. MODIFICATION IS THE GOAL↵
tcTUU> void decrement(T& t, U&... u) { increment_one(t,-1); decrement(u...); }↵
}↵
↵
inline namespace Input {↵
tcT> constexpr bool needs_input_v = !is_readable_v<T> && is_iterable_v<T>;↵
↵
tcTUU> void re(T& t, U&... u);↵
tcTU> void re(pair<T,U>& p); // pairs↵
↵
// re: read↵
tcT> typename enable_if<is_readable_v<T>,void>::type re(T& x) { cin >> x; } // default↵
tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; } // complex↵
tcT> typename enable_if<needs_input_v<T>,void>::type re(T& i); // ex. vectors, arrays↵
tcTU> void re(pair<T,U>& p) { re(p.first,p.second); }↵
template<class A,class B,class C> void re(tuple<A,B,C>& t) {auto& [a,b,c]=t; re(a,b,c);}↵
template<class A,class B,class C, class D> void re(tuple<A,B,C,D>& t) {auto& [a,b,c,d]=t; re(a,b,c,d);}↵
template<class A,class B,class C, class D, class E> void re(tuple<A,B,C>& t) {auto& [a,b,c,d,e]=t; re(a,b,c,d,e);}↵
template<class A,class B,class C, class D, class E, class F> void re(tuple<A,B,C>& t) {auto& [a,b,c,d,e,f]=t; re(a,b,c,d,e,f);}↵
tcT> typename enable_if<needs_input_v<T>,void>::type re(T& i) {↵
each(x,i) re(x); }↵
tcTUU> void re(T& t, U&... u) { re(t); re(u...); } // read multiple↵
↵
// rv: resize and read vectors↵
void rv(size_t) {}↵
tcTUU> void rv(size_t N, V<T>& t, U&... u);↵
template<class...U> void rv(size_t, size_t N2, U&... u);↵
tcTUU> void rv(size_t N, V<T>& t, U&... u) {↵
t.resize(N); re(t);↵
rv(N,u...); }↵
template<class...U> void rv(size_t, size_t N2, U&... u) {↵
rv(N2,u...); }↵
void rv1(size_t) {}↵
tcTUU> void rv1(size_t N, V<T>& t, U&... u) {↵
t.resize(N); re(t); for(auto& x : t) decrement(x);↵
rv1(N,u...); }↵
↵
↵
// dumb shortcuts to read in ints↵
#define ints(...) int __VA_ARGS__; re(__VA_ARGS__);↵
#define int1(...) ints(__VA_ARGS__); decrement(__VA_ARGS__);↵
#define chars(...) char __VA_ARGS__; re(__VA_ARGS__);↵
#define lls(...) ll __VA_ARGS__; re(__VA_ARGS__);↵
#define ll1(...) lls(__VA_ARGS__); decrement(__VA_ARGS__);↵
#define strings(...) string __VA_ARGS__; re(__VA_ARGS__);↵
}↵
↵
inline namespace ToString {↵
tcT> constexpr bool needs_output_v = !is_printable_v<T> && is_iterable_v<T>;↵
↵
// ts: string representation to print↵
tcT> typename enable_if<is_printable_v<T>,str>::type ts(T v) {↵
stringstream ss; ss << fixed << setprecision(15) << v;↵
return ss.str(); } // default↵
tcT> str bit_vec(T t) { // bit vector to string↵
str res = "{"; F0R(i,sz(t)) res += ts(t[i]);↵
res += "}"; return res; }↵
str ts(V<bool> v) { return bit_vec(v); }↵
template<size_t SZ> str ts(bitset<SZ> b) { return bit_vec(b); } // bit vector↵
tcTU> str ts(pair<T,U> p); // pairs↵
tcT> typename enable_if<needs_output_v<T>,str>::type ts(T v); // vectors, arrays↵
tcTU> str ts(pair<T,U> p) { return "("+ts(p.first)+", "+ts(p.second)+")"; }↵
tcT> typename enable_if<is_iterable_v<T>,str>::type ts_sep(T v, str sep) {↵
// convert container to string w/ separator sep↵
bool fst = 1; str res = "";↵
for (const auto& x: v) {↵
if (!fst) res += sep;↵
fst = 0; res += ts(x);↵
}↵
return res;↵
}↵
tcT> typename enable_if<needs_output_v<T>,str>::type ts(T v) {↵
return "{"+ts_sep(v,", ")+"}"; }↵
↵
// for nested DS↵
template<int, class T> typename enable_if<!needs_output_v<T>,vs>::type↵
ts_lev(const T& v) { return {ts(v)}; }↵
template<int lev, class T> typename enable_if<needs_output_v<T>,vs>::type↵
ts_lev(const T& v) {↵
if (lev == 0 || !sz(v)) return {ts(v)};↵
vs res;↵
for (const auto& t: v) {↵
if (sz(res)) res.back() += ",";↵
vs tmp = ts_lev<lev-1>(t);↵
res.insert(end(res),all(tmp));↵
}↵
F0R(i,sz(res)) {↵
str bef = " "; if (i == 0) bef = "{";↵
res[i] = bef+res[i];↵
}↵
res.back() += "}";↵
return res;↵
}↵
}↵
↵
inline namespace Output {↵
template<class T, size_t k>↵
void tsish_tuplehelper(T& t, string& out) {↵
out += ts(get<k>(t)); out.push_back(' ');↵
if constexpr (k < tuple_size_v<T> - 1) { tsish_tuplehelper<T, k+1>(t, out); }↵
}↵
tcT> typename enable_if<is_tuplelike_v<T>, string>::type tsish(T& t) {↵
string out; tsish_tuplehelper<T,0>(t, out); out.pop_back(); return out;↵
}↵
tcT> typename enable_if<!is_tuplelike_v<T>, string>::type tsish(T& t) { return ts(t); }↵
↵
template<class T> void pr_sep(ostream& os, str, const T& t) { os << tsish(t); }↵
template<class T, class... U> void pr_sep(ostream& os, str sep, const T& t, const U&... u) {↵
pr_sep(os,sep,t); os << sep; pr_sep(os,sep,u...); }↵
template<class T> void pr_sep1(ostream& os, str, T& t) { increment(t); os << tsish(t); decrement(t); }↵
template<class T, class... U> void pr_sep1(ostream& os, str sep, T& t, U&... u) {↵
pr_sep1(os,sep,t); os << sep; pr_sep1(os,sep,u...); }↵
// print w/ no spaces↵
template<class ...T> void pr(const T&... t) { pr_sep(cout,"",t...); }↵
// print w/ spaces, end with newline↵
void ps() { cout << "\n"; }↵
template<class ...T> void ps(const T&... t) { pr_sep(cout," ",t...); ps(); }↵
void ps1() { cout << "\n"; }↵
template<class ...T> void ps1(T&... t) { pr_sep1(cout," ",t...); ps1(); }↵
void pso() {}↵
template<class ...T> void pso(const T&... t) { pr_sep(cout," ",t...); pso(); }↵
void pso1() {}↵
template<class ...T> void pso1(T&... t) { pr_sep1(cout," ",t...); pso1(); }↵
↵
template<class T>↵
void pv(T& dat) {bool f=1; for(auto&& x : dat) {if (!f) {cout<<' ';} f=0; cout << tsish(x);} cout<<'\n';}↵
template<class T>↵
void pv1(T& dat) {bool f=1; increment(dat); for(auto&& x : dat) {if (!f) {cout<<' ';} f=0; cout << tsish(x);} cout<<'\n'; decrement(dat);}↵
template<class T>↵
void pvn(T& dat) {bool f=1; for(auto&& x : dat) {if (!f) {cout<<'\n';} f=0; cout << tsish(x);} cout<<'\n';}↵
template<class T>↵
void pvn1(T& dat) {bool f=1; increment(dat); for(auto&& x : dat) {if (!f) {cout<<'\n';} f=0; cout << tsish(x);} cout<<'\n'; decrement(dat);}↵
// * Remove debug code; I'll use the tourist+me amalgamation instead.↵
↵
#ifndef _OPENMP↵
const clock_t beg = clock();↵
#define dbg_time() dbg((db)(clock()-beg)/CLOCKS_PER_SEC)↵
db TIME() {return (db)(clock()-beg)/CLOCKS_PER_SEC;}↵
#else↵
const db beg = omp_get_wtime();↵
db TIME() {return omp_get_wtime() - beg;}↵
#endif↵
void flush() {std::cout << std::flush;}↵
}↵
↵
inline namespace FileIO {↵
void setIn(str s) { if ( !freopen(s.c_str(),"r",stdin) ) assert(false); }↵
void setOut(str s) { if ( freopen(s.c_str(),"w",stdout) ) assert(false); }↵
void setIO(str s = "") {↵
cin.tie(0)->sync_with_stdio(0); // unsync C / C++ I/O streams↵
cout.tie(0);↵
cin.exceptions(cin.failbit);↵
// throws exception when do smth illegal↵
// ex. try to read letter into int↵
if (sz(s)) setIn(s+".in"), setOut(s+".out"); // for old USACO↵
}↵
}↵
↵
#pragma region // debugging↵
// * debug setup mostly stolen from tourist. https://codeforces.net/contest/1540/submission/120602670↵
// * dcclyde added line numbers, colors, probably some other stuff.↵
↵
template <typename A, typename B>↵
string to_string(pair<A, B> p);↵
↵
template <typename X>↵
typename enable_if<is_tuplelike_v<X>, string>::type to_string(X p);↵
↵
string to_string(const string& s) {↵
return '"' + s + '"';↵
}↵
↵
string to_string(char c) {↵
return "'" + string(1, c) + "'";↵
}↵
↵
string to_string(const char* s) {↵
return to_string((string) s);↵
}↵
↵
string to_string(bool b) {↵
return (b ? "true" : "false");↵
}↵
↵
string to_string(vector<bool> v) {↵
bool first = true;↵
string res = "{";↵
for (int i = 0; i < static_cast<int>(v.size()); i++) {↵
if (!first) {↵
res += ", ";↵
}↵
first = false;↵
res += to_string(v[i]);↵
}↵
res += "}";↵
return res;↵
}↵
↵
template <size_t N>↵
string to_string(bitset<N> v) {↵
string res = "";↵
for (size_t i = 0; i < N; i++) {↵
res += static_cast<char>('0' + v[i]);↵
}↵
return res;↵
}↵
↵
template <typename A>↵
typename enable_if<is_iterable_v<A>, string>::type to_string(A v) {↵
bool first = true;↵
string res = "{";↵
for (const auto &x : v) {↵
if (!first) {↵
res += ", ";↵
}↵
first = false;↵
res += to_string(x);↵
}↵
res += "}";↵
return res;↵
}↵
↵
template<typename T>↵
V<T> pqueue_to_iterable(priority_queue<T> PQ) { // PASS BY VALUE!↵
V<T> working;↵
while (!PQ.empty()) {working.push_back(PQ.top()); PQ.pop();}↵
reverse(all(working));↵
return working;↵
}↵
↵
template <typename T>↵
string to_string(priority_queue<T>&& PQ) {↵
return to_string(pqueue_to_iterable(PQ));↵
}↵
↵
template <typename A, typename B>↵
string to_string(pair<A, B> p) {↵
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";↵
}↵
↵
template<class T, size_t k>↵
void to_string_tuplehelper(string& out, T& t) {↵
out += ", " + to_string(get<k>(t));↵
if constexpr (k < tuple_size_v<T> - 1) {↵
to_string_tuplehelper<T, k+1>(out, t);↵
}↵
}↵
template <typename X>↵
typename enable_if<is_tuplelike_v<X>, string>::type to_string(X p) {↵
string out = "(" + to_string(get<0>(p));↵
to_string_tuplehelper<X, 1>(out, p);↵
out += ")";↵
return out;↵
}↵
↵
↵
// helpers for debugging complicated objects↵
template<class T, class S>↵
string print_details_helper_general(T&& q, S f, ll MAX) {↵
string out;↵
ll ctr = 0;↵
bool trimmed = false;↵
for ( auto&& x : q ) {↵
if (ctr == MAX) {trimmed = true; break;}↵
out.push_back('\t');↵
out += to_string(ctr) + ":\t" + to_string(f(x)) + "\n";↵
++ctr;↵
}↵
// string prefix = "\tlen " + to_string(q.size());↵
string prefix = "";↵
if (trimmed) {↵
// prefix += ", trimmed to " + to_string(MAX);↵
out.pop_back();↵
out = prefix + "\n" + out + "\n\t... (full length " + to_string(q.size()) + ")";↵
out.push_back('\n');↵
} else {↵
out = prefix + "\n" + out;↵
}↵
return out;↵
}↵
↵
#define PDH_DEFAULT_MAX 10'000↵
template<class T>↵
string print_details_helper(T&& q, ll MAX=PDH_DEFAULT_MAX) {↵
return print_details_helper_general(q, [&](auto x) {return x;}, MAX);↵
}↵
string print_details_helper(V<bool>&& q, ll MAX=PDH_DEFAULT_MAX) {↵
return print_details_helper_general(q, [&](auto x) {return static_cast<bool>(x);}, MAX);↵
}↵
template<class T>↵
string print_details_helper(priority_queue<T>&& PQ, ll MAX=PDH_DEFAULT_MAX) {↵
return print_details_helper(pqueue_to_iterable(PQ), MAX);↵
}↵
#define pdh print_details_helper↵
↵
template<class T, class S>↵
string print_details_helper_func(T&& q, S f, ll MAX=PDH_DEFAULT_MAX) {↵
return print_details_helper_general(q, f, MAX);↵
}↵
template<class S>↵
string print_details_helper_func(V<bool>&& q, S f, ll MAX=PDH_DEFAULT_MAX) {↵
return print_details_helper_general(q, [&](auto x) {return f(static_cast<bool>(x));}, MAX);↵
}↵
template<class T, class S>↵
string print_details_helper_func(priority_queue<T>&& PQ, S f, ll MAX=PDH_DEFAULT_MAX) {↵
return print_details_helper_general(pqueue_to_iterable(PQ), f, MAX);↵
}↵
#define pdh_func print_details_helper_func↵
#define pdhf print_details_helper_func↵
↵
↵
↵
template<class T>↵
string print_tsv_helper(T&& q) {↵
string out = "\n";↵
for ( auto&& x : q ) {↵
bool first = true;↵
for ( auto& v : x ) {↵
if ( !first ) {↵
out += '\t';↵
}↵
out += to_string(v);↵
first = false;↵
}↵
out += '\n';↵
}↵
return out;↵
}↵
#define pth print_tsv_helper↵
↵
↵
void debug_out() {}↵
↵
template <typename Head, typename... Tail>↵
void debug_out(Head H, Tail... T) {↵
// mostly no difference unless there's a background color.↵
// std::cerr << to_string(H) << " ";↵
// debug_out(T...);↵
std::cerr << ' ' << to_string(H) << ' ';↵
if (sizeof...(T)) {↵
std::cerr << " ";↵
debug_out(T...);↵
}↵
}↵
↵
// #define BOLD_MAYBE "" // NOT bold↵
#define BOLD_MAYBE ";1" // YES bold↵
↵
#define OUT_RESET "\033[0m"↵
#define OUT_BOLD "\033[;1m"↵
#define OUT_RED "\033[31" "m"↵
#define OUT_CYAN "\033[36" BOLD_MAYBE "m"↵
// #define OUT_GREEN "\033[32" << BOLD_MAYBE << "m"↵
#define OUT_GREEN "\033[32" "m"↵
#define OUT_BLUE "\033[34" BOLD_MAYBE "m"↵
#define OUT_WHITE "\033[97" "m"↵
#define OUT_MARK "\033[0;30;41;1m"↵
#define OUT_YELLOW "\033[33" BOLD_MAYBE "m"↵
#define OUT_PURPLE "\033[35" BOLD_MAYBE "m"↵
↵
↵
#define dbgc(...) ;↵
#define dbg(...) ;↵
#define el ;↵
#define dbgBold(...) ;↵
#define dbgcBold(...) ;↵
#define dbgY(...) ;↵
#define dbgcY(...) ;↵
#define dbgP(...) ;↵
#define dbgcP(...) ;↵
#define dbgR(...) ;↵
#define dbgcR(...) ;↵
#define dbgB(...) ;↵
#define dbgcB(...) ;↵
#define dbgW(...) ;↵
#define dbgcW(...) ;↵
#define dbg_only(...) ;↵
#define local_run (false)↵
#ifdef DCCLYDE_LOCAL↵
// dbgc = "debug with comment"↵
#define dbgcbase(A, B, C, ARGTEXT, ...) std::cout << std::flush; \↵
std::cerr << OUT_BOLD << B \↵
<< std::right << setw(20) << C << ' ' \↵
<< OUT_RESET << OUT_BOLD << OUT_RED \↵
<< std::right << setw(7) << __LINE__ \↵
<< OUT_BOLD << " : " << OUT_RESET \↵
<< A << "[ " << ARGTEXT << " ]" \↵
<< OUT_BOLD << " : " << OUT_RESET \↵
<< B, debug_out(__VA_ARGS__); \↵
std::cerr << OUT_RESET << std::endl;↵
↵
#undef dbgBold↵
#define dbgBold(...) dbgcbase(OUT_GREEN, OUT_MARK, "", #__VA_ARGS__, __VA_ARGS__)↵
#undef dbgcBold↵
#define dbgcBold(MSG, ...) dbgcbase(OUT_GREEN, OUT_MARK, MSG, #__VA_ARGS__, __VA_ARGS__)↵
↵
#undef dbg↵
#define dbg(...) dbgcbase(OUT_GREEN, OUT_CYAN, "", #__VA_ARGS__, __VA_ARGS__)↵
#undef dbgc↵
#define dbgc(MSG, ...) dbgcbase(OUT_GREEN, OUT_CYAN, MSG, #__VA_ARGS__, __VA_ARGS__)↵
↵
#undef dbgY↵
#define dbgY(...) dbgcbase(OUT_GREEN, OUT_YELLOW, "", #__VA_ARGS__, __VA_ARGS__)↵
#undef dbgcY↵
#define dbgcY(MSG, ...) dbgcbase(OUT_GREEN, OUT_YELLOW, MSG, #__VA_ARGS__, __VA_ARGS__)↵
↵
#undef dbgP↵
#define dbgP(...) dbgcbase(OUT_GREEN, OUT_PURPLE, "", #__VA_ARGS__, __VA_ARGS__)↵
#undef dbgcP↵
#define dbgcP(MSG, ...) dbgcbase(OUT_GREEN, OUT_PURPLE, MSG, #__VA_ARGS__, __VA_ARGS__)↵
↵
#undef dbgR↵
#define dbgR(...) dbgcbase(OUT_GREEN, OUT_RED, "", #__VA_ARGS__, __VA_ARGS__)↵
#undef dbgcR↵
#define dbgcR(MSG, ...) dbgcbase(OUT_GREEN, OUT_RED, MSG, #__VA_ARGS__, __VA_ARGS__)↵
↵
#undef dbgB↵
#define dbgB(...) dbgcbase(OUT_GREEN, OUT_BLUE, "", #__VA_ARGS__, __VA_ARGS__)↵
#undef dbgcB↵
#define dbgcB(MSG, ...) dbgcbase(OUT_GREEN, OUT_BLUE, MSG, #__VA_ARGS__, __VA_ARGS__)↵
↵
#undef dbgW↵
#define dbgW(...) dbgcbase(OUT_GREEN, OUT_WHITE, "", #__VA_ARGS__, __VA_ARGS__)↵
#undef dbgcW↵
#define dbgcW(MSG, ...) dbgcbase(OUT_GREEN, OUT_WHITE, MSG, #__VA_ARGS__, __VA_ARGS__)↵
↵
#undef dbg_only↵
#define dbg_only(...) __VA_ARGS__;↵
↵
#undef el↵
#define el std::cerr << std::flush; std::cerr << '\n'; // in my head I say "error line"↵
↵
#undef local_run↵
#define local_run (true)↵
#endif↵
#pragma endregion↵
↵
#define timebomb(a) dbg_only({static int _bomb = 0; if(++_bomb>=a) {dbgc("boom!", a);exit(1);}});↵
↵
#define YES ps("YES");↵
#define NO ps("NO");↵
#define Yes ps("Yes");↵
#define No ps("No");↵
#define IMPOSSIBLE ps("IMPOSSIBLE");↵
↵
const ll INF_ll = ll(2e18) + 1;↵
const int INF_i = int(2e9) + 1;↵
↵
// const int MOD = 1'000'000'007;↵
// const int MOD = 998'244'353;↵
↵
#pragma endregion↵
↵
// ! ---------------------------------------------------------------------------↵
↵
↵
↵
↵
↵
↵
void solve() {↵
lls(N);↵
V<ll> dat;↵
rv(N, dat);↵
dbgR(N, dat);↵
el;↵
↵
// ! Read the sample cases AND EXPLANATIONS before writing code for nontrivial problems!↵
↵
↵
↵
return;↵
}↵
↵
// ! Do something instead of nothing: write out small cases, code bruteforce↵
// ! Check bounds even if I have a solution - are they letting through simpler versions?↵
// ! If stuck on a "should be easy" problem for 10 mins, reread statement, check bounds↵
↵
#define PROBLEM_STYLE CF↵
// #define SINGLE_CASE // ! Uncomment this for one-case problems.↵
#pragma region // main↵
#if PROBLEM_STYLE == CF || PROBLEM_STYLE == GCJ↵
int main() {↵
setIO();↵
↵
int T = 1;↵
#ifndef SINGLE_CASE↵
dbgc("loading num cases!!!"); std::cin >> T;↵
#endif↵
for ( int CASE = 1 ; CASE <= T ; ++CASE ) {↵
#if PROBLEM_STYLE == GCJ↵
cout << "Case #" << CASE << ": ";↵
#endif↵
el;↵
#ifndef DCCLYDE_BRUTEFORCE↵
dbgcBold("CASE" , CASE );↵
solve();↵
#else↵
dbgcBold("brute force" , CASE );↵
brute();↵
#endif↵
}↵
dbgR(TIME());↵
return 0;↵
}↵
#else↵
// PROBLEM_STYLE is CLEAN or undefined.↵
int main() {↵
#ifdef _OPENMP↵
ll num_procs = omp_get_num_procs();↵
ll max_threads = omp_get_max_threads();↵
dbgBold(num_procs, max_threads);↵
omp_set_num_threads(num_procs - 4);↵
#endif↵
solve();↵
dbgR(TIME());↵
return 0;↵
}↵
#endif↵
#pragma endregion↵
~~~~~↵
↵
</spoiler>
* [Current template.cpp](https://github.com/dcclyde/coding_puzzles/blob/master/templates/template.cpp) — includes updates made after this blog was posted. This is the recommended version for most people.↵
* [Minimal version with debug printouts only](https://github.com/dcclyde/coding_puzzles/blob/master/templates/dbg_demo.cpp) — Stripped-down version that compiles faster while still providing the `dbg()` setup, which is IMO the most novel and cool feature in the template. Recommended if your computer is too slow to compile the main version. But please try the precompiled headers trick first, since that helps the compile times a lot!↵
↵
Specific cool tricks in the template↵
------------------↵
### Debug printouts↵
Here's an output screenshot:↵
↵
↵
...and here's the code I used↵
↵
[cut]↵
↵
:↵
↵
~~~~~↵
void solve() {↵
ll a = 14; double b = -3e-2; char c = '@'; string s = "Test String";↵
vector<ll> q = {1, 6, 4, 3, 5, 3, 1};↵
dbg(a, b, c, "", s, q);↵
dbgc("show this on left", make_pair(a, c)); // dbgc = "debug with 1st arg as comment"↵
dbgcP("diff colors", a, b); // uppercase letters change the color; all terminal colors are available↵
dbgc("expressions work too", 2*b, gcd(a, a+4));↵
el; // empty line↵
↵
// complex/nested data structures work too.↵
map<pair<ll,ll>, V<string>> dat = {↵
{{3, 5}, {"abc", "def"}},↵
{{4, -1}, {"apple", "peach", "banana"}},↵
{{-5, 0}, {"tourist", "jiangly", "um_nik", "slime", "ksun48"}}↵
};↵
dbgY(dat);↵
// that may be pretty messy to read all on one line though, so we can use:↵
dbg(pdh(dat));↵
el;↵
↵
// show how "regular output" lines look visibly different from dbg() lines.↵
cout << a << ' ' << b << ' ' << c << '\n';↵
↵
// what if we have a big object and we want to "get the idea" of its contents↵
// without printing the whole thing?↵
vector<pll> vbig; FOR(k, 0, 100) {vbig.emplace_back(k, -k*k);}↵
dbgR(pdh(vbig, 10)); // short for "print_details_helper"↵
↵
el;↵
// Advanced: pdhf lets me specify a function, so f(x) will be printed for each x in the structure.↵
dbg(pdhf(vbig, [&](auto x){return x.second;}, 5)); // pdhf = "print_details_helper_func"↵
↵
dbgcBold("done!");↵
return;↵
}↵
~~~~~↵
↵
#### Summary of key dbg() features↵
↵
* `dbg(a, b, c)` prints line number, exact text you passed in, and the values of all those variables/expressions/objects. Optional `dbgc` version uses the first argument as a marker or comment, which is placed to the left. All printouts are indented to keep them visually separate from the normal outputs to cout.↵
* Different color options so you can easily see which printouts came from which dbg() call without comparing line numbers every time. Default color is cyan if you just use dbg(); specify other colors with dbgP (purple), dbgY (yellow), and so on. All the ANSI terminal colors are provided except black; see the template code for the full list. dbgBold provides a special colorset with a bright red background.↵
* Handles pairs, tuples, and STL data structures including arbitrary nesting.↵
* **All `dbg()` and `el` stuff is removed at preprocessor stage if we didn't pass flag -DDCCLYDE_LOCAL when compiling.** That means I don't need to bother commenting out these lines before submitting to online judges. (That's a big upgrade from regular cerr printouts, which won't cause WA at most judges but can easily cause TLE.)↵
* pdh ("print details helper") functionality prints one entry per line; useful if we're printing a complex object since printing on one line can be hard to visually process. Template includes some extensions, demod above.↵
↵
#### Real-life example↵
The demo above may make it seem like the different colors are just visually noisy instead of useful. Here's an example of how I'd use the printouts in "real life" on a recent div2 C. (OK, in a real competition I wouldn't use this many comments or printouts unless the implementation was more complicated, but I want to make the example understandable by everyone who sees this blog.)↵
↵
[Submission link](https://codeforces.net/contest/1720/submission/169037463)↵
↵
<spoiler summary="Just the solve() function">↵
~~~~~↵
/**↵
Idea: After the very first step, it should always be possible to remove↵
exactly one 1 per step. So the plan is:↵
1) Choose the first step to remove smallest possible number of 1s↵
2) Answer will be 1 + num ones remaining after the first step↵
*/↵
↵
void solve() {↵
lls(R, C);↵
V<string> dat; rv(R, dat);↵
dbgR(MP(R,C), dat); // I usually dbg() the inputs so I can confirm I read them correctly.↵
el;↵
↵
// Step 1: Find smallest possible number of 1s deleted in first step.↵
ll fewest_deleted = 3;↵
FOR(r, 0, R-1) FOR(c, 0, C-1) {↵
ll ones_in_2x2 = 0;↵
FOR(j, 0, 2) FOR(k, 0, 2) {↵
if (dat[r + j][c + k] == '1') {++ones_in_2x2;}↵
}↵
ll ones_deleted_here = max(ones_in_2x2 - 1, 0LL);↵
ckmin(fewest_deleted, ones_deleted_here);↵
dbg(MP(r, c), ones_in_2x2, "", ones_deleted_here, fewest_deleted);↵
}↵
↵
ll ones_total = 0;↵
FOR(r, 0, R) FOR(c, 0, C) {↵
if (dat[r][c] == '1') {++ones_total;}↵
}↵
↵
ll out;↵
if (fewest_deleted == 0) {↵
// It's initially possible to pick an L shape that doesn't hit any 1s.↵
// That isn't a legal move though.↵
out = ones_total;↵
} else {↵
out = 1 + (ones_total - fewest_deleted);↵
}↵
dbgY(fewest_deleted, ones_total, out);↵
ps(out);↵
return;↵
}↵
~~~~~↵
</spoiler>↵
↵
Here's what I see when I run the sample test cases locally:↵
↵
↵
For short solutions, I normally just use random different colors for each printout. In more complicated programs I try to somewhat organize my color usage. For example, I sometimes use: Red = print out inputs as soon as I read them to confirm I loaded them correctly; Yellow = higher-level info, maybe printing out results of a big intermediate step or printing status once per outer loop cycle; Cyan (default) = less important stuff, or printouts coming from inside a work loop; Purple = printouts from inside a function call or nested loop.↵
↵
↵
### "Unhackable" and faster unordered_map and unordered_set replacements↵
`unordered_map` and `unordered_set` are notoriously hackable and so generally should not be used on Codeforces; see [classic blog post](https://codeforces.net/blog/entry/62393). Also, they are usually around 5x slower than the alternative `gp_hash_table`; see [another blog](https://codeforces.net/blog/entry/60737).↵
My template defines replacements `umap` and `uset` which fix both of those problems, basically by implementing the recommendations from those linked posts. Bonus: my versions also happily hash arbitrary pairs, tuples, or iterable STL objects. I make it easy to toggle which implementation is used by `umap` and `uset`. Caveat: pairs and tuples work well, but hashing more complex stuff like `std::vector`s can often lead to TLE.↵
↵
### Precompiled header↵
When compiling on judge server, the template uses a few includes:↵
↵
~~~~~↵
#include <tgmath.h>↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
~~~~~↵
When compiling locally, the template instead just uses `#include "/home/dcclyde/puzzles/code/templates/superheader.h"`. That's because [superheader.h](https://github.com/dcclyde/coding_puzzles/blob/master/templates/superheader.h) is a local file that has all those same includes, except I've set up a precompiled header which makes my compilations several seconds faster. The difference is approximately 6s -> 1.5s on my older laptop, but only 2.5s -> 1.0s on my current machine. Basically, depending on your computer this hack might be pretty important for keeping the compile time manageable despite all the template's #includes and #defines.↵
↵
I'm not recommending a specific guide for how to build a precompiled header because the correct steps may depend on your OS and machine configuration. However, I was able to make it work pretty quickly once I searched Google for `precompiled header C++ gcc ubuntu`, so I hope you'll have good luck here too.↵
↵
### I/O shortcuts↵
These aren't a huge deal, but they do save me from typing the same annoying lines of code in every problem.↵
↵
~~~~~↵
// INPUT↵
lls(R, C); // declare and read from stdin two long longs called R and C. Can also use ints, chars, strings to read those other datatypes.↵
ll1(a, b); // same as lls except decrement the variables by 1 after reading; useful when problems give 1-indexed inputs but I want to work with 0-indexed↵
V<int> q;↵
rv(R, q); // resize q to size R and then fill all entries from stdin↵
rv1(R, q); // same as rv except decrement by 1 after reading↵
↵
// OUTPUT↵
ps(a, b, R); // same as cout << a << ' ' << b << ' ' << R << '\n';↵
ps1(a, b); // same as cout << a+1 << ' ' << b+1 << '\n'; notice we ADD 1 when outputting.↵
pv(q); // output space-separated all on one line, with newline at the end↵
pv1(q); // same as pv but add 1 to each output↵
~~~~~↵
↵
Compilation and usage notes↵
------------------↵
Sample compile+run command: `g++ --std=c++20 -DDCCLYDE_LOCAL template.cpp && ./a.out`↵
↵
The template requires C++17 or higher. It also works better on 64-bit systems, just because lately I use `long long` instead of `int` by default due to the negligible speed difference on modern machines including online judges.↵
↵
I submit to Codeforces using `GNU C++20 (64)` and AtCoder using `C++ (GCC 9.2.1)`.↵
↵
The template will be nicer to use if your editor has a shortcut for code folding between `#pragma region` and `#pragma endregion`. I use VS Code and I have keyboard shortcuts bound for "Fold All Regions" and "Unfold All Regions". I also use the "Better Comments" extension, which explains why some of the comments have special flags at the start (they show up in different colors on my screen).↵
↵
↵
What a good template can (and can't) do for you↵
------------------↵
↵
The main things I think a template can help with are:↵
↵
1. Reduce repetitive typing: save 1-5 minutes on every problem by using small prewritten functions/macros for I/O, binary searches, etc. On CF this is pretty important, since getting problems A and B in 1-3 mins instead of 5-10 minutes helps my rating a lot. Less code typed for each problem also means less chances for typos, so it becomes a little easier to code correctly.↵
2. Make debugging faster and easier: even when the intermediate steps are producing complicated data structures, the dbg() functionality lets me track down unexpected/buggy behaviour very fast. Before I had this template I used to code new debug printouts on every problem, and coding the printouts would distract me from focusing fully on thinking through my logic to actually find the mistake.↵
↵
Overall, the template makes it way easier and faster for me to go from "having the right idea" to "getting AC". I always feel frustrated if I think of the correct plan but don't end up getting AC. My template makes the implementation process much smoother which helps me feel motivated and confident during contests and training, especially with new ideas/algorithms that I'm not very comfortable with.↵
↵
Unfortunately, a template can't help you have the right solution ideas in the first place. For that you can instead read the thousands of blogs that already exist with more general advice about how to train ;)↵
↵
I've read some CF blogs where strong coders say that a good coder shouldn't rely on a long template. I also see a very wide variety in template lengths even among LGMs. Overall, I think template size can just be personal preference, and you should experiment to see what feels best to you.↵
↵
Special thanks↵
------------------↵
↵
When creating my template, I started from [user:benq,2022-08-20]'s TemplateLong.cpp ([GitHub](https://github.com/bqi343/USACO/blob/master/Implementations/content/contest/TemplateLong.cpp)). My version is very different, but I still use lots of minor convenience features from his template.↵
↵
The dbg() functionality is my heavily modified version of ideas stolen from [user:tourist,2022-08-20] and [user:Livw08,2022-08-20], see [blog](https://codeforces.net/blog/entry/68809).↵
↵
Of course I've taken ideas or code from a ton of other sources too, mostly other CF blogs. Thanks everyone!↵
↵
Questions, suggestions, advice?↵
------------------↵
I'm very interested to hear to advice about how to accomplish the same things in a better way, or feature requests that would make the template easier to use or more helpful, or even just random questions about why I did things a certain way. Some of my "weird" decisions are made on purpose to get around non-obvious issues that I didn't discuss in this blog, and others may be just because I'm clumsy with some of the tools I'm using here, so even asking "silly" questions can be useful — either I'll explain something you didn't see, or I'll learn something from your idea.↵
↵
This is my first blog post after using Codeforces off and on for 6+ years, so I'm also interested to hear advice about how to make a more useful blog next time.
