Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 58968ef

Browse filesBrowse files
bqi343bqi343
committed
rewrite many templates
1 parent c29db6f commit 58968ef
Copy full SHA for 58968ef

File tree

Expand file treeCollapse file tree

113 files changed

+1054
-708
lines changed
Filter options

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.
Dismiss banner
Expand file treeCollapse file tree

113 files changed

+1054
-708
lines changed

‎.gitignore

Copy file name to clipboardExpand all lines: .gitignore
+2-1Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,4 +3,5 @@ header.tmp
33
a.out
44
/Implementations/build/
55
Implementations/kactl.pdf
6-
Contests/Tools/
6+
Contests/Tools/
7+
.vscode

‎Implementations/content/combinatorial (11.2)/DeBruijnSeq.h

Copy file name to clipboard
+7-7Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,22 +1,22 @@
11
/**
2-
* Description: Recursive FKM, given alphabet $[0,k)$ constructs cyclic string
2+
* Description: Given alphabet $[0,k)$ constructs a cyclic string
33
* of length $k^n$ that contains every length $n$ string as substr.
44
* Source: https://github.com/koosaga/DeobureoMinkyuParty/blob/master/teamnote.tex
55
* https://en.wikipedia.org/wiki/De_Bruijn_sequence
66
* pg 241 of http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.5967&rep=rep1&type=pdf
77
* Verification: https://codeforces.com/gym/102001/problem/C
88
*/
99

10-
vi dseq(int k, int n) {
10+
vi deBruijnSeq(int k, int n) { /// Recursive FKM
1111
if (k == 1) return {0};
12-
vi res, aux(n+1);
12+
vi seq, aux(n+1);
1313
function<void(int,int)> gen = [&](int t, int p) {
14-
if (t > n) { // consider lyndon word of len p
15-
if (n%p == 0) FOR(i,1,p+1) res.pb(aux[i]);
14+
if (t > n) { // +lyndon word of len p
15+
if (n%p == 0) FOR(i,1,p+1) seq.pb(aux[i]);
1616
} else {
1717
aux[t] = aux[t-p]; gen(t+1,p);
18-
FOR(i,aux[t-p]+1,k) aux[t] = i, gen(t+1,t);
18+
while (++aux[t] < k) gen(t+1,t);
1919
}
2020
};
21-
gen(1,1); return res;
21+
gen(1,1); return seq;
2222
}

‎Implementations/content/combinatorial (11.2)/MatroidIsect.h

Copy file name to clipboardExpand all lines: Implementations/content/combinatorial (11.2)/MatroidIsect.h
+4-4Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -16,24 +16,24 @@
1616

1717
struct Gmat { // graphic matroid
1818
int V = 0; vpi ed; DSU D;
19-
Gmat(vpi ed):ed(ed) {
19+
Gmat(vpi _ed):ed(_ed) {
2020
map<int,int> m; each(t,ed) m[t.f] = m[t.s] = 0;
2121
each(t,m) t.s = V++;
22-
each(t,this->ed) t.f = m[t.f], t.s = m[t.s];
22+
each(t,ed) t.f = m[t.f], t.s = m[t.s];
2323
}
2424
void clear() { D.init(V); }
2525
void ins(int i) { assert(D.unite(ed[i].f,ed[i].s)); }
2626
bool indep(int i) { return !D.sameSet(ed[i].f,ed[i].s); }
2727
};
2828
struct Cmat { // colorful matroid
29-
int C = 0; vi col; vector<bool> used;
29+
int C = 0; vi col; V<bool> used;
3030
Cmat(vi col):col(col) {each(t,col) ckmax(C,t+1); }
3131
void clear() { used.assign(C,0); }
3232
void ins(int i) { used[col[i]] = 1; }
3333
bool indep(int i) { return !used[col[i]]; }
3434
};
3535
template<class M1, class M2> struct MatroidIsect {
36-
int n; vector<bool> iset; M1 m1; M2 m2;
36+
int n; V<bool> iset; M1 m1; M2 m2;
3737
bool augment() {
3838
vi pre(n+1,-1); queue<int> q({n});
3939
while (sz(q)) {

‎Implementations/content/combinatorial (11.2)/MatroidPart.h

Copy file name to clipboardExpand all lines: Implementations/content/combinatorial (11.2)/MatroidPart.h
+4-4Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@
1111
struct Gmat { // graphic matroid
1212
int V = 0; vpi ed; DSU D;
1313
vi depth;
14-
vector<vpi> adj;
14+
V<vpi> adj;
1515
vpi pre;
1616
Gmat(vpi ed):ed(ed) {
1717
map<int,int> m; each(t,ed) m[t.f] = m[t.s] = 0;
@@ -52,7 +52,7 @@
5252

5353
template<class M> struct MatroidPart {
5454
int n,k; vi iset;
55-
vector<M> m;
55+
V<M> m;
5656
bool augment(int st) {
5757
F0R(i,k) m[i].clear();
5858
F0R(i,n) if (iset[i] != -1) m[iset[i]].ins(i);
@@ -76,10 +76,10 @@ template<class M> struct MatroidPart {
7676
m.assign(k,_m); F0R(i,k) m[i].clear();
7777
int cur = 0;
7878
F0R(j,k) F0R(i,n) if (iset[i] == -1 && m[j].indep(i))
79-
iset[i] = j, m[j].ins(i), cur ++;
79+
iset[i] = j, m[j].ins(i), ++cur;
8080
int lef = n-cur;
8181
F0R(i,n) if (iset[i] == -1) {
82-
cur += augment(i); lef --;
82+
cur += augment(i); --lef;
8383
if (cur == des || cur+lef < des) break;
8484
}
8585
}

‎Implementations/content/combinatorial (11.2)/NimProduct.h

Copy file name to clipboardExpand all lines: Implementations/content/combinatorial (11.2)/NimProduct.h
+3-3Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,6 @@
1919
*/
2020

2121
using ul = uint64_t;
22-
2322
struct Precalc {
2423
ul tmp[64][64], y[8][8][256];
2524
unsigned char x[256][256];
@@ -43,9 +42,10 @@ struct Precalc {
4342
// 2^{8*i}*(a>>(8*i)&255) * 2^{8*j}*(b>>(8*j)&255)
4443
// -> (2^{8*i}*2^{8*j})*((a>>(8*i)&255)*(b>>(8*j)&255))
4544
ul multFast(ul a, ul b) const { // faster nim product
46-
ul res = 0; auto f = [](ul c, int d) { return c>>(8*d)&255; };
45+
ul res = 0; auto f=[](ul c,int d) {return c>>(8*d)&255;};
4746
F0R(i,8) {
48-
F0R(j,i) res ^= y[i][j][x[f(a,i)][f(b,j)]^x[f(a,j)][f(b,i)]];
47+
F0R(j,i) res ^= y[i][j][x[f(a,i)][f(b,j)]
48+
^x[f(a,j)][f(b,i)]];
4949
res ^= y[i][i][x[f(a,i)][f(b,i)]];
5050
}
5151
return res;

‎Implementations/content/combinatorial (11.2)/chapter.tex

Copy file name to clipboardExpand all lines: Implementations/content/combinatorial (11.2)/chapter.tex
+6-6Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -8,9 +8,9 @@ \section{Permutations}
88
Let $g_S(n)$ be the number of $n$-permutations whose cycle lengths all belong to the set $S$. Then
99
$$\sum_{n=0} ^\infty g_S(n) \frac{x^n}{n!} = \exp\left(\sum_{n\in S} \frac{x^n} {n} \right)$$
1010

11-
\subsection{Derangements}
12-
Permutations of a set such that none of the elements appear in their original position.
13-
\[ \mkern-2mu D(n) = (n-1)(D(n-1)+D(n-2)) = n D(n-1)+(-1)^n = \left\lfloor\frac{n!}{e}\right\rceil \]
11+
% \subsection{Derangements}
12+
% Permutations of a set such that none of the elements appear in their original position.
13+
% \[ \mkern-2mu D(n) = (n-1)(D(n-1)+D(n-2)) = n D(n-1)+(-1)^n = \left\lfloor\frac{n!}{e}\right\rceil \]
1414

1515
\subsection{Burnside's lemma} % https://open.kattis.com/problems/littletoys
1616
Given a group $G$ of symmetries and a set $X$, the number of elements of $X$ \emph{up to symmetry} equals
@@ -20,8 +20,8 @@ \section{Permutations}
2020
If $f(n)$ counts ``configurations'' (of some sort) of length $n$, we can ignore rotational symmetry using $G = \mathbb Z_n$ to get
2121
\[ g(n) = \frac 1 n \sum_{k=0}^{n-1}{f(\text{gcd}(n, k))} = \frac 1 n \sum_{k|n}{f(k)\phi(n/k)}. \]
2222

23-
\kactlimport{IntPerm.h}
24-
\kactlimport{PermGroup.h}
23+
% \kactlimport{IntPerm.h}
24+
% \kactlimport{PermGroup.h}
2525

2626
\section{Partitions and subsets}
2727
\subsection{Partition function}
@@ -162,7 +162,7 @@ \section{Young Tableaux}
162162
% 300iq Disjoint LIS
163163
% msg camp 2014 "sequence shape"
164164

165-
\kactlimport{RSK.h}
165+
% \kactlimport{RSK.h}
166166
% \kactlimport{RSKrecover.h}
167167

168168
\section{Other}

‎Implementations/content/contest/Snippets.md

Copy file name to clipboardExpand all lines: Implementations/content/contest/Snippets.md
+4-4Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -51,7 +51,8 @@ void inp(vi& v) {
5151
}
5252
5353
void solve(int tc) {
54-
cerr << "Doing TC #" << tc << " " << (db)(clock()-beg)/CLOCKS_PER_SEC << "\n";
54+
// cerr << "Doing TC #" << tc << endl;
55+
// dbg_time();
5556
${0}
5657
}
5758
@@ -70,10 +71,9 @@ int main() {
7071
```
7172
// make sure to intialize ALL GLOBAL VARS between tcs!
7273
73-
clock_t beg = clock();
74-
7574
void solve(int tc) {
76-
// cerr << "Doing TC #" << tc << " " << (db)(clock()-beg)/CLOCKS_PER_SEC << "\n";
75+
// cerr << "Doing TC #" << tc << endl;
76+
// dbg_time();
7777
${0}
7878
}
7979

‎Implementations/content/contest/TemplateLong.cpp

Copy file name to clipboardExpand all lines: Implementations/content/contest/TemplateLong.cpp
+6-6Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@ using namespace std;
33

44
using ll = long long;
55
using db = long double; // or double, if TL is tight
6-
using str = string; // yay python!
6+
using str = string; // yay python!
77

88
using pi = pair<int,int>;
99
using pl = pair<ll,ll>;
@@ -12,10 +12,10 @@ using pd = pair<db,db>;
1212
using vi = vector<int>;
1313
using vb = vector<bool>;
1414
using vl = vector<ll>;
15-
using vd = vector<db>;
15+
using vd = vector<db>;
1616
using vs = vector<str>;
1717
using vpi = vector<pi>;
18-
using vpl = vector<pl>;
18+
using vpl = vector<pl>;
1919
using vpd = vector<pd>;
2020

2121
#define tcT template<class T
@@ -47,7 +47,7 @@ tcT> using PR = pair<T,T>;
4747
#define rtn return
4848

4949
#define lb lower_bound
50-
#define ub upper_bound
50+
#define ub upper_bound
5151
tcT> int lwb(V<T>& a, const T& b) { return int(lb(all(a),b)-bg(a)); }
5252
tcT> int upb(V<T>& a, const T& b) { return int(ub(all(a),b)-bg(a)); }
5353

@@ -61,9 +61,9 @@ tcT> int upb(V<T>& a, const T& b) { return int(ub(all(a),b)-bg(a)); }
6161

6262
const int MOD = 1e9+7; // 998244353;
6363
const int MX = 2e5+5;
64-
const ll INF = 1e18; // not too close to LLONG_MAX
64+
const ll BIG = 1e18; // not too close to LLONG_MAX
6565
const db PI = acos((db)-1);
66-
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!
66+
const int dx[4]{1,0,-1,0}, dy[4]{0,1,0,-1}; // for every grid problem!!
6767
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
6868
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
6969

‎Implementations/content/contest/TemplateLong_Old.cpp

Copy file name to clipboardExpand all lines: Implementations/content/contest/TemplateLong_Old.cpp
+6-6Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@ using namespace std;
33

44
using ll = long long;
55
using db = long double; // or double, if TL is tight
6-
using str = string; // yay python!
6+
using str = string; // yay python!
77

88
using pi = pair<int,int>;
99
using pl = pair<ll,ll>;
@@ -12,10 +12,10 @@ using pd = pair<db,db>;
1212
using vi = vector<int>;
1313
using vb = vector<bool>;
1414
using vl = vector<ll>;
15-
using vd = vector<db>;
15+
using vd = vector<db>;
1616
using vs = vector<str>;
1717
using vpi = vector<pi>;
18-
using vpl = vector<pl>;
18+
using vpl = vector<pl>;
1919
using vpd = vector<pd>;
2020

2121
#define tcT template<class T
@@ -47,7 +47,7 @@ tcT> using PR = pair<T,T>;
4747
#define rtn return
4848

4949
#define lb lower_bound
50-
#define ub upper_bound
50+
#define ub upper_bound
5151
tcT> int lwb(V<T>& a, const T& b) { return int(lb(all(a),b)-bg(a)); }
5252
tcT> int upb(V<T>& a, const T& b) { return int(ub(all(a),b)-bg(a)); }
5353

@@ -61,9 +61,9 @@ tcT> int upb(V<T>& a, const T& b) { return int(ub(all(a),b)-bg(a)); }
6161

6262
const int MOD = 1e9+7; // 998244353;
6363
const int MX = 2e5+5;
64-
const ll INF = 1e18; // not too close to LLONG_MAX
64+
const ll BIG = 1e18; // not too close to LLONG_MAX
6565
const db PI = acos((db)-1);
66-
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!
66+
const int dx[4]{1,0,-1,0}, dy[4]{0,1,0,-1}; // for every grid problem!!
6767
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
6868
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
6969

‎Implementations/content/contest/TemplateShort.cpp

Copy file name to clipboardExpand all lines: Implementations/content/contest/TemplateShort.cpp
+4-87Lines changed: 4 additions & 87 deletions
Original file line numberDiff line numberDiff line change
@@ -2,118 +2,35 @@
22
using namespace std;
33

44
using ll = long long;
5-
using db = long double; // or double, if TL is tight
6-
using str = string; // yay python!
7-
5+
using db = long double; // or double if tight TL
86
using pi = pair<int,int>;
9-
using pl = pair<ll,ll>;
10-
using pd = pair<db,db>;
11-
127
using vi = vector<int>;
13-
using vb = vector<bool>;
14-
using vl = vector<ll>;
15-
using vd = vector<db>;
16-
using vs = vector<str>;
17-
using vpi = vector<pi>;
18-
using vpl = vector<pl>;
19-
using vpd = vector<pd>;
20-
218
#define tcT template<class T
22-
#define tcTU tcT, class U
23-
// ^ lol this makes everything look weird but I'll try it
249
tcT> using V = vector<T>;
25-
tcT, size_t SZ> using AR = array<T,SZ>;
26-
tcT> using PR = pair<T,T>;
2710

28-
// pairs
2911
#define mp make_pair
3012
#define f first
3113
#define s second
3214

33-
// vectors
34-
// oops size(x), rbegin(x), rend(x) need C++17
3515
#define sz(x) int((x).size())
36-
#define bg(x) begin(x)
37-
#define all(x) bg(x), end(x)
38-
#define rall(x) x.rbegin(), x.rend()
39-
#define sor(x) sort(all(x))
16+
#define all(x) begin(x), end(x)
4017
#define rsz resize
41-
#define ins insert
42-
#define ft front()
4318
#define bk back()
4419
#define pb push_back
45-
#define eb emplace_back
46-
#define pf push_front
47-
#define rtn return
4820

49-
#define lb lower_bound
50-
#define ub upper_bound
51-
tcT> int lwb(V<T>& a, const T& b) { return int(lb(all(a),b)-bg(a)); }
52-
tcT> int upb(V<T>& a, const T& b) { return int(ub(all(a),b)-bg(a)); }
53-
54-
// loops
5521
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
5622
#define F0R(i,a) FOR(i,0,a)
5723
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
5824
#define R0F(i,a) ROF(i,0,a)
59-
#define rep(a) F0R(_,a)
6025
#define each(a,x) for (auto& a: x)
6126

62-
const int MOD = 1e9+7;
63-
const int MX = 2e5+5;
64-
const ll INF = 1e18; // not too close to LLONG_MAX
27+
const int MOD = 1e9+7; // 998244353;
6528
const db PI = acos((db)-1);
66-
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!
67-
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
68-
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
69-
70-
// bitwise ops
71-
// also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
72-
constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
73-
constexpr int bits(int x) { // assert(x >= 0); // make C++11 compatible until USACO updates ...
74-
return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x))
75-
constexpr int p2(int x) { return 1<<x; }
76-
constexpr int msk2(int x) { return p2(x)-1; }
77-
78-
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
79-
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
29+
mt19937 rng(0); // or mt19937_64
8030

8131
tcT> bool ckmin(T& a, const T& b) {
8232
return b < a ? a = b, 1 : 0; } // set a = min(a,b)
8333
tcT> bool ckmax(T& a, const T& b) {
8434
return a < b ? a = b, 1 : 0; }
8535

86-
tcTU> T fstTrue(T lo, T hi, U f) {
87-
hi ++; assert(lo <= hi); // assuming f is increasing
88-
while (lo < hi) { // find first index such that f is true
89-
T mid = lo+(hi-lo)/2;
90-
f(mid) ? hi = mid : lo = mid+1;
91-
}
92-
return lo;
93-
}
94-
tcTU> T lstTrue(T lo, T hi, U f) {
95-
lo --; assert(lo <= hi); // assuming f is decreasing
96-
while (lo < hi) { // find first index such that f is true
97-
T mid = lo+(hi-lo+1)/2;
98-
f(mid) ? lo = mid : hi = mid-1;
99-
}
100-
return lo;
101-
}
102-
tcT> void remDup(vector<T>& v) { // sort and remove duplicates
103-
sort(all(v)); v.erase(unique(all(v)),end(v)); }
104-
tcTU> void erase(T& t, const U& u) { // don't erase
105-
auto it = t.find(u); assert(it != end(t));
106-
t.erase(it); } // element that doesn't exist from (multi)set
107-
108-
109-
void DBG() { cerr << "]" << endl; }
110-
template<class H, class... T> void DBG(H h, T... t) {
111-
cerr << h; if (sizeof...(t)) cerr << ", ";
112-
DBG(t...); }
113-
#ifdef LOCAL // compile with -DLOCAL
114-
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
115-
#else
116-
#define dbg(...) 0
117-
#endif
118-
11936
int main() { cin.tie(0)->sync_with_stdio(0); }

‎Implementations/content/contest/CppIO_test.cpp renamed to ‎Implementations/content/contest/old/CppIO_test.cpp

Copy file name to clipboard
File renamed without changes.

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.