Skip to content

Instantly share code, notes, and snippets.

View Chillee's full-sized avatar

Horace He Chillee

View GitHub Profile
@Chillee
Chillee / benchmark.cpp
Created April 2, 2019 06:42
Benchmarking utilities
struct timeit {
decltype(chrono::high_resolution_clock::now()) begin;
const string label;
timeit(string label = "???") : label(label) { begin = chrono::high_resolution_clock::now(); }
~timeit() {
auto end = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::milliseconds>(end - begin).count();
cerr << duration << "ms elapsed [" << label << "]" << endl;
}
};
@Chillee
Chillee / fread_gc.cpp
Last active April 16, 2019 00:12
Fast IO
struct GC {
char buf[1 << 16 | 1];
int bc = 0, be = 0;
char operator()() {
if (bc >= be) {
be = fread(buf, 1, sizeof(buf) - 1, stdin);
buf[be] = bc = 0;
}
return buf[bc++];
}
@Chillee
Chillee / diameter.cpp
Last active April 4, 2019 02:20
Tree Diameter: O(N)
int dfs(int cur, int prv = -1, int d = 0) {
dist[cur] = d;
int mx = cur;
for (auto i : adj[cur]) {
if (i == prv)
continue;
int res = dfs(i, cur, d + 1);
if (dist[res] > dist[mx])
mx = res;
}
@Chillee
Chillee / const_intervals.cpp
Last active April 3, 2019 21:35
Binary Search
void rec(int from, int to, function<int(int)> f, int &i, int &p, int q, vector<array<int, 3>> &ints) {
if (p == q)
return;
if (from == to) {
ints.push_back({i, to, p});
i = to;
p = q;
} else {
int mid = (from + to) >> 1;
rec(from, mid, f, i, p, f(mid), ints);
@Chillee
Chillee / coord comp.cpp
Last active October 19, 2019 01:23
Coordinate Compression
map<int, int> comp, decomp;
int A[];
// insert everything into map;
for (int i=0; i<N; i++)
comp[A[i]]=0;
int idx=0;
for (auto &i: comp)
i.second = idx++, decomp[i.second] = i.first;
for (int i=0; i<N; i++)
A[i] = comp[A[i]];
@Chillee
Chillee / intperm.cpp
Created March 17, 2019 08:45
Permutation Mapping: Permutations to/from integers - order preserving
int fac;
template <class It> int perm_to_int(It begin, It end) {
int x = 0, n = 0;
for (It i = begin; i != end; ++i, ++n)
if (*i < *begin)
++x;
int val = 0;
if (n > 2)
val = perm_to_int(++begin, end);
else
@Chillee
Chillee / millerabin.cpp
Last active April 10, 2019 23:03
Miller Rabin: primality test
bool isPrime(ull n) {
if (n < 2 || n % 2 == 0 || n % 3 == 0)
return n - 2 < 2;
ull s = __builtin_ctzll(n - 1), d = n >> s; // counts trailing zeros
for (auto a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
ull p = binExp(a, d, n), i = s;
while (p != 1 && p != n - 1 && a % n && i--)
p = binExp(p, 2, n);
if (p != n - 1 && i != s)
return 0;
@Chillee
Chillee / modsum.cpp
Last active April 4, 2019 02:20
Mod Sum: sum_{i=0}^{to-1} (k*i+c)%m: log(m) with large constant
typedef unsigned long long ull;
ull sumsq(ull to) { return to / 2 * ((to - 1) | 1); }
ull divsum(ull to, ull c, ull k, ull m) {
ull res = k / m * sumsq(to) + c / m * to;
k %= m, c %= m;
if (!k)
return res;
ull to2 = (to * k + c) / m;
return res + (to - 1) * to2 - divsum(to2, m - 1 - c, m, k);
}
@Chillee
Chillee / fft.cpp
Last active October 18, 2024 00:06
FFT
template <int maxn> struct FFT {
constexpr static int lg2(int n) { return 32 - __builtin_clz(n - 1); }
const static int MAXN = 1 << lg2(maxn);
typedef complex<double> cpx;
int rev[MAXN];
cpx rt[MAXN];
FFT() {
rt[1] = cpx{1, 0};
for (int k = 2; k < MAXN; k *= 2) {
cpx z[] = {1, polar(1.0, M_PI / k)};
@Chillee
Chillee / merging two paths on tree.cpp
Last active December 21, 2018 16:13
Random Snippets (Stuff that's not reusable but were painful to write that I wrote nicely and am happy with)
pair<bool, array<int, 2>> canMerge(array<int, 4> pts) {
auto cmp = [&](int a, int b) { return make_pair(lca.depth[a], a) > make_pair(lca.depth[b], b); };
sort(pts.begin(), pts.end(), cmp);
do {
if (lca.dist(pts[0], pts[1]) + lca.dist(pts[1], pts[2]) + lca.dist(pts[2], pts[3]) == lca.dist(pts[0], pts[3]))
return {true, {pts[0], pts[3]}};
} while (next_permutation(pts.begin() + 1, pts.end(), cmp));
return {false, {0, 0}};
}