C++ Utility library for competitive programming. Fully C++17 compatible.
Permit to use under MIT License.
Additionally, anybody can submit code that contains any part of this library to online judging platforms, if the usage can be restricted in online judging only.
(e.g. If someone can get submitted code on an OJ, and then use it outside the OJ legally according to the OJ's term of service, the usage of this library is forbidden.)
- Submit a single C++ file to online judging platform.
Target environments are Codeforces, Atcoder and Google Code Jam (stack size >= 64M, source code size limit >= 64KB, support most c++17 features, at least O2 optimization level).
ojlibs_cppscript can be used to combine headers, remove comments, put library code to global namespace, and produce a single file. - as a header-only library, all components are in
ojlibsnamespace, and only depends on standard library.
Readability first, Performance second, Source Code Size third.
Header Only.
Modern C++. Use standard library whenever possible. Depend on template heavily.
Trust compiler instead of hand-tuning.
This library adopts c++17 futures to reduce template boilerplate.
When c++20 is widely available, we will switch to c++20.
Old c++11 version of this library can be found at c++11 branch.
list : doubly-linked list
slist: singly-linked list
rbtree: red-black tree
splay: a splay tree with subtree size to support fast n-th query
treap, sbtree, link-cut tree. (TODO)
Disjoint Set
Bit Index Tree (a.k.a Fenwick Tree)
Segment Tree (flavour I/II, and lazy)
Division with fixed rounding direction
GCD / LCM
Extended Euclid Algorithm
Modular Arithmatic
Chinese Remainder Theorem
Bignum
PELL equation (python source)
Permutaion, Combination, Subset (and generators)
Mobius Inversion
Subset Inversion
Multiprecision (bignum)
FFT, FWT.
NTT (TODO)
Matrix over a ring / field, Arithmatics, Inversion, Determinant
(P)LU decomposition
2D geometry (point, line, circle, convex hull, half-planes intersection, closest point pair)
Geometry Transform (TODO)
KMP
Z-Function
Suffix Array (TODO: SA-IS algorithm, linear time construction)
AC-Automaton
Lexicographically least string of all rotations of a given string
Generic graph algorithms (inspired by boost graph library. all vertex or edge attributes are stored externally, and algorithms depends on graph concept, not graph implementation)
DFS / BFS
Shortest Path (Dijkstra, Bellman-Ford, Floyd-Warshall)
Strongly Connected Component
Topological Sort (on DAG)
Offline Tarjan LCA (on rooted/rootless tree)
Cut-vertex in undirected graph (Tarjan)
Network Flow (Dinic)
Maximum Bipartitie Matching (Hungarian / Kuhn-Munkres)
Eular Walk (TODO : support removing edge in graph)
reusable Centroid Decomposition (TODO)
Generic memorization function without virtual function overhead (Useful for top-down dynamic programming.)
High-dimension pre-order problem (CDQ algorithm)
2SAT
// A + B problem
int main() {
int a, b; fin, a, b;
fout, a + b, endl;
}-
Codeforces sample test cases crawler, and automatic validation script. (tools/cf_test_crawler)
-
A tool that can combine source code with included header files of this library to produce a single source file to submit. (tools/ojlibs_cpp)
-
Solution Template : main.cpp, check.sh, interactive.sh and Makefile (src/)
# Download test cases
$ cf_test_crawler -p 123 A
# Check program
$ make check