From d1791b90ae00a4f688218a9810e55d1db5311cdc Mon Sep 17 00:00:00 2001 From: Anthony Wang Date: Tue, 6 Oct 2020 17:25:38 -0500 Subject: Restructured directories --- 15/day1/comehome.cpp | 44 ++++ 15/day3/camelot.cpp | 71 +++++++ 16/day1/tractor.cpp | 30 +++ 16/day3/lct.cpp | 38 ++++ 16/day3/nickname.cpp | 58 ++++++ 16/day4/iqtest.cpp | 48 +++++ 17/day1/arboreal.cpp | 85 ++++++++ 17/day1/ingrass.cpp | 35 ++++ 17/day1/palindrome.cpp | 30 +++ 17/day2/cookie.cpp | 37 ++++ 17/day2/lazybubblesort.cpp | 20 ++ 17/day3/balancing.cpp | 23 +++ 17/day3/timeline.cpp | 41 ++++ 17/day4/knights.cpp | 91 ++++++++ 17/day4/stock_trading.cpp | 21 ++ 17/day4/tuning.cpp | 22 ++ 17/day5/trip.cpp | 41 ++++ 18/day1/fanfiction.cpp | 85 ++++++++ 18/day1/grazing.cpp | 62 ++++++ 18/day1/tastyhay.cpp | 32 +++ 18/day2/cowcliquer.cpp | 39 ++++ 18/day2/grader.h | 55 +++++ 18/day2/sweetgrass.cpp | 66 ++++++ 18/day5/cowmooting.cpp | 35 ++++ 18/day5/mootube.cpp | 78 +++++++ 19/day1/out | 1 + 19/day1/palindrometer.cpp | 22 ++ 19/day1/retemordnilap.cpp | 42 ++++ 19/day1/test.sh | 9 + 19/day1/treedist.cpp | 44 ++++ 19/day2/mana.cpp | 31 +++ 19/day2/themepark.cpp | 42 ++++ 20/day1/repl.cpp | 43 ++++ 20/day1/tri.cpp | 42 ++++ 20/day2/meet.cpp | 32 +++ 20/day2/meet_slow.cpp | 97 +++++++++ 20/day2/reopen.cpp | 29 +++ 20/day2/triangles.cpp | 45 ++++ 20/day2/triangles_gen.cpp | 24 +++ 20/day3/treemst.cpp | 44 ++++ 20/day4/extra.cpp | 30 +++ 20/day6/cowputing | 29 +++ 20/day6/friend.cpp | 29 +++ 20/day6/grader.cc | 467 ++++++++++++++++++++++++++++++++++++++++++ 20/day6/milkvisits.cpp | 61 ++++++ 20/practice/babynames.cpp | 93 +++++++++ 20/practice/cowforce.cpp | 42 ++++ 20/practice/data | 10 + 20/practice/debug | 0 20/practice/guess.cpp | 6 + 20/practice/test_grader.cpp | 264 ++++++++++++++++++++++++ 2015/day1/comehome.cpp | 44 ---- 2015/day3/camelot.cpp | 71 ------- 2016/day1/tractor.cpp | 30 --- 2016/day3/lct.cpp | 38 ---- 2016/day3/nickname.cpp | 58 ------ 2016/day4/iqtest.cpp | 48 ----- 2017/day1/arboreal.cpp | 85 -------- 2017/day1/ingrass.cpp | 35 ---- 2017/day1/palindrome.cpp | 30 --- 2017/day2/cookie.cpp | 37 ---- 2017/day2/lazybubblesort.cpp | 20 -- 2017/day3/balancing.cpp | 23 --- 2017/day3/timeline.cpp | 41 ---- 2017/day4/knights.cpp | 91 -------- 2017/day4/stock_trading.cpp | 21 -- 2017/day4/tuning.cpp | 22 -- 2017/day5/trip.cpp | 41 ---- 2018/day1/fanfiction.cpp | 85 -------- 2018/day1/grazing.cpp | 62 ------ 2018/day1/tastyhay.cpp | 32 --- 2018/day2/cowcliquer.cpp | 39 ---- 2018/day2/grader.h | 55 ----- 2018/day2/sweetgrass.cpp | 66 ------ 2018/day5/cowmooting.cpp | 35 ---- 2018/day5/mootube.cpp | 78 ------- 2019/day1/out | 1 - 2019/day1/palindrometer.cpp | 22 -- 2019/day1/retemordnilap.cpp | 42 ---- 2019/day1/test.sh | 9 - 2019/day1/treedist.cpp | 44 ---- 2019/day2/mana.cpp | 31 --- 2019/day2/themepark.cpp | 42 ---- 2020/day1/repl.cpp | 43 ---- 2020/day1/tri.cpp | 42 ---- 2020/day2/meet.cpp | 32 --- 2020/day2/meet_slow.cpp | 97 --------- 2020/day2/reopen.cpp | 29 --- 2020/day2/triangles.cpp | 45 ---- 2020/day2/triangles_gen.cpp | 24 --- 2020/day3/treemst.cpp | 44 ---- 2020/day4/extra.cpp | 30 --- 2020/day6/cowputing | 29 --- 2020/day6/friend.cpp | 29 --- 2020/day6/grader.cc | 467 ------------------------------------------ 2020/day6/milkvisits.cpp | 61 ------ 2020/practice/babynames.cpp | 93 --------- 2020/practice/cowforce.cpp | 42 ---- 2020/practice/data | 10 - 2020/practice/debug | 0 2020/practice/guess.cpp | 6 - 2020/practice/test_grader.cpp | 264 ------------------------ 102 files changed, 2765 insertions(+), 2765 deletions(-) create mode 100644 15/day1/comehome.cpp create mode 100644 15/day3/camelot.cpp create mode 100644 16/day1/tractor.cpp create mode 100644 16/day3/lct.cpp create mode 100644 16/day3/nickname.cpp create mode 100644 16/day4/iqtest.cpp create mode 100644 17/day1/arboreal.cpp create mode 100644 17/day1/ingrass.cpp create mode 100644 17/day1/palindrome.cpp create mode 100644 17/day2/cookie.cpp create mode 100644 17/day2/lazybubblesort.cpp create mode 100644 17/day3/balancing.cpp create mode 100644 17/day3/timeline.cpp create mode 100644 17/day4/knights.cpp create mode 100644 17/day4/stock_trading.cpp create mode 100644 17/day4/tuning.cpp create mode 100644 17/day5/trip.cpp create mode 100644 18/day1/fanfiction.cpp create mode 100644 18/day1/grazing.cpp create mode 100644 18/day1/tastyhay.cpp create mode 100644 18/day2/cowcliquer.cpp create mode 100644 18/day2/grader.h create mode 100644 18/day2/sweetgrass.cpp create mode 100644 18/day5/cowmooting.cpp create mode 100644 18/day5/mootube.cpp create mode 100644 19/day1/out create mode 100644 19/day1/palindrometer.cpp create mode 100644 19/day1/retemordnilap.cpp create mode 100644 19/day1/test.sh create mode 100644 19/day1/treedist.cpp create mode 100644 19/day2/mana.cpp create mode 100644 19/day2/themepark.cpp create mode 100644 20/day1/repl.cpp create mode 100644 20/day1/tri.cpp create mode 100644 20/day2/meet.cpp create mode 100644 20/day2/meet_slow.cpp create mode 100644 20/day2/reopen.cpp create mode 100644 20/day2/triangles.cpp create mode 100644 20/day2/triangles_gen.cpp create mode 100644 20/day3/treemst.cpp create mode 100644 20/day4/extra.cpp create mode 100644 20/day6/cowputing create mode 100644 20/day6/friend.cpp create mode 100644 20/day6/grader.cc create mode 100644 20/day6/milkvisits.cpp create mode 100644 20/practice/babynames.cpp create mode 100644 20/practice/cowforce.cpp create mode 100644 20/practice/data create mode 100644 20/practice/debug create mode 100644 20/practice/guess.cpp create mode 100644 20/practice/test_grader.cpp delete mode 100644 2015/day1/comehome.cpp delete mode 100644 2015/day3/camelot.cpp delete mode 100644 2016/day1/tractor.cpp delete mode 100644 2016/day3/lct.cpp delete mode 100644 2016/day3/nickname.cpp delete mode 100644 2016/day4/iqtest.cpp delete mode 100644 2017/day1/arboreal.cpp delete mode 100644 2017/day1/ingrass.cpp delete mode 100644 2017/day1/palindrome.cpp delete mode 100644 2017/day2/cookie.cpp delete mode 100644 2017/day2/lazybubblesort.cpp delete mode 100644 2017/day3/balancing.cpp delete mode 100644 2017/day3/timeline.cpp delete mode 100644 2017/day4/knights.cpp delete mode 100644 2017/day4/stock_trading.cpp delete mode 100644 2017/day4/tuning.cpp delete mode 100644 2017/day5/trip.cpp delete mode 100644 2018/day1/fanfiction.cpp delete mode 100644 2018/day1/grazing.cpp delete mode 100644 2018/day1/tastyhay.cpp delete mode 100644 2018/day2/cowcliquer.cpp delete mode 100644 2018/day2/grader.h delete mode 100644 2018/day2/sweetgrass.cpp delete mode 100644 2018/day5/cowmooting.cpp delete mode 100644 2018/day5/mootube.cpp delete mode 100644 2019/day1/out delete mode 100644 2019/day1/palindrometer.cpp delete mode 100644 2019/day1/retemordnilap.cpp delete mode 100644 2019/day1/test.sh delete mode 100644 2019/day1/treedist.cpp delete mode 100644 2019/day2/mana.cpp delete mode 100644 2019/day2/themepark.cpp delete mode 100644 2020/day1/repl.cpp delete mode 100644 2020/day1/tri.cpp delete mode 100644 2020/day2/meet.cpp delete mode 100644 2020/day2/meet_slow.cpp delete mode 100644 2020/day2/reopen.cpp delete mode 100644 2020/day2/triangles.cpp delete mode 100644 2020/day2/triangles_gen.cpp delete mode 100644 2020/day3/treemst.cpp delete mode 100644 2020/day4/extra.cpp delete mode 100644 2020/day6/cowputing delete mode 100644 2020/day6/friend.cpp delete mode 100644 2020/day6/grader.cc delete mode 100644 2020/day6/milkvisits.cpp delete mode 100644 2020/practice/babynames.cpp delete mode 100644 2020/practice/cowforce.cpp delete mode 100644 2020/practice/data delete mode 100644 2020/practice/debug delete mode 100644 2020/practice/guess.cpp delete mode 100644 2020/practice/test_grader.cpp diff --git a/15/day1/comehome.cpp b/15/day1/comehome.cpp new file mode 100644 index 0000000..e9c72db --- /dev/null +++ b/15/day1/comehome.cpp @@ -0,0 +1,44 @@ +#include +#define f first +#define s second +#define int long long +using namespace std; +using ll = long long; +using ii = pair; + +ii dist[100001], src[100001]; +vector G[100001]; + +signed main() { + ios_base::sync_with_stdio(0), cin.tie(0); + + int N, M, K; cin >> N >> M >> K; + while (M--) { + int A, B, D; cin >> A >> B >> D; + G[A].emplace_back(D, B), G[B].emplace_back(D, A); + } + + priority_queue, greater> pq; + memset(dist, '?', sizeof dist); + for (int i = 1; i <= K; ++i) dist[i] = ii(0, 0), pq.emplace(0, i); + while (pq.size()) { + int d = pq.top().f, u = pq.top().s; + pq.pop(); + if (d > dist[u].s) continue; + for (auto & p : G[u]) { + int d = p.f, v = p.s; + if ((dist[u].s + d == dist[v].f && src[v].f == u) || (dist[u].s + d == dist[d].s && src[v].s == u)) continue; + if (dist[u].s + d <= dist[v].f) { + dist[v].s = dist[v].f, src[v].s = src[v].f; + dist[v].f = dist[u].s + d, src[v].f = u; + pq.emplace(dist[v].s, v); + } + else if (dist[u].s + d <= dist[v].s) { + dist[v].s = dist[u].s + d, src[v].s = u; + pq.emplace(dist[v].s, v); + } + } + } + + cout << (dist[N].s <= 1e18 ? dist[N].s : -1) << '\n'; +} \ No newline at end of file diff --git a/15/day3/camelot.cpp b/15/day3/camelot.cpp new file mode 100644 index 0000000..ea96663 --- /dev/null +++ b/15/day3/camelot.cpp @@ -0,0 +1,71 @@ +#include +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair; + +const int dx[] = { 2, 1, -1, -2, -2, -1, 1, 2 }; +const int dy[] = { 1, 2, 2, 1, -1, -2, -2, -1 }; + +int d[44][44]; +bool b[44][44]; +inline int & dist(int i, int j) { return d[i + 22][j + 22]; } +inline bool & vis(int i, int j) { return b[i + 22][j + 22]; } + +ii P[202]; +int dp[202][101]; + +int main() { + ios_base::sync_with_stdio(0), cin.tie(0); + + int N, R, C; + cin >> N >> R >> C; + for (int i = 0; i < N; ++i) { + cin >> P[i].f >> P[i].s; + --P[i].f, --P[i].s; + } + + // BFS to compute distances + auto valid = [&R, &C](int i, int j) { return i > -R && i < R && j > -C && j < C; }; + dist(0, 0) = 0; + queue q; + q.emplace(0, 0); + while (q.size()) { + ii u = q.front(); + q.pop(); + if (vis(u.f, u.s)) continue; + vis(u.f, u.s) = 1; + for (int d = 0; d < 8; ++d) { + ii v(u.f + dx[d], u.s + dy[d]); + if (valid(v.f, v.s) && !vis(v.f, v.s)) { + dist(v.f, v.s) = dist(u.f, u.s) + 1; + q.push(v); + } + } + } + + // O(R^2 * C^2 * N^2) + int ans = 1e9; + for (int a = 0; a < R; ++a) { + for (int b = 0; b < C; ++b) { + for (int c = a; c < R; ++c) { + for (int d = 0; d < C; ++d) { + if (a == c && b == d) continue; + // First meetup location: (a, b) + // Second meetup location: (c, d) + memset(dp, '?', sizeof dp); + dp[0][0] = 0; + for (int i = 0; i < N; ++i) { + for (int j = 0; j <= min(i, N / 2); ++j) { + dp[i + 1][j] = min(dist(P[i].f - a, P[i].s - b) + dp[i][j], dp[i + 1][j]); + dp[i + 1][j + 1] = min(dist(P[i].f - c, P[i].s - d) + dp[i][j], dp[i + 1][j + 1]); + } + } + ans = min(dp[N][N / 2], ans); + } + } + } + } + cout << ans << '\n'; +} \ No newline at end of file diff --git a/16/day1/tractor.cpp b/16/day1/tractor.cpp new file mode 100644 index 0000000..6318ff7 --- /dev/null +++ b/16/day1/tractor.cpp @@ -0,0 +1,30 @@ +#include +using namespace std; + +int w[55], v[55], dp[55][1001]; +vector G[55]; + +void dfs(int i) { + dp[i][v[i]] = w[i]; + for (int j : G[i]) { + dfs(j); + for (int k = 1000; k >= 0; --k) { + for (int l = k; l >= 0; --l) dp[i][k] = min(dp[i][l] + dp[j][k - l], dp[i][k]); + } + } + dp[i][0] = 0; +} + +int main() { + ios_base::sync_with_stdio(0), cin.tie(0); + int N, W; cin >> N >> W; + for (int i = 1, p; i <= N; ++i) { + cin >> w[i] >> v[i] >> p; + G[p].push_back(i); + } + memset(dp, '?', sizeof dp); + dfs(0); + int ans = 1000; + while (dp[0][ans] > W) --ans; + cout << ans << '\n'; +} \ No newline at end of file diff --git a/16/day3/lct.cpp b/16/day3/lct.cpp new file mode 100644 index 0000000..77961fe --- /dev/null +++ b/16/day3/lct.cpp @@ -0,0 +1,38 @@ +#include +#define f first +#define s second +using namespace std; +using ii = pair; +template class fenwick_tree { +private: vector FT; +public: + fenwick_tree(int N) { FT.assign(N + 1, 0); } + void update(int x, T val) { if (x > 0) for (; x < FT.size(); x += x & -x) FT[x] += val; } + T query(int x) { T ret = 0; if (x > 0) for (; x > 0; x -= x & -x) ret += FT[x]; return ret; } + T query(int x, int y) { return query(y) - query(x - 1); } +}; + +int N, Q, ans[200002]; +ii E[200002]; +pair q[200002]; + +int main() { + ios_base::sync_with_stdio(0), cin.tie(0); + + cin >> N >> Q; + fenwick_tree FT(N); + for (int i = 0; i < N - 1; ++i) { + cin >> E[i].f >> E[i].s; + if (E[i].f > E[i].s) swap(E[i].f, E[i].s); + FT.update(E[i].s, 1); + } + for (int i = 0; i < Q; ++i) { + cin >> q[i].f.f >> q[i].f.s; q[i].s = i; + } + sort(E, E + N - 1), sort(q, q + Q); + for (int i = 0, j = 0; i < Q; ++i) { + while (j < N - 1 && E[j].f < q[i].f.f) FT.update(E[j++].s, -1); + ans[q[i].s] = q[i].f.s - q[i].f.f + 1 - FT.query(q[i].f.s); + } + for (int i = 0; i < Q; ++i) cout << ans[i] << '\n'; +} \ No newline at end of file diff --git a/16/day3/nickname.cpp b/16/day3/nickname.cpp new file mode 100644 index 0000000..7e28696 --- /dev/null +++ b/16/day3/nickname.cpp @@ -0,0 +1,58 @@ +#include +using namespace std; + +vector suffix_array(string& S) { + int N = S.length(); + vector SA(N), rank(N); + for (int i = 0; i < N; i++) { + SA[i] = N - i - 1; + rank[i] = S[i]; + } + stable_sort(SA.begin(), SA.end(), [&S](int i, int j) { return S[i] < S[j]; }); + for (int t = 1; t < N; t <<= 1) { + vector tmp(rank); + for (int i = 0; i < N; i++) { + bool s = i && SA[i - 1] + t < N && tmp[SA[i]] == tmp[SA[i - 1]] && tmp[SA[i] + (t >> 1)] == tmp[SA[i - 1] + (t >> 1)]; + rank[SA[i]] = s ? rank[SA[i - 1]] : i; + } + tmp = SA; + vector cnt(N); + for (int i = 0; i < N; i++) cnt[i] = i; + for (int i = 0; i < N; i++) { + if (tmp[i] >= t) SA[cnt[rank[tmp[i] - t]]++] = tmp[i] - t; + } + } + return SA; +} + +vector lcp_array(const vector& SA, string& S) { + int N = S.size(); + vector rank(N), LCP(N - 1); + for (int i = 0; i < N; i++) rank[SA[i]] = i; + int pre = 0; + for (int i = 0; i < N; i++) { + if (rank[i] < N - 1) { + int j = SA[rank[i] + 1]; + while (max(i, j) + pre < S.size() && S[i + pre] == S[j + pre]) pre++; + LCP[rank[i]] = pre; + if (pre > 0) pre--; + } + } + return LCP; +} + +int main() { + int A, B; + string X, Y; + cin >> A >> B >> X >> Y; + string S = X + '$' + Y; + vector SA = suffix_array(S); + vector L = lcp_array(SA, S); + int ans = 0; + for (int i = 0; i < S.size() - 1; ++i) { + if ((SA[i] < A && SA[i + 1] > A) || (SA[i] > A && SA[i + 1] < A)) { + ans = max(L[i], ans); + } + } + cout << ans << '\n'; +} \ No newline at end of file diff --git a/16/day4/iqtest.cpp b/16/day4/iqtest.cpp new file mode 100644 index 0000000..0f55c58 --- /dev/null +++ b/16/day4/iqtest.cpp @@ -0,0 +1,48 @@ +#include +using namespace std; +using ll = long long; + +int N, K, A[400004]; + +inline ll pw(ll base, ll exp) { + ll res = 1; + while (exp) { + if (exp & 1) res = base * res % K; + exp >>= 1, base = base * base % K; + } + return res; +} + +int main() { + ios_base::sync_with_stdio(0), cin.tie(0); + + cin >> N >> K; + for (int i = 0; i < N; ++i) cin >> A[i]; + + ll phi = K, tmp = K; + vector factors, exp; + for (int i = 2; i * i <= K; ++i) { + if (tmp % i == 0) { + while (tmp % i == 0) tmp /= i; + factors.push_back(i), exp.push_back(0); + phi = phi * (i - 1) / i; + } + } + if (tmp > 1) { + factors.push_back(tmp), exp.push_back(0); + phi = phi * (tmp - 1) / tmp; + } + + ll cur = 1, ans = A[0]; + for (int i = 1; i < N; ++i) { + ll x = N - i, y = i; + for (int j = 0; j < factors.size(); ++j) { + while (x % factors[j] == 0) ++exp[j], x /= factors[j]; + while (y % factors[j] == 0) --exp[j], y /= factors[j]; + } + ll tmp = cur = x * pw(y, phi - 1) % K * cur % K; + for (int j = 0; j < factors.size(); ++j) tmp = pw(factors[j], exp[j]) * tmp % K; + ans = (tmp * A[i] + ans) % K; + } + cout << ans; +} \ No newline at end of file diff --git a/17/day1/arboreal.cpp b/17/day1/arboreal.cpp new file mode 100644 index 0000000..659216b --- /dev/null +++ b/17/day1/arboreal.cpp @@ -0,0 +1,85 @@ +#include +#include +#include +#define f first +#define s second +using namespace std; +using namespace __gnu_pbds; +using ii = pair; +template using ordered_set = tree, rb_tree_tag, tree_order_statistics_node_update>; +constexpr int MAXN = 100001; + +vector T[MAXN + 1]; +ordered_set S[4 * MAXN + 4]; + +void build(int l = 0, int r = MAXN, int n = 1) { + if (l == r) { + for (auto& y : T[l]) S[n].insert(y); + } + else { + int m = (l + r) >> 1; + build(l, m, n << 1), build(m + 1, r, n << 1 | 1); + for (auto& y : S[n << 1]) S[n].insert(y); + for (auto& y : S[n << 1 | 1]) S[n].insert(y); + } +} + +int query(int xl, int xr, int yl, int yr, int l = 0, int r = MAXN, int n = 1) { + if (l > r || l > xr || r < xl) return 0; + if (l >= xl && r <= xr) return S[n].order_of_key(yr + 1) - S[n].order_of_key(yl); + else { + int m = (l + r) >> 1; + return query(xl, xr, yl, yr, l, m, n << 1) + query(xl, xr, yl, yr, m + 1, r, n << 1 | 1); + } +} + +ii P[100001]; + +int main() { + ios_base::sync_with_stdio(0), cin.tie(0); + + int N; cin >> N; + for (int i = 0; i < N; ++i) cin >> P[i].f >> P[i].s; + + vector tmp; + for (int i = 0; i < N; ++i) tmp.emplace_back(P[i].f, i); + sort(begin(tmp), end(tmp)); + for (int i = 0; i < N; ++i) { + if (i && tmp[i].f == tmp[i - 1].f) P[tmp[i].s].f = P[tmp[i - 1].s].f; + else P[tmp[i].s].f = i; + } + tmp.clear(); + for (int i = 0; i < N; ++i) tmp.emplace_back(P[i].s, i); + sort(begin(tmp), end(tmp)); + for (int i = 0; i < N; ++i) { + if (i && tmp[i].f == tmp[i - 1].f) P[tmp[i].s].s = P[tmp[i - 1].s].s; + else P[tmp[i].s].s = i; + } + + for (int i = 0; i < N; ++i) T[P[i].f].push_back(P[i].s); + build(); + + vector X, Y; + for (int i = 0; i < N; ++i) X.push_back(P[i]), Y.push_back(P[i]); + + auto cmpy = [](const ii & a, const ii & b) { return a.s < b.s || (a.s == b.s && a.f < b.f); }; + sort(begin(X), end(X)); + sort(begin(Y), end(Y), cmpy); + unique(begin(X), end(X)); + unique(begin(Y), end(Y), cmpy); + + int ans = 0; + for (int i = 0; i < N; ++i) { + auto it = lower_bound(begin(X), end(X), ii(P[i].f, P[i].s)); + int yh = (next(it) != end(X) && next(it)->f == P[i].f ? next(it)->s : MAXN + 1); + int yl = (it != begin(X) && prev(it)->f == P[i].f ? prev(it)->s : -2); + + it = lower_bound(begin(Y), end(Y), ii(P[i].f, P[i].s), cmpy); + int xh = (next(it) != end(Y) && next(it)->s == P[i].s ? next(it)->f : MAXN + 1); + int xl = (it != begin(Y) && prev(it)->s == P[i].s ? prev(it)->f : -2); + + int q = query(xl + 1, xh - 1, yl + 1, yh - 1); + if (q > 1) ++ans; + } + cout << ans << '\n'; +} diff --git a/17/day1/ingrass.cpp b/17/day1/ingrass.cpp new file mode 100644 index 0000000..984fe20 --- /dev/null +++ b/17/day1/ingrass.cpp @@ -0,0 +1,35 @@ +#include +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair; + +ii P[50005]; + +bool ccw(ii a, ii b, ii c) { return (ll)(b.f - a.f) * (c.s - a.s) - (ll)(c.f - a.f) * (b.s - a.s) > 0; } + +int main() { + ios_base::sync_with_stdio(0), cin.tie(0); + int N; cin >> N; + for (int i = 0; i < N; ++i) cin >> P[i].f >> P[i].s; + int m = min_element(P, P + N) - P; + vector> A; + for (int i = 0; i < N; ++i) { + if (i != m) A.emplace_back(atan2(P[i].s - P[m].s, P[i].f - P[m].f), i); + } + sort(begin(A), end(A)); + vector S; + vector ans; + for (int i = 0; i < A.size(); ++i) { + ans.emplace_back(m, A[i].s); + while (i) { + ans.emplace_back(A[i].s, S.back()); + if (S.size() <= 1 || ccw(P[A[i].s], P[S[S.size() - 2]], P[S.back()])) break; + else S.pop_back(); + } + S.push_back(A[i].s); + } + cout << 3 * N - 2 * S.size() - 4 << ' ' << ans.size() << '\n'; + for (auto& p : ans) cout << p.f + 1 << ' ' << p.s + 1 << '\n'; +} \ No newline at end of file diff --git a/17/day1/palindrome.cpp b/17/day1/palindrome.cpp new file mode 100644 index 0000000..dbf5fd6 --- /dev/null +++ b/17/day1/palindrome.cpp @@ -0,0 +1,30 @@ +#include +using namespace std; + +int N, s[100001], dp[100001][606]; +inline int & get(int i, int j) { return dp[i][N - j - i + 301]; } + +int main() { + ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); + + cin >> N; + for (int i = 0; i < N; ++i) cin >> s[i]; + + memset(dp, '?', sizeof dp); + get(0, N) = 0; + for (int i = 0; i < N; ++i) { + for (int j = min(N - i + 300, N); j >= max(N - i - 300, i); --j) { + get(i + 1, j) = min(get(i, j) + 1, get(i + 1, j)); + get(i, j - 1) = min(get(i, j) + 1, get(i, j - 1)); + if (s[i] == s[j - 1]) get(i + 1, j - 1) = min(get(i, j), get(i + 1, j - 1)); + } + } + + int ans = 1e9; + for (int i = 0; i < N; ++i) { + if (N - 2 * i + 301 >= 0 && N - 2 * i + 301 < 606) ans = min(get(i, i), ans); + if (N - 2 * i + 300 >= 0 && N - 2 * i + 300 < 606) ans = min(get(i, i + 1), ans); + } + if (ans <= 300) cout << ans << '\n'; + else cout << "many\n"; +} \ No newline at end of file diff --git a/17/day2/cookie.cpp b/17/day2/cookie.cpp new file mode 100644 index 0000000..d03e72f --- /dev/null +++ b/17/day2/cookie.cpp @@ -0,0 +1,37 @@ +#include +#define f first +#define s second +using namespace std; +using ll = long long; +using pl = pair; + +ll C[5005], D[5005]; +pl DP[5005][5005]; + +int main() { + ios_base::sync_with_stdio(0), cin.tie(0); + + ll N, T, RA, RB; + cin >> N >> T >> RA >> RB; + for (int i = 0; i < N; ++i) cin >> C[i]; + for (int i = 0; i < N; ++i) cin >> D[i]; + + memset(DP, 63, sizeof(DP)); + DP[0][0] = pl(0, 0); + ll ans = T; + for (int i = 0; i <= N; ++i) { + for (int j = 0; j <= N; ++j) { + ll r = 1 + i * RA + j * RB; + if (i < N) { + ll t = max((C[i] + DP[i][j].s + r - 1) / r, 0ll); + DP[i + 1][j] = min(pl(DP[i][j].f + t, -t * r + C[i] + DP[i][j].s), DP[i + 1][j]); + } + if (j < N) { + ll t = max((D[j] + DP[i][j].s + r - 1) / r, 0ll); + DP[i][j + 1] = min(pl(DP[i][j].f + t, -t * r + D[j] + DP[i][j].s), DP[i][j + 1]); + } + ans = min(DP[i][j].f + max((T + DP[i][j].s + r - 1) / r, 0ll), ans); + } + } + cout << ans << '\n'; +} \ No newline at end of file diff --git a/17/day2/lazybubblesort.cpp b/17/day2/lazybubblesort.cpp new file mode 100644 index 0000000..8395298 --- /dev/null +++ b/17/day2/lazybubblesort.cpp @@ -0,0 +1,20 @@ +#include +using namespace std; + +int A[100001]; + +int main() { + int N, K; cin >> N >> K; + for (int i = 0; i < N; ++i) cin >> A[i]; + multiset S; + vector ans; + for (int i = 0; i < N; ++i) { + if (S.size() < K || A[i] > *begin(S)) { + if (S.size() == K) ans.push_back(*begin(S)), S.erase(begin(S)); + S.insert(A[i]); + } + else ans.push_back(A[i]); + } + while (S.size()) ans.push_back(*begin(S)), S.erase(begin(S)); + for (auto& x : ans) cout << x << '\n'; +} \ No newline at end of file diff --git a/17/day3/balancing.cpp b/17/day3/balancing.cpp new file mode 100644 index 0000000..c5fa7c6 --- /dev/null +++ b/17/day3/balancing.cpp @@ -0,0 +1,23 @@ +#include +using namespace std; + +int main() { + ios_base::sync_with_stdio(0), cin.tie(0); + string S; cin >> S; + int N = S.size(), cnt = 0; + if (count(begin(S), end(S), 'G') << 1 != N) { + cout << "NO\n"; + return 0; + } + unordered_set M[2]; + for (int i = 0; i < N; ++i) { + if (S[i] != S[(i-1+N)%N]) M[S[i] == 'G'].insert(cnt); + cnt += (S[i] == 'G' ? 1 : -1); + if (S[i] != S[(i+1)%N] && M[S[i] == 'G'].find(cnt - (S[i] == 'G' ? 1 : -1)) != end(M[S[i] == 'G'])) { + cout << "YES\n"; + return 0; + } + } + cout << "NO\n"; + return 0; +} \ No newline at end of file diff --git a/17/day3/timeline.cpp b/17/day3/timeline.cpp new file mode 100644 index 0000000..a6b8e30 --- /dev/null +++ b/17/day3/timeline.cpp @@ -0,0 +1,41 @@ +#include +#define f first +#define s second +using namespace std; +using ii = pair; + +int dist[5005]; +vector G[5005]; + +int main() { + ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); + int N, M, C; cin >> N >> M >> C; + for (int u = 1; u <= N; ++u) { + int s, t; cin >> s >> t; + G[u].emplace_back(-s, 0); + G[0].emplace_back(t, u); + } + while (C--) { + int a, b, x; cin >> a >> b >> x; + G[a].emplace_back(-x, b); + } + memset(dist, '?', sizeof dist); + dist[0] = 0; + for (int i = 0; i < N; ++i) { + for (int u = 0; u <= N; ++u) { + for (auto& v : G[u]) { + if (dist[u] + v.f < dist[v.s]) dist[v.s] = dist[u] + v.f; + } + } + } + for (int u = 0; u <= N; ++u) { + for (auto& v : G[u]) { + if (dist[u] < 0 || dist[u] > M || dist[u] + v.f < dist[v.s]) { + cout << "impossible\n"; + return 0; + } + } + } + for (int u = 1; u <= N; ++u) cout << dist[u] << '\n'; + return 0; +} \ No newline at end of file diff --git a/17/day4/knights.cpp b/17/day4/knights.cpp new file mode 100644 index 0000000..784abfc --- /dev/null +++ b/17/day4/knights.cpp @@ -0,0 +1,91 @@ +#include +using namespace std; +using ll = long long; +constexpr ll INF = 1e12; + +int dx[] = { 2, 1, -1, -2, -2, -1, 1, 2 }; +int dy[] = { 1, 2, 2, 1, -1, -2, -2, -1 }; +char A[101][101]; + +template class max_flow { + struct edge { + int t, rev; + T cap, f; + }; + vector adj[V]; + int dist[V]; + int ptr[V]; + bool bfs(int s, int t) { + memset(dist, -1, sizeof dist); + dist[s] = 0; + queue q({ s }); + while (!q.empty() && dist[t] == -1) { + int n = q.front(); + q.pop(); + for (auto& e : adj[n]) { + if (dist[e.t] == -1 && e.cap != e.f) { + dist[e.t] = dist[n] + 1; + q.push(e.t); + } + } + } + return dist[t] != -1; + } + T augment(int n, T amt, int t) { + if (n == t) return amt; + for (; ptr[n] < adj[n].size(); ptr[n]++) { + edge& e = adj[n][ptr[n]]; + if (dist[e.t] == dist[n] + 1 && e.cap != e.f) { + T flow = augment(e.t, min(amt, e.cap - e.f), t); + if (flow != 0) { + e.f += flow; + adj[e.t][e.rev].f -= flow; + return flow; + } + } + } + return 0; + } +public: + void add(int u, int v, T cap = 1, T rcap=0) { + adj[u].push_back({ v, (int) adj[v].size(), cap, 0 }); + adj[v].push_back({ u, (int) adj[u].size() - 1, rcap, 0 }); + } + T calc(int s, int t) { + T flow = 0; + while (bfs(s, t)) { + memset(ptr, 0, sizeof ptr); + while (T df = augment(s, INF, t)) flow += df; + } + return flow; + } + void clear() { + for (int n = 0; n < V; n++) adj[n].clear(); + } +}; + +int main() { + int R, C; + cin >> R >> C; + int ans = R * C; + for (int i = 0; i < R; ++i) { + for (int j = 0; j < C; ++j) cin >> A[i][j]; + } + + max_flow<101*101> MF; + for (int i = 0; i < R; ++i) { + for (int j = 0; j < C; ++j) { + if (A[i][j] == '#') { --ans; continue; } + if (i + j & 1) { + MF.add(10000, i * C + j, (A[i][j] == 'C' ? INF : 1)); + for (int d = 0; d < 8; ++d) { + int x = i + dx[d], y = j + dy[d]; + if (x < 0 || x >= R || y < 0 || y >= C || A[x][y] == '#') continue; + MF.add(i * C + j, x * C + y, INF); + } + } + else MF.add(i * C + j, 10001, (A[i][j] == 'C' ? INF : 1)); + } + } + cout << ans - MF.calc(10000, 10001) << '\n'; +} \ No newline at end of file diff --git a/17/day4/stock_trading.cpp b/17/day4/stock_trading.cpp new file mode 100644 index 0000000..c2aa679 --- /dev/null +++ b/17/day4/stock_trading.cpp @@ -0,0 +1,21 @@ +#include +using namespace std; +using ll = long long; + +int main() { + ios_base::sync_with_stdio(0), cin.tie(0); + + int N, L; + cin >> N >> L; + + multiset S; + ll ans = 0; + for (int i = 0, b, s; i < N; ++i) { + cin >> b >> s; + ans = max(ans - (i >= L ? *begin(S) : 0) + s, ans); + S.insert({ b, s }); + if (i >= L) S.erase(begin(S)), S.erase(prev(end(S))); + } + for (auto it = S.begin(); L; ++it, --L) ans -= *it; + cout << ans << endl; +} \ No newline at end of file diff --git a/17/day4/tuning.cpp b/17/day4/tuning.cpp new file mode 100644 index 0000000..d2bddd9 --- /dev/null +++ b/17/day4/tuning.cpp @@ -0,0 +1,22 @@ +#include +using namespace std; + +int main() { + ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); + + int N; + cin >> N; + int ans = 1, cnt = 1; + for (int i = 2; i < N; ++i) { + if (cnt) { + cout << ans << ' ' << i << endl; + string s; cin >> s; + s[0] == 'S' ? ++cnt : --cnt; + } + else { + ans = i; + ++cnt; + } + } + cout << (cnt ? ans : N) << endl; +} \ No newline at end of file diff --git a/17/day5/trip.cpp b/17/day5/trip.cpp new file mode 100644 index 0000000..35ded67 --- /dev/null +++ b/17/day5/trip.cpp @@ -0,0 +1,41 @@ +#include +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair; + +vector G[100001]; +unordered_map A[100001], B[100001]; + +ll dfs(int u, int p) { + sort(begin(G[u]), end(G[u])); + ll ret = 0, sa = 1, tmp = 0, l = -1; + ++A[u][0], ++B[u][1e9+7]; + for (auto& v : G[u]) { + if (v.s != p) { + ret += dfs(v.s, u); + ll ca = 0, cb = 0; + for (auto& x : A[v.s]) { + if (x.f < v.f) ca += x.s, A[u][v.f] += x.s; + } + for (auto& x : B[v.s]) { + if (x.f > v.f) cb += x.s, B[u][v.f] += x.s; + } + ret += cb * sa, sa += ca; + if (v.f != l) l = v.f, tmp = ca; + else ret -= cb * tmp, tmp += ca; + } + } + return ret + sa - 1; +} + +int main() { + int N; + cin >> N; + for (int i = 1, a, b, e; i < N; ++i) { + cin >> a >> b >> e; + G[a].emplace_back(e, b), G[b].emplace_back(e, a); + } + cout << dfs(1, 0) << '\n'; +} \ No newline at end of file diff --git a/18/day1/fanfiction.cpp b/18/day1/fanfiction.cpp new file mode 100644 index 0000000..82c06c1 --- /dev/null +++ b/18/day1/fanfiction.cpp @@ -0,0 +1,85 @@ +#include +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair; + +int N, T, c[2552], f[2552], g[2552][26], G[2552][26]; +ll out[2552], dp[2552][2552]; +string B, S[2552]; + +int aho_corasick() { + memset(g, -1, sizeof g), memset(out, 0, sizeof out); + int nodes = 1; + for (int i = 0; i < N; i++) { + int cur = 0; + for (int j = 0; j < S[i].size(); j++) { + if (g[cur][S[i][j] - 'a'] == -1) g[cur][S[i][j] - 'a'] = ++nodes; + cur = g[cur][S[i][j] - 'a']; + } + ++out[cur]; + } + for (int ch = 0; ch < T; ch++) { + if (g[0][ch] == -1) g[0][ch] = 0; + } + memset(f, -1, sizeof f); + queue q; + for (int ch = 0; ch < T; ch++) { + if (g[0][ch] != 0) { + f[g[0][ch]] = 0; + q.push(g[0][ch]); + } + } + while (!q.empty()) { + int state = q.front(); + q.pop(); + for (int ch = 0; ch < T; ch++) { + if (g[state][ch] == -1) continue; + int fail = f[state]; + while (g[fail][ch] == -1) fail = f[fail]; + f[g[state][ch]] = g[fail][ch]; + out[g[state][ch]] += out[g[fail][ch]]; + q.push(g[state][ch]); + } + } + return nodes; +} + +int main() { + ios_base::sync_with_stdio(0), cin.tie(0); + + cin >> N >> T; + for (int i = 0; i < N; ++i) cin >> S[i]; + cin >> B; + int L = B.size(); + for (int i = 0; i < L; ++i) cin >> c[i]; + + int M = aho_corasick(); + + for (int i = 0; i < M; ++i) { + for (int j = 0; j < T; ++j) { + int k = i; + while (g[k][j] == -1) k = f[k]; + G[i][j] = g[k][j]; + } + } + + memset(dp, '?', sizeof dp); + dp[0][0] = 0; + for (int i = 0; i < L; ++i) { + for (int j = 0; j < M; ++j) { + if (!out[j]) { + for (int k = 0; k < T; ++k) { + dp[i + 1][G[j][k]] = min(dp[i][j] + c[i] * (k != B[i] - 'a'), dp[i + 1][G[j][k]]); + } + } + } + } + + ll ans = 1e18; + for (int i = 0; i < M; ++i) { + if (!out[i]) ans = min(dp[L][i], ans); + } + cout << (ans < 1e18 ? ans : -1) << '\n'; +} \ No newline at end of file diff --git a/18/day1/grazing.cpp b/18/day1/grazing.cpp new file mode 100644 index 0000000..dcc8a79 --- /dev/null +++ b/18/day1/grazing.cpp @@ -0,0 +1,62 @@ +#include +#define f first +#define s second +using namespace std; +typedef long long ll; +typedef pair ii; +typedef vector vi; +typedef vector vii; + +const int dx[] = { 1, 0, -1, 0 }; +const int dy[] = { 0, 1, 0, -1 }; + +int N, M, A[11][11], vis[11][11]; +vi G[11][11]; +vii S; + +bool valid(int x, int y) { return x >= 0 && x < N && y >= 0 && y < M; }; + +void dfs(int i, int j) { + vis[i][j] = -1; + for (auto& d : G[i][j]) + if (!vis[i + dx[d]][j + dy[d]]) dfs(i + dx[d], j + dy[d]); + vis[i][j] = 1; + S.emplace_back(i, j); +} + +int main() { + ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); + + cin >> N >> M; + for (int i = 0; i < N; ++i) { + for (int j = 0; j < M; ++j) cin >> A[i][j]; + } + + for (int i = 0; i < N; ++i) { + for (int j = 0; j < M; ++j) { + for (int d = 0; d < 4; ++d) { + if (valid(i + dx[d], j + dy[d]) && A[i + dx[d]][j + dy[d]] <= A[i][j]) + G[i][j].push_back(d); + } + } + } + + for (int i = 0; i < N; ++i) { + for (int j = 0; j < M; ++j) { + if (!vis[i][j]) dfs(i, j); + } + } + + memset(vis, 0, sizeof vis); + int ans = 0; + for (int i = S.size() - 1; i >= 0; --i) { + ii p = S[i]; + ans += A[p.f][p.s]; + for (int d = 0; d < 4; ++d) { + if (valid(p.f + dx[d], p.s + dy[d]) && vis[p.f + dx[d]][p.s + dy[d]]) + ans += A[p.f + dx[d]][p.s + dy[d]]; + } + vis[p.f][p.s] = 1; + } + cout << ans << '\n'; +} \ No newline at end of file diff --git a/18/day1/tastyhay.cpp b/18/day1/tastyhay.cpp new file mode 100644 index 0000000..8ef6d42 --- /dev/null +++ b/18/day1/tastyhay.cpp @@ -0,0 +1,32 @@ +#include +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair; + +int t[100001]; +map cnt, pre; + +int main() { + int N, Q; + cin >> N >> Q; + for (int i = 0; i < N; ++i) cin >> t[i]; + + unordered_map m; + for (int i = N - 1; i >= 0; --i) { + unordered_map tmp; + for (auto x : m) tmp[__gcd(t[i], x.f)] += x.s; + ++tmp[t[i]]; + swap(tmp, m); + for (auto& x : m) cnt[x.f] += x.s; + } + for (auto& x : cnt) pre[x.f] = x.s + (pre.size() ? pre.rbegin()->s : 0); + + while (Q--) { + int a, b; + cin >> a >> b; + auto ia = pre.upper_bound(a - 1), ib = pre.upper_bound(b); + cout << (ib != pre.begin() ? prev(ib)->s : 0) - (ia != pre.begin() ? prev(ia)->s : 0) << '\n'; + } +} \ No newline at end of file diff --git a/18/day2/cowcliquer.cpp b/18/day2/cowcliquer.cpp new file mode 100644 index 0000000..fc7f9e9 --- /dev/null +++ b/18/day2/cowcliquer.cpp @@ -0,0 +1,39 @@ +#include "grader.h" +#include +#define par first +#define sz second +using namespace std; +using ii = pair; +constexpr int INF = 2e9; + +int cnt; +unordered_map s; +vector> m[200002]; + +inline void alloc(string cow) { if (s.find(cow) == end(s)) s[cow] = ++cnt, m[cnt].emplace_back(0, ii(cnt, 1)); } + +inline ii & get(int i, int timestamp) { return prev(upper_bound(begin(m[i]), end(m[i]), make_pair(timestamp, ii(INF, 0))))->second; } + +int find_set(int i, int timestamp) { + int & p = get(i, timestamp).par; + return (p == i) ? i : (p = find_set(p, timestamp)); +} + +void add_friend(string cow1, string cow2, int timestamp) { + alloc(cow1), alloc(cow2); + int i = find_set(s[cow1], timestamp), j = find_set(s[cow2], timestamp); + if (i == j) return; + ii x = get(i, timestamp), y = get(j, timestamp); + if (x.sz < y.sz) swap(i, j); + m[i].emplace_back(timestamp, ii(i, x.sz + y.sz)), m[j].emplace_back(timestamp, ii(i, 0)); +} + +bool check_friend(string cow1, string cow2, int timestamp) { + alloc(cow1), alloc(cow2); + return find_set(s[cow1], timestamp) == find_set(s[cow2], timestamp); +} + +int get_number_of_friends(string cow, int timestamp) { + alloc(cow); + return get(find_set(s[cow], timestamp), timestamp).sz; +} \ No newline at end of file diff --git a/18/day2/grader.h b/18/day2/grader.h new file mode 100644 index 0000000..bbe8639 --- /dev/null +++ b/18/day2/grader.h @@ -0,0 +1,55 @@ +#include + +/* + * You need to implement the following functions: + */ + +void add_friend(std::string cow1, std::string cow2, int timestamp); +bool check_friend(std::string cow1, std::string cow2, int timestamp); +int get_number_of_friends(std::string cow, int timestamp); + +// Commands have the following format: +// A c1 c2 t +// - Calls "add"friend" on cows "c1" and "c2" at timestamp t. You are +// guaranteed that successive calls to A will have increasing values of t. +// C c1 c2 t +// - Calls "check_friend" on cows "c1" and "c2" at timestamp t. +// N c t +// - Calls "get_number_of_friends" on cow "c" at timestamp "t". + +// You don't need to read or understand any of the code below, +// but it may be helpful. + +int main() { + int num_commands; + std::cin >> num_commands; + + for (int i = 0; i < num_commands; ++i) { + std::string command_type; + std::cin >> command_type; + + if (command_type == "A") { + std::string cow1, cow2; + int timestamp; + std::cin >> cow1 >> cow2 >> timestamp; + + add_friend(cow1, cow2, timestamp); + } else if (command_type == "C") { + std::string cow1, cow2; + int timestamp; + std::cin >> cow1 >> cow2 >> timestamp; + + std::string responses[] = {"FALSE", "TRUE"}; + std::cout << responses[check_friend(cow1, cow2, timestamp)] << std::endl; + } else if (command_type == "N") { + std::string cow; + int timestamp; + std::cin >> cow >> timestamp; + + std::cout << get_number_of_friends(cow, timestamp) << std::endl; + } else { + std::cout << "Invalid command type: " << command_type << std::endl; + exit(1); + } + } +} diff --git a/18/day2/sweetgrass.cpp b/18/day2/sweetgrass.cpp new file mode 100644 index 0000000..96380bf --- /dev/null +++ b/18/day2/sweetgrass.cpp @@ -0,0 +1,66 @@ +#include +using namespace std; + +int N, idx[100001]; +bitset<100001> vis, ans; +vector path; +unordered_set G[100001]; + +void solve() { + vis.reset(); + for (int i = 0; i < path.size() - 1; ++i) { + G[path[i]].erase(path[i + 1]); + } + memset(idx, -1, sizeof idx); + for (int i = 0; i < path.size(); ++i) idx[path[i]] = i; + int m = 0; + ans.set(); + for (int i = 0; i < path.size() - 1; ++i) { + m = max(i + 1, m); + queue q; + q.push(path[i]); + while (q.size()) { + int u = q.front(); + q.pop(); + if (vis[u]) continue; + vis[u] = 1; + if (u != path[i] && idx[u] != -1) { + for (int j = m; j < idx[u]; ++j) + ans[j] = 0; + m = max(idx[u], m); + continue; + } + for (auto& v : G[u]) { + if (!vis[v]) q.push(v); + } + } + } + vector out; + for (int i = 1; i < path.size() - 1; ++i) + if (ans[i]) out.push_back(path[i]); + sort(begin(out), end(out)); + cout << out.size() << '\n'; + for (auto& x : out) cout << x << '\n'; +} + +void dfs(int u) { + vis[u] = 1; + path.push_back(u); + if (u == N) { + solve(); + exit(0); + } + for (auto& v : G[u]) { + if (!vis[v]) dfs(v); + } + path.pop_back(); +} + +int main() { + int M; cin >> N >> M; + while (M--) { + int a, b; cin >> a >> b; + G[a].insert(b); + } + dfs(1); +} \ No newline at end of file diff --git a/18/day5/cowmooting.cpp b/18/day5/cowmooting.cpp new file mode 100644 index 0000000..86f6460 --- /dev/null +++ b/18/day5/cowmooting.cpp @@ -0,0 +1,35 @@ +#include +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair; + +vector> G[101]; +ll dist[101][10001]; + +int main() { + int B, M, N; cin >> B >> M >> N; + while (M--) { + int a, b, t, c; cin >> a >> b >> t >> c; + G[a].emplace_back(ii(t, c), b), G[b].emplace_back(ii(t, c), a); + } + memset(dist, '?', sizeof dist); + dist[0][0] = 0; + priority_queue, vector>, greater>> pq; + pq.emplace(0, ii(0, 0)); + while (!pq.empty()) { + ll d = pq.top().f; ii u = pq.top().s; + pq.pop(); + if (d > dist[u.f][u.s]) continue; + for (auto& v : G[u.f]) { + if (u.s + v.f.f < 1e4 && d + v.f.s < dist[v.s][u.s + v.f.f]) { + dist[v.s][u.s + v.f.f] = d + v.f.s; + pq.emplace(dist[v.s][u.s + v.f.f], ii(v.s, u.s + v.f.f)); + } + } + } + int ans = 0; + while (ans < 1e4 && dist[1][ans] > B) ++ans; + cout << (ans < 1e4 ? ans : -1) << '\n'; +} \ No newline at end of file diff --git a/18/day5/mootube.cpp b/18/day5/mootube.cpp new file mode 100644 index 0000000..b146b56 --- /dev/null +++ b/18/day5/mootube.cpp @@ -0,0 +1,78 @@ +#include +using namespace std; +using ll = long long; +constexpr ll p1 = 19, p2 = 29, p3 = 53; +constexpr ll MOD = 1e9+7; + +template struct vec_nd : public vector> { + static_assert(D >= 1, "Vector dimension must be greater than zero!"); + template vec_nd(int n = 0, Args... args) : vector>(n, vec_nd(args...)) { } +}; +template struct vec_nd<1, T> : public vector { vec_nd(int n = 0, const T& val = T()) : vector(n, val) { } }; + +int pw(int base, int exp) { + int res = 1; + while (exp) { + if (exp & 1) res = (ll)base * res % MOD; + exp >>= 1, base = (ll)base * base % MOD; + } + return res; +} + +int inv(int x) { return pw(x, MOD - 2); } + +int main() { + int T1, R1, C1; cin >> T1 >> R1 >> C1; + vec_nd<3, ll> A(T1, R1, C1); + for (int i = 0; i < T1; ++i) for (int j = 0; j < R1; ++j) for (int k = 0; k < C1; ++k) cin >> A[i][j][k]; + + int T2, R2, C2; cin >> T2 >> R2 >> C2; + vec_nd<3, ll> B(T2, R2, C2); + for (int i = 0; i < T2; ++i) for (int j = 0; j < R2; ++j) for (int k = 0; k < C2; ++k) cin >> B[i][j][k]; + + ll h = 0; + ll pw1 = 1; for (int i = 0; i < T1; ++i) { + ll pw2 = 1; for (int j = 0; j < R1; ++j) { + ll pw3 = 1; for (int k = 0; k < C1; ++k) { + h = (A[i][j][k] * pw1 % MOD * pw2 % MOD * pw3 + h) % MOD; + pw3 = p3 * pw3 % MOD; } + pw2 = p2 * pw2 % MOD; } + pw1 = p1 * pw1 % MOD; } + + vec_nd<3, ll> S(T2, R2, C2); + pw1 = 1; for (int i = 0; i < T2; ++i) { + ll pw2 = 1; for (int j = 0; j < R2; ++j) { + ll pw3 = 1; for (int k = 0; k < C2; ++k) { + S[i][j][k] = B[i][j][k] * pw1 % MOD * pw2 % MOD * pw3 % MOD; + if (i) S[i][j][k] += S[i - 1][j][k]; + if (j) S[i][j][k] += S[i][j - 1][k]; + if (k) S[i][j][k] += S[i][j][k - 1]; + if (i && j) S[i][j][k] -= S[i - 1][j - 1][k]; + if (i && k) S[i][j][k] -= S[i - 1][j][k - 1]; + if (j && k) S[i][j][k] -= S[i][j - 1][k - 1]; + if (i && j && k) S[i][j][k] += S[i - 1][j - 1][k - 1]; + S[i][j][k] = (S[i][j][k] + MOD * MOD) % MOD; + pw3 = p3 * pw3 % MOD; } + pw2 = p2 * pw2 % MOD; } + pw1 = p1 * pw1 % MOD; } + + ll ans = 0; + pw1 = 1; for (int i = 0; i <= T2 - T1; ++i) { + ll pw2 = 1; for (int j = 0; j <= R2 - R1; ++j) { + ll pw3 = 1; for (int k = 0; k <= C2 - C1; ++k) { + ll h2 = S[i + T1 - 1][j + R1 - 1][k + C1 - 1]; + if (i) h2 -= S[i - 1][j + R1 - 1][k + C1 - 1]; + if (j) h2 -= S[i + T1 - 1][j - 1][k + C1 - 1]; + if (k) h2 -= S[i + T1 - 1][j + R1 - 1][k - 1]; + if (i && j) h2 += S[i - 1][j - 1][k + C1 - 1]; + if (i && k) h2 += S[i - 1][j + R1 - 1][k - 1]; + if (j && k) h2 += S[i + T1 - 1][j - 1][k - 1]; + if (i && j && k) h2 -= S[i - 1][j - 1][k - 1]; + h2 = (h2 + MOD * MOD) % MOD; + h2 = h2 * inv(pw3) % MOD * inv(pw2) % MOD * inv(pw1) % MOD; + if (h2 == h) ++ans; + pw3 = p3 * pw3 % MOD; } + pw2 = p2 * pw2 % MOD; } + pw1 = p1 * pw1 % MOD; } + cout << ans << '\n'; +} \ No newline at end of file diff --git a/19/day1/out b/19/day1/out new file mode 100644 index 0000000..67f3f23 --- /dev/null +++ b/19/day1/out @@ -0,0 +1 @@ +270 diff --git a/19/day1/palindrometer.cpp b/19/day1/palindrometer.cpp new file mode 100644 index 0000000..65914fa --- /dev/null +++ b/19/day1/palindrometer.cpp @@ -0,0 +1,22 @@ +#include +using namespace std; +using ll = long long; + +int P[2][100001]; + +int main() { + string S; cin >> S; + int N = S.size(); + for (int i = 0; i < 2; ++i) { + for (int j = 0, l = 0, r = 0; j < N; ++j) { + int k = (j > r ? !i : min(P[i][l + r - j + i], r - j + 1)); + while (j - k - i >= 0 && j + k < N && S[j - k - i] == S[j + k]) ++k; + P[i][j] = k--; + if (j + k > r) l = j - k - i, r = j + k; + } + } + + ll ans = 0; + for (int i = 0; i < N; ++i) ans += P[0][i] + P[1][i]; + cout << ans << '\n'; +} \ No newline at end of file diff --git a/19/day1/retemordnilap.cpp b/19/day1/retemordnilap.cpp new file mode 100644 index 0000000..991bc78 --- /dev/null +++ b/19/day1/retemordnilap.cpp @@ -0,0 +1,42 @@ +#include +using namespace std; +using ll = long long; + +int main() { + char s[10] = "MMOOMO"; + int K; + cin >> K; + if (K == 5) { + cout << "impossible"; + return 0; + } + if (K == 1) { cout << "O"; return 0; } + if (K == 2) { cout << "MO"; return 0; } + if (K == 3) { cout << "MM"; return 0; } + if (K == 7) { cout << "MMMO"; return 0; } + if (K == 9) { cout << "MOMOM"; return 0; } + if (K % 2 == 0 && K / 2 <= 1e5) { + for (int i = 0; i <= K / 2; ++i) cout << s[i % 6]; + return 0; + } + ll sq = sqrt(8ll * K + 1) + 0.5; + if (sq * sq == 8ll * K + 1) { + int t = (sq - 1) / 2; + for (int i = 0; i < t; ++i) cout << "O"; + return 0; + } + /*if (K > 1e8 && K % 2 == 1) { + cout << "M"; + --K; + }*/ + int t = sqrt(2 * K); + while ((((K - t * (t + 1) / 2) - 2) % 2) || K - t * (t + 1) / 2 - 2 < 6) --t; + for (int i = 0; i < t; ++i) cout << "O"; + int ans = t; + //cout << t << '\n'; + K += - t * (t + 1) / 2 - 2; + for (int i = 0; i <= K / 2; ++i) cout << s[i % 6]; + ans += K / 2; + assert(ans <= 1e5); + //cout << ans << '\n'; +} \ No newline at end of file diff --git a/19/day1/test.sh b/19/day1/test.sh new file mode 100644 index 0000000..3b4f3f1 --- /dev/null +++ b/19/day1/test.sh @@ -0,0 +1,9 @@ +for i in {6..1000} +do + echo $i >> in + .vscode/3 < in | .vscode/1 > out + if !(cmp -s in out); then + echo $i + fi + rm in +done \ No newline at end of file diff --git a/19/day1/treedist.cpp b/19/day1/treedist.cpp new file mode 100644 index 0000000..a2c83ae --- /dev/null +++ b/19/day1/treedist.cpp @@ -0,0 +1,44 @@ +#include +#define f first +#define s second +#define eb emplace_back +using namespace std; +using ll = long long; +using ii = pair; +constexpr int MAXN = 100001; +constexpr ll INF = 1e9; + +int N, Q, H[MAXN]; +bitset ans; +vector G[3 * MAXN]; +unordered_map vis; + +void solve(int u, int p, int d) { + if (d && u <= N) ans[u] = 1; + if (d < 0) d = -1; + if (vis.find(INF * u + p) != vis.end()) { + if (vis[INF * u + p] != d) d = -1; + else return; + } + vis[INF * u + p] = d; + for (auto & v : G[u]) if (v.s != p) solve(v.s, u, d - v.f); +} + +int main() { + ios_base::sync_with_stdio(0), cin.tie(0); + cin >> N >> Q; + iota(H, H + N + 1, 0); + int l = N + 1; + for (int i = 1, a, b; i < N; ++i) { + cin >> a >> b; + G[H[a]].eb(0, l), G[l].eb(0, H[a]), H[a] = l++; + G[H[b]].eb(0, l), G[l].eb(0, H[b]), H[b] = l++; + G[H[a]].eb(1, H[b]), G[H[b]].eb(1, H[a]); + } + while (Q--) { + int a, b; cin >> a >> b; + solve(a, 0, b); + } + cout << N - ans.count() << '\n'; + for (int i = 1; i <= N; ++i) if (!ans[i]) cout << i << '\n'; +} \ No newline at end of file diff --git a/19/day2/mana.cpp b/19/day2/mana.cpp new file mode 100644 index 0000000..7fad64b --- /dev/null +++ b/19/day2/mana.cpp @@ -0,0 +1,31 @@ +#include +#define f first +#define s second +using namespace std; +using ii = pair; + +vector S[101]; + +int main() { + ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); + + int M, R, N; + cin >> M >> R >> N; + for (int i = 0, a, c, d; i < N; ++i) { + cin >> a >> c >> d; + S[d].emplace_back(a, c); + } + int T = M + 100 * R; + vector dp(T + 1, -1e9); + dp[0] = 0; + for (int d = 0; d <= 100; ++d) { + int g = M + d * R; + for (auto& p : S[d]) { + int a = p.f, c = p.s; + for (int i = g - c; i >= 0; --i) dp[i + c] = max(dp[i] + a, dp[i + c]); + } + } + int ans = 0; + for (auto& x : dp) ans = max(x, ans); + cout << ans << '\n'; +} \ No newline at end of file diff --git a/19/day2/themepark.cpp b/19/day2/themepark.cpp new file mode 100644 index 0000000..2582eb3 --- /dev/null +++ b/19/day2/themepark.cpp @@ -0,0 +1,42 @@ +#include +using namespace std; +constexpr int MAXN = 100001; + +int c[MAXN]; +vector G[MAXN]; + +int cnt, scc_num, scc[MAXN], in[MAXN], low[MAXN]; +stack s; +bitset ins; + +void tarjan(int u) { + low[u] = in[u] = cnt++; + s.push(u); + ins[u] = 1; + for (int v : G[u]) { + if (in[v] == -1) tarjan(v), low[u] = min(low[u], low[v]); + else if (ins[v]) low[u] = min(low[u], in[v]); + } + if (low[u] == in[u]) { + ++scc_num; + while (1) { + int x = s.top(); s.pop(); + scc[x] = scc_num, ins[x] = 0; + if (x == u) break; + } + } +} + +int main() { + int N, M, K; cin >> N >> M >> K; + while (M--) { + int a, b; cin >> a >> b; + G[a].push_back(b); + } + + memset(scc, -1, sizeof scc), memset(in, -1, sizeof in); + for (int u = 1; u <= N; ++u) if (scc[u] == -1) tarjan(u); + + if (scc_num < K) cout << "impossible\n"; + else for (int u = 1; u <= N; ++u) cout << min(scc[u], K) << '\n'; +} \ No newline at end of file diff --git a/20/day1/repl.cpp b/20/day1/repl.cpp new file mode 100644 index 0000000..6b0a301 --- /dev/null +++ b/20/day1/repl.cpp @@ -0,0 +1,43 @@ +#include +#define f first +#define s second +#define pb push_back +#define eb emplace_back +using namespace std; +using ll = long long; +using ii = pair; +using vi = vector; +using vii = vector; + +vi G[100001]; + +bool test(int x, vector & ch) { + ll tmp = 1; + for (auto& c : ch) { + if (c > x || !tmp) return 0; + tmp = min(tmp * (1 << min(x - c, 20)) - 1, 100001ll), x = c; + } + return tmp; +} + +int dfs(int u, int p) { + vi ch; + for (auto& v : G[u]) if (v != p) ch.push_back(dfs(v, u)); + if (ch.empty()) return 0; + sort(begin(ch), end(ch), greater()); + int l = ch[0] + 1, r = 100001; + while (l < r) { + int m = (l + r) / 2; + test(m, ch) ? r = m : l = m + 1; + } + return l; +} + +int main() { + int N; cin >> N; + for (int i = 1; i < N; ++i) { + int a, b; cin >> a >> b; + G[a].push_back(b), G[b].push_back(a); + } + cout << dfs(1, 0) + N - 1 << '\n'; +} \ No newline at end of file diff --git a/20/day1/tri.cpp b/20/day1/tri.cpp new file mode 100644 index 0000000..a28df48 --- /dev/null +++ b/20/day1/tri.cpp @@ -0,0 +1,42 @@ +#include +#define f first +#define s second +#define pb push_back +#define eb emplace_back +using namespace std; +using ll = long long; +using ii = pair; +using vi = vector; +using vii = vector; + +ii E[100001]; +vi G[100001]; +bitset<100001> vis, oc; + +int main() { + int N, M; + cin >> N >> M; + for (int i = 0; i < M; ++i) { + cin >> E[i].f >> E[i].s; + G[E[i].f].pb(E[i].s), G[E[i].s].pb(E[i].f); + } + + vi v; + for (int i = 1; i <= N; ++i) v.push_back(i); + sort(begin(v), end(v), [](int a, int b) { return G[a].size() < G[b].size(); }); + + ll ans = 0; + for (auto& u : v) { + vis[u] = 1; + for (auto& v : G[u]) oc[v] = 1; + vi tmp; + for (auto& v : G[u]) { + if (vis[v]) tmp.pb(v); + } + for (auto& v : tmp) { + for (auto& w : G[v]) ans += oc[w]; + } + for (auto& v : G[u]) oc[v] = 0; + } + cout << ans / 3 << '\n'; +} \ No newline at end of file diff --git a/20/day2/meet.cpp b/20/day2/meet.cpp new file mode 100644 index 0000000..4f37159 --- /dev/null +++ b/20/day2/meet.cpp @@ -0,0 +1,32 @@ +#include +#define f first +#define s second +using namespace std; +typedef long long ll; +typedef pair ii; + +int a[303]; +vector G[303]; + +void dfs(int u, int p) { + for (auto& v : G[u]) { + dfs(v, u); + + } + + +} + +int main() { + int N; + cin >> N; + for (int i = 0; i < N; ++i) cin >> a[i]; + for (int i = 1; i < N; ++i) { + int u, v; + cin >> u >> v; + G[u].push_back(v), G[v].push_back(u); + } + + dfs(1, 0); + +} \ No newline at end of file diff --git a/20/day2/meet_slow.cpp b/20/day2/meet_slow.cpp new file mode 100644 index 0000000..99d8b21 --- /dev/null +++ b/20/day2/meet_slow.cpp @@ -0,0 +1,97 @@ +#include +#define f first +#define s second +using namespace std; +typedef long long ll; +typedef pair ii; + +int a[303], cost[303][303], dp[303][303]; +vector G[303]; + +int main() { + int N; + cin >> N; + for (int i = 0; i < N; ++i) cin >> a[i]; + for (int i = 1; i < N; ++i) { + int u, v; + cin >> u >> v; + --u, --v; + G[u].push_back(v), G[v].push_back(u); + } + if (N <= 20) { + int ans[22]; + fill(ans, ans + N + 1, 1e9); + for (int m = 1; m < (1 << N); ++m) { + int dist[22]; + queue q; + for (int i = 0; i < N; ++i) { + if (1 & (m >> i)) { + dist[i] = 0; + q.emplace(i, 0); + } + else dist[i] = 1e9; + } + while (!q.empty()) { + int u = q.front().f, d = q.front().s; + q.pop(); + if (d > dist[u]) continue; + for (auto& v : G[u]) { + if (d + 1 < dist[v]) { + dist[v] = d + 1; + q.emplace(v, dist[v]); + } + } + } + int sum = 0; + for (int i = 0; i < N; ++i) sum += a[i] * dist[i]; + ans[__builtin_popcount(m)] = min(sum, ans[__builtin_popcount(m)]); + } + for (int i = 1; i <= N; ++i) cout << ans[i] << ' '; + } + else { + int s; + for (int i = 0; i < N; ++i) { + if (G[i].size() == 1) s = i; + } + vector v(N); + int p = -1; + for (int i = 0; i < N; ++i) { + v[i] = a[s]; + if (i < N - 1) { + int tmp = s; + s = (G[s][0] == p ? G[s][1] : G[s][0]); + p = tmp; + } + } + memset(cost, '?', sizeof cost); + for (int i = 0; i < N; ++i) { + for (int j = i; j < N; ++j) { + int cnt = 0, sum = 0; + for (int k = i; k <= j; ++k) { + cnt += v[k]; + sum += (k - i) * v[k]; + } + cnt -= v[i]; + cost[i][j] = min(sum, cost[i][j]); + int tmp = 0; + for (int k = i + 1; k <= j; ++k) { + tmp += v[k - 1]; + sum -= cnt; + sum += tmp; + cnt -= v[k]; + cost[i][j] = min(sum, cost[i][j]); + } + } + } + memset(dp, '?', sizeof dp); + dp[0][0] = 0; + for (int i = 0; i < N; ++i) { + for (int j = 0; j <= i; ++j) { + for (int k = 0; k <= i; ++k) { + dp[i + 1][j + 1] = min(dp[k][j] + cost[k][i], dp[i + 1][j + 1]); + } + } + } + for (int i = 1; i <= N; ++i) cout << dp[N][i] << ' '; + } +} \ No newline at end of file diff --git a/20/day2/reopen.cpp b/20/day2/reopen.cpp new file mode 100644 index 0000000..0d64e84 --- /dev/null +++ b/20/day2/reopen.cpp @@ -0,0 +1,29 @@ +#include +#define f first +#define s second +using namespace std; +typedef long long ll; +typedef pair ii; + +int main() { + ios_base::sync_with_stdio(0), cin.tie(0); + + int n, a, b; + string r; + cin >> n >> a >> b >> r; + + if (r == "1/2") { + for (int i = 0; i < n / 2; ++i) cout << b * i << ' ' << 0 << '\n'; + for (int i = n / 2; i < n; ++i) cout << b * i + a << ' ' << 0 << '\n'; + } + else { + int d = a * (b + 1) / 2 % b; + for (int i = 0; i < n; ++i) { + int x = d + (i / 4) * b, y = 0; + if (i % 2 == 1) swap(x, y); + if (i % 4 == 2) x = -x; + if (i % 4 == 3) y = -y; + cout << x + 500000000 << ' ' << y + 500000000 << '\n'; + } + } +} \ No newline at end of file diff --git a/20/day2/triangles.cpp b/20/day2/triangles.cpp new file mode 100644 index 0000000..c30cbc7 --- /dev/null +++ b/20/day2/triangles.cpp @@ -0,0 +1,45 @@ +#include +#define f first +#define s second +using namespace std; +typedef long long ll; +typedef pair ii; +constexpr ll MOD = 1e9+7; + +ii P[2002]; + +int main() { + ifstream cin("triangles.in"); + ofstream cout("triangles.out"); + + int N; + cin >> N; + for (int i = 0; i < N; ++i) cin >> P[i].f >> P[i].s; + sort(P, P + N); + + ll ans = 0; + for (int i = 0; i < N; ++i) { + ii p = P[i]; + vector l, r; + for (int j = 0; j < i; ++j) l.push_back(P[j]); + for (int j = i + 1; j < N; ++j) r.push_back(P[j]); + sort(l.begin(), l.end(), [&p](const ii& a, const ii& b) { + int x = (a.f - p.f) * (b.s - p.s) - (a.s - p.s) * (b.f - p.f); + if (x == 0) return (a.f - p.f) * (a.f - p.f) + (a.s - p.s) * (a.s - p.s) < (b.f - p.f) * (b.f - p.f) + (b.s - p.s) * (b.s - p.s); + return x < 0; + }); + sort(r.begin(), r.end(), [&p](const ii& a, const ii& b) { + int x = (a.f - p.f) * (b.s - p.s) - (a.s - p.s) * (b.f - p.f); + if (x == 0) return (a.f - p.f) * (a.f - p.f) + (a.s - p.s) * (a.s - p.s) < (b.f - p.f) * (b.f - p.f) + (b.s - p.s) * (b.s - p.s); + return x < 0; + }); + + for (int j = 0, k = 0; j < i; ++j) { + while (k < N - i - 1 && (l[j].f - p.f) * (r[k].s - p.s) - (l[j].s - p.s) * (r[k].f - p.f) <= 0) ++k; + ans += (ll)(2 * j + N - 2 * i - 2 * k) * (p.s + l[j].s) * (p.f - l[j].f) + MOD * MOD; + ans %= MOD; + } + } + + cout << ans << '\n'; +} \ No newline at end of file diff --git a/20/day2/triangles_gen.cpp b/20/day2/triangles_gen.cpp new file mode 100644 index 0000000..fec17ae --- /dev/null +++ b/20/day2/triangles_gen.cpp @@ -0,0 +1,24 @@ +#include +#define f first +#define s second +using namespace std; +typedef pair ii; + +int M = 10000; + +int main() { + ofstream cout("triangles.in"); + + int N = 100; + cout << N << '\n'; + srand(time(0)); + vector v; + for (int i = 0; i < N; ++i) { + ii x; + do { + x.f = (rand() % (2 * M)) - M, x.s = (rand() % (2 * M)) - M; + } while (find(v.begin(), v.end(), x) != v.end()); + v.push_back(x); + cout << x.f << ' ' << x.s << '\n'; + } +} \ No newline at end of file diff --git a/20/day3/treemst.cpp b/20/day3/treemst.cpp new file mode 100644 index 0000000..ad4bae2 --- /dev/null +++ b/20/day3/treemst.cpp @@ -0,0 +1,44 @@ +#include +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair; + +int h[100001], p[100001], d[100001], l[100001], r[100001]; +ll ans; +set S; +vector G[100001]; + +void dfs(int u, int p) { + d[u] = d[p] + 1; + l[u] = r[u] = 2e9; + S.emplace(h[u], u); + for (auto& v : G[u]) { + if (v != p) dfs(v, u); + } + S.erase(ii(h[u], u)); + if (u == 1) return; + + auto it = S.lower_bound(ii(h[u], u)); + if (it != begin(S)) l[u] = min(h[u] - prev(it)->f, l[u]); + if (it != end(S)) r[u] = min(it->f - h[u], r[u]); + ans += min(l[u], r[u]); + int m = max(l[u], r[u]); + if (m < 2e9) { + int y = prev(it)->s, z = it->s; + d[y] > d[z] ? r[y] = min(m, r[y]) : l[z] = min(m, l[z]); + } +} + +int main() { + int N; + cin >> N; + for (int i = 1; i <= N; ++i) cin >> h[i]; + for (int i = 2; i <= N; ++i) { + cin >> p[i]; + G[p[i]].push_back(i); + } + dfs(1, 0); + cout << ans << '\n'; +} \ No newline at end of file diff --git a/20/day4/extra.cpp b/20/day4/extra.cpp new file mode 100644 index 0000000..360fa67 --- /dev/null +++ b/20/day4/extra.cpp @@ -0,0 +1,30 @@ +#include +using namespace std; +constexpr int MOD = 1e9+7; + +int lcp[5005][5005], dp[5005][5005]; + +int main() { + string s; + cin >> s; + int n = s.size(); + for (int i = n - 1; i >= 0; --i) { + for (int j = n - 1; j >= i; --j) { + if (s[i] == s[j]) lcp[i][j] = 1 + lcp[i + 1][j + 1]; + } + } + + dp[0][0] = 1; + for (int i = 0; i < n; ++i) { + for (int j = i + 1; j <= n; ++j) { + dp[i][j] += dp[i][j - 1], dp[i][j] %= MOD; + int len = min(lcp[i][j], j - i); + if (i + len >= n || (len < j - i && s[i + len] > s[j + len])) continue; + dp[j][j + len + 1] += dp[i][j], dp[j][j + len + 1] %= MOD; + } + } + + int ans = 0; + for (int i = 0; i < n; ++i) ans += dp[i][n], ans %= MOD; + cout << ans << '\n'; +} \ No newline at end of file diff --git a/20/day6/cowputing b/20/day6/cowputing new file mode 100644 index 0000000..f15e67a --- /dev/null +++ b/20/day6/cowputing @@ -0,0 +1,29 @@ +# g++ grader.cc && cp solution output && ./a.out + +# Blank lines and comment lines (start with '#') are allowed + +# TASK 1 +# Your machine is given as lines of rules. Each rule has the form: +# STATE SYMBOL -> NEW_STATE WRITE_SYMBOL ACTION +# STATE can be any string. The Cowputer always starts in state "0". +# SYMBOL can be any alphanumeric character (A-Z,a-z,0-9). +# ACTION is one of L(eft) R(ight) S(tay) H(alt) +# If your program encounters a state it has no rule for, that's WA. +# With these rules, the Cowputer will go left until it finds an 'X' and then halt. +# It won't change the array at all, because on every step it just writes whatever symbol +# was already there. +0 1 -> 0 1 L +# ^"If you are in state 0 and see symbol '1', go to state 0, write a '1' and move left" +# This means that the state stays the same, it writes a one on the current index +# in the array, and moves to index-1 in the array +0 0 -> 0 0 L +# ^"If you are in state 0 and see symbol '0', go to state 0, write a '0' and move left" +0 X -> 0 X H +# ^"If you are in state 0 and see symbol 'X', go to state 0, write an 'X', and halt" + +# TASK 2 +# You should submit all your programs in one file. Programs are separated by '# TASK ' lines. +# You would put your rules for TASK 2 here. +# This submission for TASK 2 just halts immediately. Unfortunately, that does not solve task 2. +0 0 -> 0 0 H +0 1 -> 0 1 H \ No newline at end of file diff --git a/20/day6/friend.cpp b/20/day6/friend.cpp new file mode 100644 index 0000000..6a9fdec --- /dev/null +++ b/20/day6/friend.cpp @@ -0,0 +1,29 @@ +#include +#define f first +#define s second +using namespace std; +typedef long long ll; +typedef pair ii; +constexpr ll MOD = 1e9+7; + +int a[100001], b[100001]; +map f, g; + +int main() { + int N; + cin >> N; + f[ii(1, 2)] = 1; + for (int i = 3; i <= N; ++i) { + cin >> a[i] >> b[i]; + f[ii(a[i], i)] = f[ii(b[i], i)] = 1; + } + g = f; + int ans = 0; + for (int i = N; i >= 3; --i) { + ii x(a[i], i), y(b[i], i), z(a[i], b[i]); + ans = (g[x] * f[y] % MOD * f[z] + f[x] * g[y] % MOD * f[z] + f[x] * f[y] % MOD * g[z] + ans) % MOD; + g[z] = (f[x] * g[y] + g[x] * f[y] + g[z]) % MOD; + f[z] = (f[x] * f[y] + f[z]) % MOD; + } + cout << 2 * ans % MOD << '\n'; +} \ No newline at end of file diff --git a/20/day6/grader.cc b/20/day6/grader.cc new file mode 100644 index 0000000..b1c32c0 --- /dev/null +++ b/20/day6/grader.cc @@ -0,0 +1,467 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +int TRACE = -1; + +using ll = long long; +using namespace std; + +ostream& operator<<(ostream& o, const deque& ARRAY) { + for(int i=0; i(lo,hi)(RNG); +} + +void fassert(bool b, const string& msg) { + if(!b) { + cerr << msg << endl; + cout << "W" << endl; + assert(false); + } +} + +// STATE CHARACTER -> NEW_STATE NEW_CHARACTER {L(EFT),R(IGHT),S(TAY),H(ALT)} +using Cowputer = map>>; +constexpr ll LIMIT = static_cast(1e6); + +set symbols(const Cowputer& M) { + set ans; + for(auto& kv : M) { + for(auto& kv2 : kv.second) { + string new_state; char new_char; char action; + std::tie(new_state, new_char, action) = kv2.second; + ans.insert(kv2.first); + ans.insert(new_char); + } + } + return ans; +} + +struct State { + State(Cowputer m, deque& START, bool trace_) : RULES(m), ARRAY(START), pos(0), state("0"), time(0), tle(false), trace(trace_) { + if(ARRAY.size() == 0) { + ARRAY.push_back('X'); + } + } + deque& ARRAY; + int pos; + string state; + int time; + Cowputer RULES; + bool tle; + + bool trace; + + bool run() { + if(trace) { + cerr << "TRACE: STARTING ARRAY=" << ARRAY << endl; + } + while(!step(trace)) {} + if(trace) { + cerr << "TRACE: ENDING ARRAY=" << ARRAY << endl; + } + return tle; + } + + bool step(bool trace) { + if(time == LIMIT) { + tle = true; + return true; + } + if(trace) { cerr << "TRACE: " << show() << endl; } + fassert(0<=pos && pos ll_to_array(ll n) { + deque ARRAY; + ll tmp = n; + while(tmp > 0) { + ARRAY.push_front(static_cast('0'+(tmp%2))); + tmp /= 2; + } + return ARRAY; +} + +// Trim X off left and right +string read_array(const deque& ARRAY) { + stringstream ans; + ll start = 0; + while(start=0 && ARRAY[end]=='X') { end--; } + for(ll i=start; i<=end; i++) { + ans << ARRAY[i]; + } + return ans.str(); +} + +// Reads the first integer in binary on the array +ll from_binary(const string& S) { + ll ans = 0; + for(ll i=0; i GOAL; + for(ll i=0; i GOAL; + for(ll i=0; i syms = symbols(RULES); + if(syms.size() > 3) { + cerr << "Only 3 characters allowed for task 7" << endl; + } + + deque ARRAY; + State START(RULES,ARRAY,trace); + bool tle = START.run(); + if(tle) { + cerr << "TLE TASK 7" << endl; + return 0; + } + ll score = START.time; + if(trace) { + cerr << "TASK 7: TOOK " << score << " steps" << endl; + } + if(score >= 10000) { + return 5; + } else if(score >= 1000) { + return 4; + } else if(score >= 500) { + return 3; + } else if(score >= 100) { + return 2; + } else if(score >= 20) { + return 1; + } else { + return 0; + } +} + +int main() { + ifstream in; + in.open("output"); + if (!in) { + cerr << "No \"output\" file" << endl; + cout << "W" << endl; + exit(0); + } + using Checker = std::function; + vector TASKS{ + {task1}, + {task2}, + {task3}, + {task4}, + {task5}, + {task6}, + {task7}, + }; + + map MS; + Cowputer RULES; + ll task = -1; + while(!in.eof()) { + string line; + getline(in, line); + string PREFIX = "# TASK"; + if(line.find(PREFIX)==0) { + stringstream ss(line); + if(task != -1) { + fassert(MS.count(task)==0, "Already submitted a machine for task=" + std::to_string(task)); + MS[task] = RULES; + RULES.clear(); + } + string hash; string label; ll new_task; + ss >> hash >> label >> new_task; + fassert(hash == "#", "TASK LINE must start with '# TASK' line="+line); + fassert(label == "TASK", "TASK LINE must start with '# TASK' line="+line); + fassert(1<=new_task && new_task<=TASKS.size(), "Unknown TASK="+std::to_string(new_task)); + task = new_task-1; + } + bool isempty = true; + for(ll i=0; i", "BAD ARROW line="+line+" arrow=" + arrow); + assert(arrow == "->"); + if(RULES.count(state)==0) { + RULES[state] = map>{}; + } + fassert(set{'L', 'R', 'S', 'H'}.count(action)==1, "Action must be one of L(EFT) R(IGHT) S(TAY) H(ALT) got="+std::to_string(action)); + fassert(RULES[state].count(seen)==0, "Duplicate rule detected state="+state+" char="+std::string(1, seen)); + RULES[state][seen] = make_tuple(new_state, write, action); + } + if(task != -1) { + fassert(MS.count(task)==0, "Already submitted a machine for task=" + std::to_string(task)); + MS[task] = RULES; + } + + ll score = 0; + for(auto& kv : MS) { + ll task; Cowputer M; + std::tie(task, M) = kv; + if(M.size() > 1000) { + cerr << "You used more than 1000 internal states for task=" << task << endl; + continue; + } + Checker check = TASKS[task]; + ll points = check(M, TRACE==task+1); + score += points; + cerr << "Task " << (task+1) << ": " << points << endl; + } + cout << score << endl; +} diff --git a/20/day6/milkvisits.cpp b/20/day6/milkvisits.cpp new file mode 100644 index 0000000..d18c457 --- /dev/null +++ b/20/day6/milkvisits.cpp @@ -0,0 +1,61 @@ +#include +#define f first +#define s second +using namespace std; +typedef pair ii; + +vector G[100001]; + +vector path16[17][17]; +ii ans16[17]; +void dfs16(int r, int u, int p) { + path16[r][u] = path16[r][p], path16[r][u].push_back(u); + for (auto& v : G[u]) if (v != p) dfs16(r, v, u); +} + +int main() { + int N, M; + cin >> N >> M; + for (int i = 1; i < N; ++i) { + int a, b; + cin >> a >> b; + G[a].push_back(b), G[b].push_back(a); + } + + if (N <= 16) { + pair Q[17]; + fill(ans16 + 1, ans16 + N + 1, ii(-1, 0)); + for (int i = 0; i < M; ++i) cin >> Q[i].f.f >> Q[i].f.s >> Q[i].s; + for (int u = 1; u <= N; ++u) dfs16(u, u, 0); + for (int y = 0; y < (1 << N); ++y) { + int m = 2 * y; + bool pass = 1; + for (int i = 0; i < M && pass; ++i) { + bool flag = 0; + for (auto& x : path16[Q[i].f.f][Q[i].f.s]) { + if ((1 & (m >> x)) == (Q[i].s == 'G')) flag = 1; + } + if (!flag) pass = 0; + } + if (pass) { + for (int i = 1; i <= N; ++i) { + if (ans16[i].f == -1) ans16[i].f = (1 & (m >> i)); + else if ((1 & (m >> i)) != ans16[i].f) ans16[i].s = 1; + ans16[i].f = (1 & (m >> i)); + } + } + } + if (ans16[1].f == -1) { + cout << "NO\n"; + } + else { + cout << "YES\n"; + for (int i = 1; i <= N; ++i) cout << (ans16[i].f ? 'G' : 'H') << (ans16[i].s ? '?' : '!') << '\n'; + } + } + else { + + + + } +} \ No newline at end of file diff --git a/20/practice/babynames.cpp b/20/practice/babynames.cpp new file mode 100644 index 0000000..42a5629 --- /dev/null +++ b/20/practice/babynames.cpp @@ -0,0 +1,93 @@ +#include +using namespace std; +typedef long long ll; +constexpr int M1 = 8191, M2 = 1e9+7; + +string s[10001]; +vector h[10001]; +int r[10001], hs[2][10001]; + +inline void print(int x, int d) { + cout << "MOO "; + for (int i = 0; i < d; ++i) cout << (1 & (x >> i)); + cout << endl; +} + +inline int read(int d) { + int x = 0; + for (int i = 0; i < 16; ++i) { + char c; + cin >> c; + if (c == '1') x |= (1 << i); + } + return x; +} + +inline int hsh(string& s, int m) { + ll x = 0; + for (auto& c : s) x *= 31, x += c - 'a', x %= m; + return x; +} + +int main() { + ofstream debug("debug"); + + int c, n[2]; + cin >> c >> n[0]; + for (int i = 0; i < n[0]; ++i) { + cin >> s[i]; + hs[0][i] = hsh(s[i], M1); + hs[1][i] = hsh(s[i], M2); + } + if (c) { + print(n[0], 16); + debug << 1 << ' ' << n[1]; + n[1] = read(16); + + for (int i = 0; i < n[0]; ++i) { + print(hs[0][i], 13); + bool b; + cin >> b; + if (b == 1) { + print(hs[1][i], 30); + cin >> b; + if (b == 1) { + cout << "RETURN " << s[i] << endl; + return 0; + } + } + } + } + else { + n[1] = read(16); + debug << 0 << ' ' << n[1]; + print(n[0], 16); + + for (int i = 0; i < n[0]; ++i) { + h[hs[0][i]].push_back(i); + } + for (int i = 0; i < n[1]; ++i) { + r[i] = read(13); + if (h[r[i]].empty()) { + print(0, 1); + } + else { + print(1, 1); + int x; + x = read(30); + bool ans = 0; + for (auto& y : h[r[i]]) { + if (hs[1][y] == x) { + ans = 1; + cout << "RETURN " << s[y] << endl; + print(1, 1); + return 0; + } + } + if (!ans) { + print(0, 1); + } + } + } + } +} \ No newline at end of file diff --git a/20/practice/cowforce.cpp b/20/practice/cowforce.cpp new file mode 100644 index 0000000..71ef087 --- /dev/null +++ b/20/practice/cowforce.cpp @@ -0,0 +1,42 @@ +#include +using namespace std; +typedef long long ll; + +ll t[303][303], dp[303][303][303]; + +int main() { + int N, M, K; + cin >> N >> M >> K; + for (int i = 0; i < N; ++i) { + for (int j = 0; j < M; ++j) cin >> t[i][j]; + } + + memset(dp, '?', sizeof dp); + memset(dp[0], 0, sizeof dp[0]); + for (int i = 0; i < N; ++i) { + for (int j = 0; j < M; ++j) { + for (int k = 0; k < M; ++k) { + if (j != k) dp[i + 1][j][k] = min(dp[i][j][k] + t[i][j] + t[i][k], dp[i + 1][j][k]); + } + } + for (int j = 0; j < M; ++j) { + for (int k = 0; k < M; ++k) { + if (j > 0 && j - 1 != k) dp[i + 1][j][k] = min(dp[i + 1][j - 1][k] + K, dp[i + 1][j][k]); + if (k > 0 && j != k - 1) dp[i + 1][j][k] = min(dp[i + 1][j][k - 1] + K, dp[i + 1][j][k]); + } + } + for (int j = M - 1; j >= 0; --j) { + for (int k = M - 1; k >= 0; --k) { + if (j < M - 1 && j + 1 != k) dp[i + 1][j][k] = min(dp[i + 1][j + 1][k] + K, dp[i + 1][j][k]); + if (k < M - 1 && j != k + 1) dp[i + 1][j][k] = min(dp[i + 1][j][k + 1] + K, dp[i + 1][j][k]); + } + } + } + ll ans = 1e18; + for (int i = 0; i < M; ++i) { + for (int j = 0; j < M; ++j) { + if (i != j) ans = min(dp[N][i][j], ans); + } + } + cout << ans << '\n'; +} \ No newline at end of file diff --git a/20/practice/data b/20/practice/data new file mode 100644 index 0000000..85ab75d --- /dev/null +++ b/20/practice/data @@ -0,0 +1,10 @@ +0 3 +candice +mark +john +1 5 +paul +qq +tjhance +candice +bob \ No newline at end of file diff --git a/20/practice/debug b/20/practice/debug new file mode 100644 index 0000000..e69de29 diff --git a/20/practice/guess.cpp b/20/practice/guess.cpp new file mode 100644 index 0000000..a9ff0e0 --- /dev/null +++ b/20/practice/guess.cpp @@ -0,0 +1,6 @@ +#include +using namespace std; + +int main() { + cout << 42 << '\n'; +} \ No newline at end of file diff --git a/20/practice/test_grader.cpp b/20/practice/test_grader.cpp new file mode 100644 index 0000000..b7d9162 --- /dev/null +++ b/20/practice/test_grader.cpp @@ -0,0 +1,264 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#include + +using namespace std; + +#define L 1000000000000000LL + +#define RETRY(x) ({ \ + int _r = (x); \ + while (_r == -1 && errno == EINTR) { \ + _r = (x); \ + } \ + _r; \ +}) + +template +string to_string(const T& x) { + ostringstream sout; + sout << x; + return sout.str(); +} + +pid_t start_instance(int argc, char** argv, int* pipes) { + int pipe_a[2]; + int pipe_b[2]; + if (pipe(pipe_a) == -1 || pipe(pipe_b) == -1) { + perror("pipe"); + return -1; + } + + pid_t pid = fork(); + if (pid == -1) { + perror("fork"); + return -1; + } else if (pid == 0) { + close(0); + close(1); + dup2(pipe_b[0], 0); + dup2(pipe_a[1], 1); + close(pipe_a[0]); + close(pipe_a[1]); + close(pipe_b[0]); + close(pipe_b[1]); + + char** args = (char**)malloc(sizeof(char*) * (argc + 2)); + args[0] = strdup("stdbuf"); + args[1] = strdup("-oL"); + for (int i = 1; i < argc; i++) { + args[1 + i] = argv[i]; + } + args[argc + 1] = NULL; + execvp("stdbuf", args); + perror("execvp"); + exit(1); + } + + close(pipe_a[1]); + close(pipe_b[0]); + pipes[0] = pipe_a[0]; + pipes[1] = pipe_b[1]; + return pid; +} + +int main(int argc, char** argv) { + if (argc == 1) { + cout << "USAGE:" << endl; + cout << argv[0] << " ./test_program" << endl; + return 0; + } + if (signal(SIGPIPE, SIG_IGN)) { + perror("signal"); + return 1; + } + + int nfds = 1; + char buf[1024]; + int rfd[2]; + int wfd[2]; + pid_t pids[2]; + bool alive[2] = {true, true}; + bool returned[2] = {false, false}; + string return_val[2] = {"", ""}; + for (int i = 0; i < 2; i++) { + int pipe_tmp[2]; + pids[i] = start_instance(argc, argv, pipe_tmp); + if (pids[i] == -1) { + cerr << "failed to start solution program" << endl; + return 1; + } + + rfd[i] = pipe_tmp[0]; + wfd[i] = pipe_tmp[1]; + nfds = max(nfds, max(rfd[i], wfd[i])) + 1; + } + + int ign; + vector names[2]; + string in[2]; + string out[2]; + + set names_set[2]; + for (int i = 0; i < 2; i++) { + int sz; + cin >> ign >> sz; + names[i].resize(sz); + + out[i] = to_string(i) + " " + to_string(sz) + "\n"; + for (int j = 0; j < sz; j++) { + cin >> names[i][j]; + assert(0 <= names[i][j].size() && names[i][j].size() <= 100); + for(int k = 0; k < names[i][j].size(); k++){ + assert('a' <= names[i][j][k] && names[i][j][k] <= 'z'); + } + + if (j) out[i] += ' '; + out[i] += names[i][j]; + } + out[i] += '\n'; + + names_set[i] = set(names[i].begin(), names[i].end()); + assert(names_set[i].size() == names[i].size()); + } + vector intersection; + for(auto it = names_set[0].begin(); it != names_set[0].end(); ++it){ + if(names_set[1].count(*it)){ + cerr << "COMMON NAME: " << *it << endl; + intersection.push_back(*it); + } + } + assert(intersection.size() == 1); + string answer_val = intersection[0]; + + int total_bits = 0; + for (; alive[0] || alive[1]; ) { + fd_set rfds; + fd_set wfds; + FD_ZERO(&rfds); + FD_ZERO(&wfds); + for (int i = 0; i < 2; i++) { + if (!alive[i]) { + continue; + } + FD_SET(rfd[i], &rfds); + if (out[i].size()) { + FD_SET(wfd[i], &wfds); + } + } + + if (RETRY(select(nfds, &rfds, &wfds, NULL, NULL)) == -1) { + perror("select"); + cout << "E" << endl; + return 0; + } + + for (int i = 0; i < 2; i++) { + if (FD_ISSET(rfd[i], &rfds)) { + ssize_t amt = RETRY(read(rfd[i], buf, sizeof(buf))); + if (amt <= 0) { + close(rfd[i]); + close(wfd[i]); + alive[i] = false; + cerr << "Cow " << i << " communication closed" << endl; + continue; + } + in[i] += string(buf, amt); + cerr << "COW[" << i << "]: " << string(buf, amt) << endl; + + for(;;) { + int nline = in[i].find('\n'); + if (nline == -1) { + break; + } + string line = in[i].substr(0, nline); + in[i] = in[i].substr(nline + 1); + + istringstream sin(line); + string cmd; sin >> cmd; + if (cmd == "MOO") { + string data; sin >> data; + for (int j = 0; j < data.size(); j++) { + if (data[j] != '0' && data[j] != '1') { + cerr << "Cow " << i << " tried to moo non-binary" << endl; + return 1; + } + } + out[1 - i] += data + "\n"; + total_bits += data.size(); + } else if (cmd == "RETURN") { + string val; + sin >> val; + if (returned[i]) { + cerr << "Same cow cannot return twice" << endl; + return 1; + } else { + returned[i] = true; + return_val[i] = val; + } + } else { + cerr << "Unknown command from cow " << i << endl; + return 1; + } + } + if (in[i].size() > 7000000) { + cerr << "Line too long from cow " << i << endl; + return 1; + } + } + if (FD_ISSET(wfd[i], &wfds)) { + // cerr << "TO COW[" << i << "]: " << out[i] << endl; + ssize_t amt = RETRY(write(wfd[i], out[i].data(), out[i].size())); + if (amt <= 0) { + close(rfd[i]); + close(wfd[i]); + alive[i] = false; + cerr << "Cow " << i << " communication closed" << endl; + continue; + } else { + out[i] = out[i].substr(amt); + } + } + } + } + for (int i = 0; i < 2; i++) { + int status = 0; + if (RETRY(waitpid(pids[i], &status, 0)) == -1) { + perror("waitpid"); + return 1; + } + if (WIFSIGNALED(status)) { + cerr << "Cow " << i << " crashed" << endl; + return 1; + } + } + + for (int i = 0; i < 2; i++) { + if (returned[i] && return_val[i] != answer_val) { + cerr << "Cow " << i << " returned the wrong value" << endl; + return 1; + } + } + if (!returned[0] && !returned[1]) { + cerr << "Neither cow returned a value" << endl; + return 1; + } + + cerr << "Found correct name " << answer_val << " using " << + total_bits << " total bits." << endl; + + return 0; +} diff --git a/2015/day1/comehome.cpp b/2015/day1/comehome.cpp deleted file mode 100644 index e9c72db..0000000 --- a/2015/day1/comehome.cpp +++ /dev/null @@ -1,44 +0,0 @@ -#include -#define f first -#define s second -#define int long long -using namespace std; -using ll = long long; -using ii = pair; - -ii dist[100001], src[100001]; -vector G[100001]; - -signed main() { - ios_base::sync_with_stdio(0), cin.tie(0); - - int N, M, K; cin >> N >> M >> K; - while (M--) { - int A, B, D; cin >> A >> B >> D; - G[A].emplace_back(D, B), G[B].emplace_back(D, A); - } - - priority_queue, greater> pq; - memset(dist, '?', sizeof dist); - for (int i = 1; i <= K; ++i) dist[i] = ii(0, 0), pq.emplace(0, i); - while (pq.size()) { - int d = pq.top().f, u = pq.top().s; - pq.pop(); - if (d > dist[u].s) continue; - for (auto & p : G[u]) { - int d = p.f, v = p.s; - if ((dist[u].s + d == dist[v].f && src[v].f == u) || (dist[u].s + d == dist[d].s && src[v].s == u)) continue; - if (dist[u].s + d <= dist[v].f) { - dist[v].s = dist[v].f, src[v].s = src[v].f; - dist[v].f = dist[u].s + d, src[v].f = u; - pq.emplace(dist[v].s, v); - } - else if (dist[u].s + d <= dist[v].s) { - dist[v].s = dist[u].s + d, src[v].s = u; - pq.emplace(dist[v].s, v); - } - } - } - - cout << (dist[N].s <= 1e18 ? dist[N].s : -1) << '\n'; -} \ No newline at end of file diff --git a/2015/day3/camelot.cpp b/2015/day3/camelot.cpp deleted file mode 100644 index ea96663..0000000 --- a/2015/day3/camelot.cpp +++ /dev/null @@ -1,71 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ll = long long; -using ii = pair; - -const int dx[] = { 2, 1, -1, -2, -2, -1, 1, 2 }; -const int dy[] = { 1, 2, 2, 1, -1, -2, -2, -1 }; - -int d[44][44]; -bool b[44][44]; -inline int & dist(int i, int j) { return d[i + 22][j + 22]; } -inline bool & vis(int i, int j) { return b[i + 22][j + 22]; } - -ii P[202]; -int dp[202][101]; - -int main() { - ios_base::sync_with_stdio(0), cin.tie(0); - - int N, R, C; - cin >> N >> R >> C; - for (int i = 0; i < N; ++i) { - cin >> P[i].f >> P[i].s; - --P[i].f, --P[i].s; - } - - // BFS to compute distances - auto valid = [&R, &C](int i, int j) { return i > -R && i < R && j > -C && j < C; }; - dist(0, 0) = 0; - queue q; - q.emplace(0, 0); - while (q.size()) { - ii u = q.front(); - q.pop(); - if (vis(u.f, u.s)) continue; - vis(u.f, u.s) = 1; - for (int d = 0; d < 8; ++d) { - ii v(u.f + dx[d], u.s + dy[d]); - if (valid(v.f, v.s) && !vis(v.f, v.s)) { - dist(v.f, v.s) = dist(u.f, u.s) + 1; - q.push(v); - } - } - } - - // O(R^2 * C^2 * N^2) - int ans = 1e9; - for (int a = 0; a < R; ++a) { - for (int b = 0; b < C; ++b) { - for (int c = a; c < R; ++c) { - for (int d = 0; d < C; ++d) { - if (a == c && b == d) continue; - // First meetup location: (a, b) - // Second meetup location: (c, d) - memset(dp, '?', sizeof dp); - dp[0][0] = 0; - for (int i = 0; i < N; ++i) { - for (int j = 0; j <= min(i, N / 2); ++j) { - dp[i + 1][j] = min(dist(P[i].f - a, P[i].s - b) + dp[i][j], dp[i + 1][j]); - dp[i + 1][j + 1] = min(dist(P[i].f - c, P[i].s - d) + dp[i][j], dp[i + 1][j + 1]); - } - } - ans = min(dp[N][N / 2], ans); - } - } - } - } - cout << ans << '\n'; -} \ No newline at end of file diff --git a/2016/day1/tractor.cpp b/2016/day1/tractor.cpp deleted file mode 100644 index 6318ff7..0000000 --- a/2016/day1/tractor.cpp +++ /dev/null @@ -1,30 +0,0 @@ -#include -using namespace std; - -int w[55], v[55], dp[55][1001]; -vector G[55]; - -void dfs(int i) { - dp[i][v[i]] = w[i]; - for (int j : G[i]) { - dfs(j); - for (int k = 1000; k >= 0; --k) { - for (int l = k; l >= 0; --l) dp[i][k] = min(dp[i][l] + dp[j][k - l], dp[i][k]); - } - } - dp[i][0] = 0; -} - -int main() { - ios_base::sync_with_stdio(0), cin.tie(0); - int N, W; cin >> N >> W; - for (int i = 1, p; i <= N; ++i) { - cin >> w[i] >> v[i] >> p; - G[p].push_back(i); - } - memset(dp, '?', sizeof dp); - dfs(0); - int ans = 1000; - while (dp[0][ans] > W) --ans; - cout << ans << '\n'; -} \ No newline at end of file diff --git a/2016/day3/lct.cpp b/2016/day3/lct.cpp deleted file mode 100644 index 77961fe..0000000 --- a/2016/day3/lct.cpp +++ /dev/null @@ -1,38 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ii = pair; -template class fenwick_tree { -private: vector FT; -public: - fenwick_tree(int N) { FT.assign(N + 1, 0); } - void update(int x, T val) { if (x > 0) for (; x < FT.size(); x += x & -x) FT[x] += val; } - T query(int x) { T ret = 0; if (x > 0) for (; x > 0; x -= x & -x) ret += FT[x]; return ret; } - T query(int x, int y) { return query(y) - query(x - 1); } -}; - -int N, Q, ans[200002]; -ii E[200002]; -pair q[200002]; - -int main() { - ios_base::sync_with_stdio(0), cin.tie(0); - - cin >> N >> Q; - fenwick_tree FT(N); - for (int i = 0; i < N - 1; ++i) { - cin >> E[i].f >> E[i].s; - if (E[i].f > E[i].s) swap(E[i].f, E[i].s); - FT.update(E[i].s, 1); - } - for (int i = 0; i < Q; ++i) { - cin >> q[i].f.f >> q[i].f.s; q[i].s = i; - } - sort(E, E + N - 1), sort(q, q + Q); - for (int i = 0, j = 0; i < Q; ++i) { - while (j < N - 1 && E[j].f < q[i].f.f) FT.update(E[j++].s, -1); - ans[q[i].s] = q[i].f.s - q[i].f.f + 1 - FT.query(q[i].f.s); - } - for (int i = 0; i < Q; ++i) cout << ans[i] << '\n'; -} \ No newline at end of file diff --git a/2016/day3/nickname.cpp b/2016/day3/nickname.cpp deleted file mode 100644 index 7e28696..0000000 --- a/2016/day3/nickname.cpp +++ /dev/null @@ -1,58 +0,0 @@ -#include -using namespace std; - -vector suffix_array(string& S) { - int N = S.length(); - vector SA(N), rank(N); - for (int i = 0; i < N; i++) { - SA[i] = N - i - 1; - rank[i] = S[i]; - } - stable_sort(SA.begin(), SA.end(), [&S](int i, int j) { return S[i] < S[j]; }); - for (int t = 1; t < N; t <<= 1) { - vector tmp(rank); - for (int i = 0; i < N; i++) { - bool s = i && SA[i - 1] + t < N && tmp[SA[i]] == tmp[SA[i - 1]] && tmp[SA[i] + (t >> 1)] == tmp[SA[i - 1] + (t >> 1)]; - rank[SA[i]] = s ? rank[SA[i - 1]] : i; - } - tmp = SA; - vector cnt(N); - for (int i = 0; i < N; i++) cnt[i] = i; - for (int i = 0; i < N; i++) { - if (tmp[i] >= t) SA[cnt[rank[tmp[i] - t]]++] = tmp[i] - t; - } - } - return SA; -} - -vector lcp_array(const vector& SA, string& S) { - int N = S.size(); - vector rank(N), LCP(N - 1); - for (int i = 0; i < N; i++) rank[SA[i]] = i; - int pre = 0; - for (int i = 0; i < N; i++) { - if (rank[i] < N - 1) { - int j = SA[rank[i] + 1]; - while (max(i, j) + pre < S.size() && S[i + pre] == S[j + pre]) pre++; - LCP[rank[i]] = pre; - if (pre > 0) pre--; - } - } - return LCP; -} - -int main() { - int A, B; - string X, Y; - cin >> A >> B >> X >> Y; - string S = X + '$' + Y; - vector SA = suffix_array(S); - vector L = lcp_array(SA, S); - int ans = 0; - for (int i = 0; i < S.size() - 1; ++i) { - if ((SA[i] < A && SA[i + 1] > A) || (SA[i] > A && SA[i + 1] < A)) { - ans = max(L[i], ans); - } - } - cout << ans << '\n'; -} \ No newline at end of file diff --git a/2016/day4/iqtest.cpp b/2016/day4/iqtest.cpp deleted file mode 100644 index 0f55c58..0000000 --- a/2016/day4/iqtest.cpp +++ /dev/null @@ -1,48 +0,0 @@ -#include -using namespace std; -using ll = long long; - -int N, K, A[400004]; - -inline ll pw(ll base, ll exp) { - ll res = 1; - while (exp) { - if (exp & 1) res = base * res % K; - exp >>= 1, base = base * base % K; - } - return res; -} - -int main() { - ios_base::sync_with_stdio(0), cin.tie(0); - - cin >> N >> K; - for (int i = 0; i < N; ++i) cin >> A[i]; - - ll phi = K, tmp = K; - vector factors, exp; - for (int i = 2; i * i <= K; ++i) { - if (tmp % i == 0) { - while (tmp % i == 0) tmp /= i; - factors.push_back(i), exp.push_back(0); - phi = phi * (i - 1) / i; - } - } - if (tmp > 1) { - factors.push_back(tmp), exp.push_back(0); - phi = phi * (tmp - 1) / tmp; - } - - ll cur = 1, ans = A[0]; - for (int i = 1; i < N; ++i) { - ll x = N - i, y = i; - for (int j = 0; j < factors.size(); ++j) { - while (x % factors[j] == 0) ++exp[j], x /= factors[j]; - while (y % factors[j] == 0) --exp[j], y /= factors[j]; - } - ll tmp = cur = x * pw(y, phi - 1) % K * cur % K; - for (int j = 0; j < factors.size(); ++j) tmp = pw(factors[j], exp[j]) * tmp % K; - ans = (tmp * A[i] + ans) % K; - } - cout << ans; -} \ No newline at end of file diff --git a/2017/day1/arboreal.cpp b/2017/day1/arboreal.cpp deleted file mode 100644 index 659216b..0000000 --- a/2017/day1/arboreal.cpp +++ /dev/null @@ -1,85 +0,0 @@ -#include -#include -#include -#define f first -#define s second -using namespace std; -using namespace __gnu_pbds; -using ii = pair; -template using ordered_set = tree, rb_tree_tag, tree_order_statistics_node_update>; -constexpr int MAXN = 100001; - -vector T[MAXN + 1]; -ordered_set S[4 * MAXN + 4]; - -void build(int l = 0, int r = MAXN, int n = 1) { - if (l == r) { - for (auto& y : T[l]) S[n].insert(y); - } - else { - int m = (l + r) >> 1; - build(l, m, n << 1), build(m + 1, r, n << 1 | 1); - for (auto& y : S[n << 1]) S[n].insert(y); - for (auto& y : S[n << 1 | 1]) S[n].insert(y); - } -} - -int query(int xl, int xr, int yl, int yr, int l = 0, int r = MAXN, int n = 1) { - if (l > r || l > xr || r < xl) return 0; - if (l >= xl && r <= xr) return S[n].order_of_key(yr + 1) - S[n].order_of_key(yl); - else { - int m = (l + r) >> 1; - return query(xl, xr, yl, yr, l, m, n << 1) + query(xl, xr, yl, yr, m + 1, r, n << 1 | 1); - } -} - -ii P[100001]; - -int main() { - ios_base::sync_with_stdio(0), cin.tie(0); - - int N; cin >> N; - for (int i = 0; i < N; ++i) cin >> P[i].f >> P[i].s; - - vector tmp; - for (int i = 0; i < N; ++i) tmp.emplace_back(P[i].f, i); - sort(begin(tmp), end(tmp)); - for (int i = 0; i < N; ++i) { - if (i && tmp[i].f == tmp[i - 1].f) P[tmp[i].s].f = P[tmp[i - 1].s].f; - else P[tmp[i].s].f = i; - } - tmp.clear(); - for (int i = 0; i < N; ++i) tmp.emplace_back(P[i].s, i); - sort(begin(tmp), end(tmp)); - for (int i = 0; i < N; ++i) { - if (i && tmp[i].f == tmp[i - 1].f) P[tmp[i].s].s = P[tmp[i - 1].s].s; - else P[tmp[i].s].s = i; - } - - for (int i = 0; i < N; ++i) T[P[i].f].push_back(P[i].s); - build(); - - vector X, Y; - for (int i = 0; i < N; ++i) X.push_back(P[i]), Y.push_back(P[i]); - - auto cmpy = [](const ii & a, const ii & b) { return a.s < b.s || (a.s == b.s && a.f < b.f); }; - sort(begin(X), end(X)); - sort(begin(Y), end(Y), cmpy); - unique(begin(X), end(X)); - unique(begin(Y), end(Y), cmpy); - - int ans = 0; - for (int i = 0; i < N; ++i) { - auto it = lower_bound(begin(X), end(X), ii(P[i].f, P[i].s)); - int yh = (next(it) != end(X) && next(it)->f == P[i].f ? next(it)->s : MAXN + 1); - int yl = (it != begin(X) && prev(it)->f == P[i].f ? prev(it)->s : -2); - - it = lower_bound(begin(Y), end(Y), ii(P[i].f, P[i].s), cmpy); - int xh = (next(it) != end(Y) && next(it)->s == P[i].s ? next(it)->f : MAXN + 1); - int xl = (it != begin(Y) && prev(it)->s == P[i].s ? prev(it)->f : -2); - - int q = query(xl + 1, xh - 1, yl + 1, yh - 1); - if (q > 1) ++ans; - } - cout << ans << '\n'; -} diff --git a/2017/day1/ingrass.cpp b/2017/day1/ingrass.cpp deleted file mode 100644 index 984fe20..0000000 --- a/2017/day1/ingrass.cpp +++ /dev/null @@ -1,35 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ll = long long; -using ii = pair; - -ii P[50005]; - -bool ccw(ii a, ii b, ii c) { return (ll)(b.f - a.f) * (c.s - a.s) - (ll)(c.f - a.f) * (b.s - a.s) > 0; } - -int main() { - ios_base::sync_with_stdio(0), cin.tie(0); - int N; cin >> N; - for (int i = 0; i < N; ++i) cin >> P[i].f >> P[i].s; - int m = min_element(P, P + N) - P; - vector> A; - for (int i = 0; i < N; ++i) { - if (i != m) A.emplace_back(atan2(P[i].s - P[m].s, P[i].f - P[m].f), i); - } - sort(begin(A), end(A)); - vector S; - vector ans; - for (int i = 0; i < A.size(); ++i) { - ans.emplace_back(m, A[i].s); - while (i) { - ans.emplace_back(A[i].s, S.back()); - if (S.size() <= 1 || ccw(P[A[i].s], P[S[S.size() - 2]], P[S.back()])) break; - else S.pop_back(); - } - S.push_back(A[i].s); - } - cout << 3 * N - 2 * S.size() - 4 << ' ' << ans.size() << '\n'; - for (auto& p : ans) cout << p.f + 1 << ' ' << p.s + 1 << '\n'; -} \ No newline at end of file diff --git a/2017/day1/palindrome.cpp b/2017/day1/palindrome.cpp deleted file mode 100644 index dbf5fd6..0000000 --- a/2017/day1/palindrome.cpp +++ /dev/null @@ -1,30 +0,0 @@ -#include -using namespace std; - -int N, s[100001], dp[100001][606]; -inline int & get(int i, int j) { return dp[i][N - j - i + 301]; } - -int main() { - ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); - - cin >> N; - for (int i = 0; i < N; ++i) cin >> s[i]; - - memset(dp, '?', sizeof dp); - get(0, N) = 0; - for (int i = 0; i < N; ++i) { - for (int j = min(N - i + 300, N); j >= max(N - i - 300, i); --j) { - get(i + 1, j) = min(get(i, j) + 1, get(i + 1, j)); - get(i, j - 1) = min(get(i, j) + 1, get(i, j - 1)); - if (s[i] == s[j - 1]) get(i + 1, j - 1) = min(get(i, j), get(i + 1, j - 1)); - } - } - - int ans = 1e9; - for (int i = 0; i < N; ++i) { - if (N - 2 * i + 301 >= 0 && N - 2 * i + 301 < 606) ans = min(get(i, i), ans); - if (N - 2 * i + 300 >= 0 && N - 2 * i + 300 < 606) ans = min(get(i, i + 1), ans); - } - if (ans <= 300) cout << ans << '\n'; - else cout << "many\n"; -} \ No newline at end of file diff --git a/2017/day2/cookie.cpp b/2017/day2/cookie.cpp deleted file mode 100644 index d03e72f..0000000 --- a/2017/day2/cookie.cpp +++ /dev/null @@ -1,37 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ll = long long; -using pl = pair; - -ll C[5005], D[5005]; -pl DP[5005][5005]; - -int main() { - ios_base::sync_with_stdio(0), cin.tie(0); - - ll N, T, RA, RB; - cin >> N >> T >> RA >> RB; - for (int i = 0; i < N; ++i) cin >> C[i]; - for (int i = 0; i < N; ++i) cin >> D[i]; - - memset(DP, 63, sizeof(DP)); - DP[0][0] = pl(0, 0); - ll ans = T; - for (int i = 0; i <= N; ++i) { - for (int j = 0; j <= N; ++j) { - ll r = 1 + i * RA + j * RB; - if (i < N) { - ll t = max((C[i] + DP[i][j].s + r - 1) / r, 0ll); - DP[i + 1][j] = min(pl(DP[i][j].f + t, -t * r + C[i] + DP[i][j].s), DP[i + 1][j]); - } - if (j < N) { - ll t = max((D[j] + DP[i][j].s + r - 1) / r, 0ll); - DP[i][j + 1] = min(pl(DP[i][j].f + t, -t * r + D[j] + DP[i][j].s), DP[i][j + 1]); - } - ans = min(DP[i][j].f + max((T + DP[i][j].s + r - 1) / r, 0ll), ans); - } - } - cout << ans << '\n'; -} \ No newline at end of file diff --git a/2017/day2/lazybubblesort.cpp b/2017/day2/lazybubblesort.cpp deleted file mode 100644 index 8395298..0000000 --- a/2017/day2/lazybubblesort.cpp +++ /dev/null @@ -1,20 +0,0 @@ -#include -using namespace std; - -int A[100001]; - -int main() { - int N, K; cin >> N >> K; - for (int i = 0; i < N; ++i) cin >> A[i]; - multiset S; - vector ans; - for (int i = 0; i < N; ++i) { - if (S.size() < K || A[i] > *begin(S)) { - if (S.size() == K) ans.push_back(*begin(S)), S.erase(begin(S)); - S.insert(A[i]); - } - else ans.push_back(A[i]); - } - while (S.size()) ans.push_back(*begin(S)), S.erase(begin(S)); - for (auto& x : ans) cout << x << '\n'; -} \ No newline at end of file diff --git a/2017/day3/balancing.cpp b/2017/day3/balancing.cpp deleted file mode 100644 index c5fa7c6..0000000 --- a/2017/day3/balancing.cpp +++ /dev/null @@ -1,23 +0,0 @@ -#include -using namespace std; - -int main() { - ios_base::sync_with_stdio(0), cin.tie(0); - string S; cin >> S; - int N = S.size(), cnt = 0; - if (count(begin(S), end(S), 'G') << 1 != N) { - cout << "NO\n"; - return 0; - } - unordered_set M[2]; - for (int i = 0; i < N; ++i) { - if (S[i] != S[(i-1+N)%N]) M[S[i] == 'G'].insert(cnt); - cnt += (S[i] == 'G' ? 1 : -1); - if (S[i] != S[(i+1)%N] && M[S[i] == 'G'].find(cnt - (S[i] == 'G' ? 1 : -1)) != end(M[S[i] == 'G'])) { - cout << "YES\n"; - return 0; - } - } - cout << "NO\n"; - return 0; -} \ No newline at end of file diff --git a/2017/day3/timeline.cpp b/2017/day3/timeline.cpp deleted file mode 100644 index a6b8e30..0000000 --- a/2017/day3/timeline.cpp +++ /dev/null @@ -1,41 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ii = pair; - -int dist[5005]; -vector G[5005]; - -int main() { - ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); - int N, M, C; cin >> N >> M >> C; - for (int u = 1; u <= N; ++u) { - int s, t; cin >> s >> t; - G[u].emplace_back(-s, 0); - G[0].emplace_back(t, u); - } - while (C--) { - int a, b, x; cin >> a >> b >> x; - G[a].emplace_back(-x, b); - } - memset(dist, '?', sizeof dist); - dist[0] = 0; - for (int i = 0; i < N; ++i) { - for (int u = 0; u <= N; ++u) { - for (auto& v : G[u]) { - if (dist[u] + v.f < dist[v.s]) dist[v.s] = dist[u] + v.f; - } - } - } - for (int u = 0; u <= N; ++u) { - for (auto& v : G[u]) { - if (dist[u] < 0 || dist[u] > M || dist[u] + v.f < dist[v.s]) { - cout << "impossible\n"; - return 0; - } - } - } - for (int u = 1; u <= N; ++u) cout << dist[u] << '\n'; - return 0; -} \ No newline at end of file diff --git a/2017/day4/knights.cpp b/2017/day4/knights.cpp deleted file mode 100644 index 784abfc..0000000 --- a/2017/day4/knights.cpp +++ /dev/null @@ -1,91 +0,0 @@ -#include -using namespace std; -using ll = long long; -constexpr ll INF = 1e12; - -int dx[] = { 2, 1, -1, -2, -2, -1, 1, 2 }; -int dy[] = { 1, 2, 2, 1, -1, -2, -2, -1 }; -char A[101][101]; - -template class max_flow { - struct edge { - int t, rev; - T cap, f; - }; - vector adj[V]; - int dist[V]; - int ptr[V]; - bool bfs(int s, int t) { - memset(dist, -1, sizeof dist); - dist[s] = 0; - queue q({ s }); - while (!q.empty() && dist[t] == -1) { - int n = q.front(); - q.pop(); - for (auto& e : adj[n]) { - if (dist[e.t] == -1 && e.cap != e.f) { - dist[e.t] = dist[n] + 1; - q.push(e.t); - } - } - } - return dist[t] != -1; - } - T augment(int n, T amt, int t) { - if (n == t) return amt; - for (; ptr[n] < adj[n].size(); ptr[n]++) { - edge& e = adj[n][ptr[n]]; - if (dist[e.t] == dist[n] + 1 && e.cap != e.f) { - T flow = augment(e.t, min(amt, e.cap - e.f), t); - if (flow != 0) { - e.f += flow; - adj[e.t][e.rev].f -= flow; - return flow; - } - } - } - return 0; - } -public: - void add(int u, int v, T cap = 1, T rcap=0) { - adj[u].push_back({ v, (int) adj[v].size(), cap, 0 }); - adj[v].push_back({ u, (int) adj[u].size() - 1, rcap, 0 }); - } - T calc(int s, int t) { - T flow = 0; - while (bfs(s, t)) { - memset(ptr, 0, sizeof ptr); - while (T df = augment(s, INF, t)) flow += df; - } - return flow; - } - void clear() { - for (int n = 0; n < V; n++) adj[n].clear(); - } -}; - -int main() { - int R, C; - cin >> R >> C; - int ans = R * C; - for (int i = 0; i < R; ++i) { - for (int j = 0; j < C; ++j) cin >> A[i][j]; - } - - max_flow<101*101> MF; - for (int i = 0; i < R; ++i) { - for (int j = 0; j < C; ++j) { - if (A[i][j] == '#') { --ans; continue; } - if (i + j & 1) { - MF.add(10000, i * C + j, (A[i][j] == 'C' ? INF : 1)); - for (int d = 0; d < 8; ++d) { - int x = i + dx[d], y = j + dy[d]; - if (x < 0 || x >= R || y < 0 || y >= C || A[x][y] == '#') continue; - MF.add(i * C + j, x * C + y, INF); - } - } - else MF.add(i * C + j, 10001, (A[i][j] == 'C' ? INF : 1)); - } - } - cout << ans - MF.calc(10000, 10001) << '\n'; -} \ No newline at end of file diff --git a/2017/day4/stock_trading.cpp b/2017/day4/stock_trading.cpp deleted file mode 100644 index c2aa679..0000000 --- a/2017/day4/stock_trading.cpp +++ /dev/null @@ -1,21 +0,0 @@ -#include -using namespace std; -using ll = long long; - -int main() { - ios_base::sync_with_stdio(0), cin.tie(0); - - int N, L; - cin >> N >> L; - - multiset S; - ll ans = 0; - for (int i = 0, b, s; i < N; ++i) { - cin >> b >> s; - ans = max(ans - (i >= L ? *begin(S) : 0) + s, ans); - S.insert({ b, s }); - if (i >= L) S.erase(begin(S)), S.erase(prev(end(S))); - } - for (auto it = S.begin(); L; ++it, --L) ans -= *it; - cout << ans << endl; -} \ No newline at end of file diff --git a/2017/day4/tuning.cpp b/2017/day4/tuning.cpp deleted file mode 100644 index d2bddd9..0000000 --- a/2017/day4/tuning.cpp +++ /dev/null @@ -1,22 +0,0 @@ -#include -using namespace std; - -int main() { - ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); - - int N; - cin >> N; - int ans = 1, cnt = 1; - for (int i = 2; i < N; ++i) { - if (cnt) { - cout << ans << ' ' << i << endl; - string s; cin >> s; - s[0] == 'S' ? ++cnt : --cnt; - } - else { - ans = i; - ++cnt; - } - } - cout << (cnt ? ans : N) << endl; -} \ No newline at end of file diff --git a/2017/day5/trip.cpp b/2017/day5/trip.cpp deleted file mode 100644 index 35ded67..0000000 --- a/2017/day5/trip.cpp +++ /dev/null @@ -1,41 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ll = long long; -using ii = pair; - -vector G[100001]; -unordered_map A[100001], B[100001]; - -ll dfs(int u, int p) { - sort(begin(G[u]), end(G[u])); - ll ret = 0, sa = 1, tmp = 0, l = -1; - ++A[u][0], ++B[u][1e9+7]; - for (auto& v : G[u]) { - if (v.s != p) { - ret += dfs(v.s, u); - ll ca = 0, cb = 0; - for (auto& x : A[v.s]) { - if (x.f < v.f) ca += x.s, A[u][v.f] += x.s; - } - for (auto& x : B[v.s]) { - if (x.f > v.f) cb += x.s, B[u][v.f] += x.s; - } - ret += cb * sa, sa += ca; - if (v.f != l) l = v.f, tmp = ca; - else ret -= cb * tmp, tmp += ca; - } - } - return ret + sa - 1; -} - -int main() { - int N; - cin >> N; - for (int i = 1, a, b, e; i < N; ++i) { - cin >> a >> b >> e; - G[a].emplace_back(e, b), G[b].emplace_back(e, a); - } - cout << dfs(1, 0) << '\n'; -} \ No newline at end of file diff --git a/2018/day1/fanfiction.cpp b/2018/day1/fanfiction.cpp deleted file mode 100644 index 82c06c1..0000000 --- a/2018/day1/fanfiction.cpp +++ /dev/null @@ -1,85 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ll = long long; -using ii = pair; - -int N, T, c[2552], f[2552], g[2552][26], G[2552][26]; -ll out[2552], dp[2552][2552]; -string B, S[2552]; - -int aho_corasick() { - memset(g, -1, sizeof g), memset(out, 0, sizeof out); - int nodes = 1; - for (int i = 0; i < N; i++) { - int cur = 0; - for (int j = 0; j < S[i].size(); j++) { - if (g[cur][S[i][j] - 'a'] == -1) g[cur][S[i][j] - 'a'] = ++nodes; - cur = g[cur][S[i][j] - 'a']; - } - ++out[cur]; - } - for (int ch = 0; ch < T; ch++) { - if (g[0][ch] == -1) g[0][ch] = 0; - } - memset(f, -1, sizeof f); - queue q; - for (int ch = 0; ch < T; ch++) { - if (g[0][ch] != 0) { - f[g[0][ch]] = 0; - q.push(g[0][ch]); - } - } - while (!q.empty()) { - int state = q.front(); - q.pop(); - for (int ch = 0; ch < T; ch++) { - if (g[state][ch] == -1) continue; - int fail = f[state]; - while (g[fail][ch] == -1) fail = f[fail]; - f[g[state][ch]] = g[fail][ch]; - out[g[state][ch]] += out[g[fail][ch]]; - q.push(g[state][ch]); - } - } - return nodes; -} - -int main() { - ios_base::sync_with_stdio(0), cin.tie(0); - - cin >> N >> T; - for (int i = 0; i < N; ++i) cin >> S[i]; - cin >> B; - int L = B.size(); - for (int i = 0; i < L; ++i) cin >> c[i]; - - int M = aho_corasick(); - - for (int i = 0; i < M; ++i) { - for (int j = 0; j < T; ++j) { - int k = i; - while (g[k][j] == -1) k = f[k]; - G[i][j] = g[k][j]; - } - } - - memset(dp, '?', sizeof dp); - dp[0][0] = 0; - for (int i = 0; i < L; ++i) { - for (int j = 0; j < M; ++j) { - if (!out[j]) { - for (int k = 0; k < T; ++k) { - dp[i + 1][G[j][k]] = min(dp[i][j] + c[i] * (k != B[i] - 'a'), dp[i + 1][G[j][k]]); - } - } - } - } - - ll ans = 1e18; - for (int i = 0; i < M; ++i) { - if (!out[i]) ans = min(dp[L][i], ans); - } - cout << (ans < 1e18 ? ans : -1) << '\n'; -} \ No newline at end of file diff --git a/2018/day1/grazing.cpp b/2018/day1/grazing.cpp deleted file mode 100644 index dcc8a79..0000000 --- a/2018/day1/grazing.cpp +++ /dev/null @@ -1,62 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -typedef long long ll; -typedef pair ii; -typedef vector vi; -typedef vector vii; - -const int dx[] = { 1, 0, -1, 0 }; -const int dy[] = { 0, 1, 0, -1 }; - -int N, M, A[11][11], vis[11][11]; -vi G[11][11]; -vii S; - -bool valid(int x, int y) { return x >= 0 && x < N && y >= 0 && y < M; }; - -void dfs(int i, int j) { - vis[i][j] = -1; - for (auto& d : G[i][j]) - if (!vis[i + dx[d]][j + dy[d]]) dfs(i + dx[d], j + dy[d]); - vis[i][j] = 1; - S.emplace_back(i, j); -} - -int main() { - ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); - - cin >> N >> M; - for (int i = 0; i < N; ++i) { - for (int j = 0; j < M; ++j) cin >> A[i][j]; - } - - for (int i = 0; i < N; ++i) { - for (int j = 0; j < M; ++j) { - for (int d = 0; d < 4; ++d) { - if (valid(i + dx[d], j + dy[d]) && A[i + dx[d]][j + dy[d]] <= A[i][j]) - G[i][j].push_back(d); - } - } - } - - for (int i = 0; i < N; ++i) { - for (int j = 0; j < M; ++j) { - if (!vis[i][j]) dfs(i, j); - } - } - - memset(vis, 0, sizeof vis); - int ans = 0; - for (int i = S.size() - 1; i >= 0; --i) { - ii p = S[i]; - ans += A[p.f][p.s]; - for (int d = 0; d < 4; ++d) { - if (valid(p.f + dx[d], p.s + dy[d]) && vis[p.f + dx[d]][p.s + dy[d]]) - ans += A[p.f + dx[d]][p.s + dy[d]]; - } - vis[p.f][p.s] = 1; - } - cout << ans << '\n'; -} \ No newline at end of file diff --git a/2018/day1/tastyhay.cpp b/2018/day1/tastyhay.cpp deleted file mode 100644 index 8ef6d42..0000000 --- a/2018/day1/tastyhay.cpp +++ /dev/null @@ -1,32 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ll = long long; -using ii = pair; - -int t[100001]; -map cnt, pre; - -int main() { - int N, Q; - cin >> N >> Q; - for (int i = 0; i < N; ++i) cin >> t[i]; - - unordered_map m; - for (int i = N - 1; i >= 0; --i) { - unordered_map tmp; - for (auto x : m) tmp[__gcd(t[i], x.f)] += x.s; - ++tmp[t[i]]; - swap(tmp, m); - for (auto& x : m) cnt[x.f] += x.s; - } - for (auto& x : cnt) pre[x.f] = x.s + (pre.size() ? pre.rbegin()->s : 0); - - while (Q--) { - int a, b; - cin >> a >> b; - auto ia = pre.upper_bound(a - 1), ib = pre.upper_bound(b); - cout << (ib != pre.begin() ? prev(ib)->s : 0) - (ia != pre.begin() ? prev(ia)->s : 0) << '\n'; - } -} \ No newline at end of file diff --git a/2018/day2/cowcliquer.cpp b/2018/day2/cowcliquer.cpp deleted file mode 100644 index fc7f9e9..0000000 --- a/2018/day2/cowcliquer.cpp +++ /dev/null @@ -1,39 +0,0 @@ -#include "grader.h" -#include -#define par first -#define sz second -using namespace std; -using ii = pair; -constexpr int INF = 2e9; - -int cnt; -unordered_map s; -vector> m[200002]; - -inline void alloc(string cow) { if (s.find(cow) == end(s)) s[cow] = ++cnt, m[cnt].emplace_back(0, ii(cnt, 1)); } - -inline ii & get(int i, int timestamp) { return prev(upper_bound(begin(m[i]), end(m[i]), make_pair(timestamp, ii(INF, 0))))->second; } - -int find_set(int i, int timestamp) { - int & p = get(i, timestamp).par; - return (p == i) ? i : (p = find_set(p, timestamp)); -} - -void add_friend(string cow1, string cow2, int timestamp) { - alloc(cow1), alloc(cow2); - int i = find_set(s[cow1], timestamp), j = find_set(s[cow2], timestamp); - if (i == j) return; - ii x = get(i, timestamp), y = get(j, timestamp); - if (x.sz < y.sz) swap(i, j); - m[i].emplace_back(timestamp, ii(i, x.sz + y.sz)), m[j].emplace_back(timestamp, ii(i, 0)); -} - -bool check_friend(string cow1, string cow2, int timestamp) { - alloc(cow1), alloc(cow2); - return find_set(s[cow1], timestamp) == find_set(s[cow2], timestamp); -} - -int get_number_of_friends(string cow, int timestamp) { - alloc(cow); - return get(find_set(s[cow], timestamp), timestamp).sz; -} \ No newline at end of file diff --git a/2018/day2/grader.h b/2018/day2/grader.h deleted file mode 100644 index bbe8639..0000000 --- a/2018/day2/grader.h +++ /dev/null @@ -1,55 +0,0 @@ -#include - -/* - * You need to implement the following functions: - */ - -void add_friend(std::string cow1, std::string cow2, int timestamp); -bool check_friend(std::string cow1, std::string cow2, int timestamp); -int get_number_of_friends(std::string cow, int timestamp); - -// Commands have the following format: -// A c1 c2 t -// - Calls "add"friend" on cows "c1" and "c2" at timestamp t. You are -// guaranteed that successive calls to A will have increasing values of t. -// C c1 c2 t -// - Calls "check_friend" on cows "c1" and "c2" at timestamp t. -// N c t -// - Calls "get_number_of_friends" on cow "c" at timestamp "t". - -// You don't need to read or understand any of the code below, -// but it may be helpful. - -int main() { - int num_commands; - std::cin >> num_commands; - - for (int i = 0; i < num_commands; ++i) { - std::string command_type; - std::cin >> command_type; - - if (command_type == "A") { - std::string cow1, cow2; - int timestamp; - std::cin >> cow1 >> cow2 >> timestamp; - - add_friend(cow1, cow2, timestamp); - } else if (command_type == "C") { - std::string cow1, cow2; - int timestamp; - std::cin >> cow1 >> cow2 >> timestamp; - - std::string responses[] = {"FALSE", "TRUE"}; - std::cout << responses[check_friend(cow1, cow2, timestamp)] << std::endl; - } else if (command_type == "N") { - std::string cow; - int timestamp; - std::cin >> cow >> timestamp; - - std::cout << get_number_of_friends(cow, timestamp) << std::endl; - } else { - std::cout << "Invalid command type: " << command_type << std::endl; - exit(1); - } - } -} diff --git a/2018/day2/sweetgrass.cpp b/2018/day2/sweetgrass.cpp deleted file mode 100644 index 96380bf..0000000 --- a/2018/day2/sweetgrass.cpp +++ /dev/null @@ -1,66 +0,0 @@ -#include -using namespace std; - -int N, idx[100001]; -bitset<100001> vis, ans; -vector path; -unordered_set G[100001]; - -void solve() { - vis.reset(); - for (int i = 0; i < path.size() - 1; ++i) { - G[path[i]].erase(path[i + 1]); - } - memset(idx, -1, sizeof idx); - for (int i = 0; i < path.size(); ++i) idx[path[i]] = i; - int m = 0; - ans.set(); - for (int i = 0; i < path.size() - 1; ++i) { - m = max(i + 1, m); - queue q; - q.push(path[i]); - while (q.size()) { - int u = q.front(); - q.pop(); - if (vis[u]) continue; - vis[u] = 1; - if (u != path[i] && idx[u] != -1) { - for (int j = m; j < idx[u]; ++j) - ans[j] = 0; - m = max(idx[u], m); - continue; - } - for (auto& v : G[u]) { - if (!vis[v]) q.push(v); - } - } - } - vector out; - for (int i = 1; i < path.size() - 1; ++i) - if (ans[i]) out.push_back(path[i]); - sort(begin(out), end(out)); - cout << out.size() << '\n'; - for (auto& x : out) cout << x << '\n'; -} - -void dfs(int u) { - vis[u] = 1; - path.push_back(u); - if (u == N) { - solve(); - exit(0); - } - for (auto& v : G[u]) { - if (!vis[v]) dfs(v); - } - path.pop_back(); -} - -int main() { - int M; cin >> N >> M; - while (M--) { - int a, b; cin >> a >> b; - G[a].insert(b); - } - dfs(1); -} \ No newline at end of file diff --git a/2018/day5/cowmooting.cpp b/2018/day5/cowmooting.cpp deleted file mode 100644 index 86f6460..0000000 --- a/2018/day5/cowmooting.cpp +++ /dev/null @@ -1,35 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ll = long long; -using ii = pair; - -vector> G[101]; -ll dist[101][10001]; - -int main() { - int B, M, N; cin >> B >> M >> N; - while (M--) { - int a, b, t, c; cin >> a >> b >> t >> c; - G[a].emplace_back(ii(t, c), b), G[b].emplace_back(ii(t, c), a); - } - memset(dist, '?', sizeof dist); - dist[0][0] = 0; - priority_queue, vector>, greater>> pq; - pq.emplace(0, ii(0, 0)); - while (!pq.empty()) { - ll d = pq.top().f; ii u = pq.top().s; - pq.pop(); - if (d > dist[u.f][u.s]) continue; - for (auto& v : G[u.f]) { - if (u.s + v.f.f < 1e4 && d + v.f.s < dist[v.s][u.s + v.f.f]) { - dist[v.s][u.s + v.f.f] = d + v.f.s; - pq.emplace(dist[v.s][u.s + v.f.f], ii(v.s, u.s + v.f.f)); - } - } - } - int ans = 0; - while (ans < 1e4 && dist[1][ans] > B) ++ans; - cout << (ans < 1e4 ? ans : -1) << '\n'; -} \ No newline at end of file diff --git a/2018/day5/mootube.cpp b/2018/day5/mootube.cpp deleted file mode 100644 index b146b56..0000000 --- a/2018/day5/mootube.cpp +++ /dev/null @@ -1,78 +0,0 @@ -#include -using namespace std; -using ll = long long; -constexpr ll p1 = 19, p2 = 29, p3 = 53; -constexpr ll MOD = 1e9+7; - -template struct vec_nd : public vector> { - static_assert(D >= 1, "Vector dimension must be greater than zero!"); - template vec_nd(int n = 0, Args... args) : vector>(n, vec_nd(args...)) { } -}; -template struct vec_nd<1, T> : public vector { vec_nd(int n = 0, const T& val = T()) : vector(n, val) { } }; - -int pw(int base, int exp) { - int res = 1; - while (exp) { - if (exp & 1) res = (ll)base * res % MOD; - exp >>= 1, base = (ll)base * base % MOD; - } - return res; -} - -int inv(int x) { return pw(x, MOD - 2); } - -int main() { - int T1, R1, C1; cin >> T1 >> R1 >> C1; - vec_nd<3, ll> A(T1, R1, C1); - for (int i = 0; i < T1; ++i) for (int j = 0; j < R1; ++j) for (int k = 0; k < C1; ++k) cin >> A[i][j][k]; - - int T2, R2, C2; cin >> T2 >> R2 >> C2; - vec_nd<3, ll> B(T2, R2, C2); - for (int i = 0; i < T2; ++i) for (int j = 0; j < R2; ++j) for (int k = 0; k < C2; ++k) cin >> B[i][j][k]; - - ll h = 0; - ll pw1 = 1; for (int i = 0; i < T1; ++i) { - ll pw2 = 1; for (int j = 0; j < R1; ++j) { - ll pw3 = 1; for (int k = 0; k < C1; ++k) { - h = (A[i][j][k] * pw1 % MOD * pw2 % MOD * pw3 + h) % MOD; - pw3 = p3 * pw3 % MOD; } - pw2 = p2 * pw2 % MOD; } - pw1 = p1 * pw1 % MOD; } - - vec_nd<3, ll> S(T2, R2, C2); - pw1 = 1; for (int i = 0; i < T2; ++i) { - ll pw2 = 1; for (int j = 0; j < R2; ++j) { - ll pw3 = 1; for (int k = 0; k < C2; ++k) { - S[i][j][k] = B[i][j][k] * pw1 % MOD * pw2 % MOD * pw3 % MOD; - if (i) S[i][j][k] += S[i - 1][j][k]; - if (j) S[i][j][k] += S[i][j - 1][k]; - if (k) S[i][j][k] += S[i][j][k - 1]; - if (i && j) S[i][j][k] -= S[i - 1][j - 1][k]; - if (i && k) S[i][j][k] -= S[i - 1][j][k - 1]; - if (j && k) S[i][j][k] -= S[i][j - 1][k - 1]; - if (i && j && k) S[i][j][k] += S[i - 1][j - 1][k - 1]; - S[i][j][k] = (S[i][j][k] + MOD * MOD) % MOD; - pw3 = p3 * pw3 % MOD; } - pw2 = p2 * pw2 % MOD; } - pw1 = p1 * pw1 % MOD; } - - ll ans = 0; - pw1 = 1; for (int i = 0; i <= T2 - T1; ++i) { - ll pw2 = 1; for (int j = 0; j <= R2 - R1; ++j) { - ll pw3 = 1; for (int k = 0; k <= C2 - C1; ++k) { - ll h2 = S[i + T1 - 1][j + R1 - 1][k + C1 - 1]; - if (i) h2 -= S[i - 1][j + R1 - 1][k + C1 - 1]; - if (j) h2 -= S[i + T1 - 1][j - 1][k + C1 - 1]; - if (k) h2 -= S[i + T1 - 1][j + R1 - 1][k - 1]; - if (i && j) h2 += S[i - 1][j - 1][k + C1 - 1]; - if (i && k) h2 += S[i - 1][j + R1 - 1][k - 1]; - if (j && k) h2 += S[i + T1 - 1][j - 1][k - 1]; - if (i && j && k) h2 -= S[i - 1][j - 1][k - 1]; - h2 = (h2 + MOD * MOD) % MOD; - h2 = h2 * inv(pw3) % MOD * inv(pw2) % MOD * inv(pw1) % MOD; - if (h2 == h) ++ans; - pw3 = p3 * pw3 % MOD; } - pw2 = p2 * pw2 % MOD; } - pw1 = p1 * pw1 % MOD; } - cout << ans << '\n'; -} \ No newline at end of file diff --git a/2019/day1/out b/2019/day1/out deleted file mode 100644 index 67f3f23..0000000 --- a/2019/day1/out +++ /dev/null @@ -1 +0,0 @@ -270 diff --git a/2019/day1/palindrometer.cpp b/2019/day1/palindrometer.cpp deleted file mode 100644 index 65914fa..0000000 --- a/2019/day1/palindrometer.cpp +++ /dev/null @@ -1,22 +0,0 @@ -#include -using namespace std; -using ll = long long; - -int P[2][100001]; - -int main() { - string S; cin >> S; - int N = S.size(); - for (int i = 0; i < 2; ++i) { - for (int j = 0, l = 0, r = 0; j < N; ++j) { - int k = (j > r ? !i : min(P[i][l + r - j + i], r - j + 1)); - while (j - k - i >= 0 && j + k < N && S[j - k - i] == S[j + k]) ++k; - P[i][j] = k--; - if (j + k > r) l = j - k - i, r = j + k; - } - } - - ll ans = 0; - for (int i = 0; i < N; ++i) ans += P[0][i] + P[1][i]; - cout << ans << '\n'; -} \ No newline at end of file diff --git a/2019/day1/retemordnilap.cpp b/2019/day1/retemordnilap.cpp deleted file mode 100644 index 991bc78..0000000 --- a/2019/day1/retemordnilap.cpp +++ /dev/null @@ -1,42 +0,0 @@ -#include -using namespace std; -using ll = long long; - -int main() { - char s[10] = "MMOOMO"; - int K; - cin >> K; - if (K == 5) { - cout << "impossible"; - return 0; - } - if (K == 1) { cout << "O"; return 0; } - if (K == 2) { cout << "MO"; return 0; } - if (K == 3) { cout << "MM"; return 0; } - if (K == 7) { cout << "MMMO"; return 0; } - if (K == 9) { cout << "MOMOM"; return 0; } - if (K % 2 == 0 && K / 2 <= 1e5) { - for (int i = 0; i <= K / 2; ++i) cout << s[i % 6]; - return 0; - } - ll sq = sqrt(8ll * K + 1) + 0.5; - if (sq * sq == 8ll * K + 1) { - int t = (sq - 1) / 2; - for (int i = 0; i < t; ++i) cout << "O"; - return 0; - } - /*if (K > 1e8 && K % 2 == 1) { - cout << "M"; - --K; - }*/ - int t = sqrt(2 * K); - while ((((K - t * (t + 1) / 2) - 2) % 2) || K - t * (t + 1) / 2 - 2 < 6) --t; - for (int i = 0; i < t; ++i) cout << "O"; - int ans = t; - //cout << t << '\n'; - K += - t * (t + 1) / 2 - 2; - for (int i = 0; i <= K / 2; ++i) cout << s[i % 6]; - ans += K / 2; - assert(ans <= 1e5); - //cout << ans << '\n'; -} \ No newline at end of file diff --git a/2019/day1/test.sh b/2019/day1/test.sh deleted file mode 100644 index 3b4f3f1..0000000 --- a/2019/day1/test.sh +++ /dev/null @@ -1,9 +0,0 @@ -for i in {6..1000} -do - echo $i >> in - .vscode/3 < in | .vscode/1 > out - if !(cmp -s in out); then - echo $i - fi - rm in -done \ No newline at end of file diff --git a/2019/day1/treedist.cpp b/2019/day1/treedist.cpp deleted file mode 100644 index a2c83ae..0000000 --- a/2019/day1/treedist.cpp +++ /dev/null @@ -1,44 +0,0 @@ -#include -#define f first -#define s second -#define eb emplace_back -using namespace std; -using ll = long long; -using ii = pair; -constexpr int MAXN = 100001; -constexpr ll INF = 1e9; - -int N, Q, H[MAXN]; -bitset ans; -vector G[3 * MAXN]; -unordered_map vis; - -void solve(int u, int p, int d) { - if (d && u <= N) ans[u] = 1; - if (d < 0) d = -1; - if (vis.find(INF * u + p) != vis.end()) { - if (vis[INF * u + p] != d) d = -1; - else return; - } - vis[INF * u + p] = d; - for (auto & v : G[u]) if (v.s != p) solve(v.s, u, d - v.f); -} - -int main() { - ios_base::sync_with_stdio(0), cin.tie(0); - cin >> N >> Q; - iota(H, H + N + 1, 0); - int l = N + 1; - for (int i = 1, a, b; i < N; ++i) { - cin >> a >> b; - G[H[a]].eb(0, l), G[l].eb(0, H[a]), H[a] = l++; - G[H[b]].eb(0, l), G[l].eb(0, H[b]), H[b] = l++; - G[H[a]].eb(1, H[b]), G[H[b]].eb(1, H[a]); - } - while (Q--) { - int a, b; cin >> a >> b; - solve(a, 0, b); - } - cout << N - ans.count() << '\n'; - for (int i = 1; i <= N; ++i) if (!ans[i]) cout << i << '\n'; -} \ No newline at end of file diff --git a/2019/day2/mana.cpp b/2019/day2/mana.cpp deleted file mode 100644 index 7fad64b..0000000 --- a/2019/day2/mana.cpp +++ /dev/null @@ -1,31 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ii = pair; - -vector S[101]; - -int main() { - ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); - - int M, R, N; - cin >> M >> R >> N; - for (int i = 0, a, c, d; i < N; ++i) { - cin >> a >> c >> d; - S[d].emplace_back(a, c); - } - int T = M + 100 * R; - vector dp(T + 1, -1e9); - dp[0] = 0; - for (int d = 0; d <= 100; ++d) { - int g = M + d * R; - for (auto& p : S[d]) { - int a = p.f, c = p.s; - for (int i = g - c; i >= 0; --i) dp[i + c] = max(dp[i] + a, dp[i + c]); - } - } - int ans = 0; - for (auto& x : dp) ans = max(x, ans); - cout << ans << '\n'; -} \ No newline at end of file diff --git a/2019/day2/themepark.cpp b/2019/day2/themepark.cpp deleted file mode 100644 index 2582eb3..0000000 --- a/2019/day2/themepark.cpp +++ /dev/null @@ -1,42 +0,0 @@ -#include -using namespace std; -constexpr int MAXN = 100001; - -int c[MAXN]; -vector G[MAXN]; - -int cnt, scc_num, scc[MAXN], in[MAXN], low[MAXN]; -stack s; -bitset ins; - -void tarjan(int u) { - low[u] = in[u] = cnt++; - s.push(u); - ins[u] = 1; - for (int v : G[u]) { - if (in[v] == -1) tarjan(v), low[u] = min(low[u], low[v]); - else if (ins[v]) low[u] = min(low[u], in[v]); - } - if (low[u] == in[u]) { - ++scc_num; - while (1) { - int x = s.top(); s.pop(); - scc[x] = scc_num, ins[x] = 0; - if (x == u) break; - } - } -} - -int main() { - int N, M, K; cin >> N >> M >> K; - while (M--) { - int a, b; cin >> a >> b; - G[a].push_back(b); - } - - memset(scc, -1, sizeof scc), memset(in, -1, sizeof in); - for (int u = 1; u <= N; ++u) if (scc[u] == -1) tarjan(u); - - if (scc_num < K) cout << "impossible\n"; - else for (int u = 1; u <= N; ++u) cout << min(scc[u], K) << '\n'; -} \ No newline at end of file diff --git a/2020/day1/repl.cpp b/2020/day1/repl.cpp deleted file mode 100644 index 6b0a301..0000000 --- a/2020/day1/repl.cpp +++ /dev/null @@ -1,43 +0,0 @@ -#include -#define f first -#define s second -#define pb push_back -#define eb emplace_back -using namespace std; -using ll = long long; -using ii = pair; -using vi = vector; -using vii = vector; - -vi G[100001]; - -bool test(int x, vector & ch) { - ll tmp = 1; - for (auto& c : ch) { - if (c > x || !tmp) return 0; - tmp = min(tmp * (1 << min(x - c, 20)) - 1, 100001ll), x = c; - } - return tmp; -} - -int dfs(int u, int p) { - vi ch; - for (auto& v : G[u]) if (v != p) ch.push_back(dfs(v, u)); - if (ch.empty()) return 0; - sort(begin(ch), end(ch), greater()); - int l = ch[0] + 1, r = 100001; - while (l < r) { - int m = (l + r) / 2; - test(m, ch) ? r = m : l = m + 1; - } - return l; -} - -int main() { - int N; cin >> N; - for (int i = 1; i < N; ++i) { - int a, b; cin >> a >> b; - G[a].push_back(b), G[b].push_back(a); - } - cout << dfs(1, 0) + N - 1 << '\n'; -} \ No newline at end of file diff --git a/2020/day1/tri.cpp b/2020/day1/tri.cpp deleted file mode 100644 index a28df48..0000000 --- a/2020/day1/tri.cpp +++ /dev/null @@ -1,42 +0,0 @@ -#include -#define f first -#define s second -#define pb push_back -#define eb emplace_back -using namespace std; -using ll = long long; -using ii = pair; -using vi = vector; -using vii = vector; - -ii E[100001]; -vi G[100001]; -bitset<100001> vis, oc; - -int main() { - int N, M; - cin >> N >> M; - for (int i = 0; i < M; ++i) { - cin >> E[i].f >> E[i].s; - G[E[i].f].pb(E[i].s), G[E[i].s].pb(E[i].f); - } - - vi v; - for (int i = 1; i <= N; ++i) v.push_back(i); - sort(begin(v), end(v), [](int a, int b) { return G[a].size() < G[b].size(); }); - - ll ans = 0; - for (auto& u : v) { - vis[u] = 1; - for (auto& v : G[u]) oc[v] = 1; - vi tmp; - for (auto& v : G[u]) { - if (vis[v]) tmp.pb(v); - } - for (auto& v : tmp) { - for (auto& w : G[v]) ans += oc[w]; - } - for (auto& v : G[u]) oc[v] = 0; - } - cout << ans / 3 << '\n'; -} \ No newline at end of file diff --git a/2020/day2/meet.cpp b/2020/day2/meet.cpp deleted file mode 100644 index 4f37159..0000000 --- a/2020/day2/meet.cpp +++ /dev/null @@ -1,32 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -typedef long long ll; -typedef pair ii; - -int a[303]; -vector G[303]; - -void dfs(int u, int p) { - for (auto& v : G[u]) { - dfs(v, u); - - } - - -} - -int main() { - int N; - cin >> N; - for (int i = 0; i < N; ++i) cin >> a[i]; - for (int i = 1; i < N; ++i) { - int u, v; - cin >> u >> v; - G[u].push_back(v), G[v].push_back(u); - } - - dfs(1, 0); - -} \ No newline at end of file diff --git a/2020/day2/meet_slow.cpp b/2020/day2/meet_slow.cpp deleted file mode 100644 index 99d8b21..0000000 --- a/2020/day2/meet_slow.cpp +++ /dev/null @@ -1,97 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -typedef long long ll; -typedef pair ii; - -int a[303], cost[303][303], dp[303][303]; -vector G[303]; - -int main() { - int N; - cin >> N; - for (int i = 0; i < N; ++i) cin >> a[i]; - for (int i = 1; i < N; ++i) { - int u, v; - cin >> u >> v; - --u, --v; - G[u].push_back(v), G[v].push_back(u); - } - if (N <= 20) { - int ans[22]; - fill(ans, ans + N + 1, 1e9); - for (int m = 1; m < (1 << N); ++m) { - int dist[22]; - queue q; - for (int i = 0; i < N; ++i) { - if (1 & (m >> i)) { - dist[i] = 0; - q.emplace(i, 0); - } - else dist[i] = 1e9; - } - while (!q.empty()) { - int u = q.front().f, d = q.front().s; - q.pop(); - if (d > dist[u]) continue; - for (auto& v : G[u]) { - if (d + 1 < dist[v]) { - dist[v] = d + 1; - q.emplace(v, dist[v]); - } - } - } - int sum = 0; - for (int i = 0; i < N; ++i) sum += a[i] * dist[i]; - ans[__builtin_popcount(m)] = min(sum, ans[__builtin_popcount(m)]); - } - for (int i = 1; i <= N; ++i) cout << ans[i] << ' '; - } - else { - int s; - for (int i = 0; i < N; ++i) { - if (G[i].size() == 1) s = i; - } - vector v(N); - int p = -1; - for (int i = 0; i < N; ++i) { - v[i] = a[s]; - if (i < N - 1) { - int tmp = s; - s = (G[s][0] == p ? G[s][1] : G[s][0]); - p = tmp; - } - } - memset(cost, '?', sizeof cost); - for (int i = 0; i < N; ++i) { - for (int j = i; j < N; ++j) { - int cnt = 0, sum = 0; - for (int k = i; k <= j; ++k) { - cnt += v[k]; - sum += (k - i) * v[k]; - } - cnt -= v[i]; - cost[i][j] = min(sum, cost[i][j]); - int tmp = 0; - for (int k = i + 1; k <= j; ++k) { - tmp += v[k - 1]; - sum -= cnt; - sum += tmp; - cnt -= v[k]; - cost[i][j] = min(sum, cost[i][j]); - } - } - } - memset(dp, '?', sizeof dp); - dp[0][0] = 0; - for (int i = 0; i < N; ++i) { - for (int j = 0; j <= i; ++j) { - for (int k = 0; k <= i; ++k) { - dp[i + 1][j + 1] = min(dp[k][j] + cost[k][i], dp[i + 1][j + 1]); - } - } - } - for (int i = 1; i <= N; ++i) cout << dp[N][i] << ' '; - } -} \ No newline at end of file diff --git a/2020/day2/reopen.cpp b/2020/day2/reopen.cpp deleted file mode 100644 index 0d64e84..0000000 --- a/2020/day2/reopen.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -typedef long long ll; -typedef pair ii; - -int main() { - ios_base::sync_with_stdio(0), cin.tie(0); - - int n, a, b; - string r; - cin >> n >> a >> b >> r; - - if (r == "1/2") { - for (int i = 0; i < n / 2; ++i) cout << b * i << ' ' << 0 << '\n'; - for (int i = n / 2; i < n; ++i) cout << b * i + a << ' ' << 0 << '\n'; - } - else { - int d = a * (b + 1) / 2 % b; - for (int i = 0; i < n; ++i) { - int x = d + (i / 4) * b, y = 0; - if (i % 2 == 1) swap(x, y); - if (i % 4 == 2) x = -x; - if (i % 4 == 3) y = -y; - cout << x + 500000000 << ' ' << y + 500000000 << '\n'; - } - } -} \ No newline at end of file diff --git a/2020/day2/triangles.cpp b/2020/day2/triangles.cpp deleted file mode 100644 index c30cbc7..0000000 --- a/2020/day2/triangles.cpp +++ /dev/null @@ -1,45 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -typedef long long ll; -typedef pair ii; -constexpr ll MOD = 1e9+7; - -ii P[2002]; - -int main() { - ifstream cin("triangles.in"); - ofstream cout("triangles.out"); - - int N; - cin >> N; - for (int i = 0; i < N; ++i) cin >> P[i].f >> P[i].s; - sort(P, P + N); - - ll ans = 0; - for (int i = 0; i < N; ++i) { - ii p = P[i]; - vector l, r; - for (int j = 0; j < i; ++j) l.push_back(P[j]); - for (int j = i + 1; j < N; ++j) r.push_back(P[j]); - sort(l.begin(), l.end(), [&p](const ii& a, const ii& b) { - int x = (a.f - p.f) * (b.s - p.s) - (a.s - p.s) * (b.f - p.f); - if (x == 0) return (a.f - p.f) * (a.f - p.f) + (a.s - p.s) * (a.s - p.s) < (b.f - p.f) * (b.f - p.f) + (b.s - p.s) * (b.s - p.s); - return x < 0; - }); - sort(r.begin(), r.end(), [&p](const ii& a, const ii& b) { - int x = (a.f - p.f) * (b.s - p.s) - (a.s - p.s) * (b.f - p.f); - if (x == 0) return (a.f - p.f) * (a.f - p.f) + (a.s - p.s) * (a.s - p.s) < (b.f - p.f) * (b.f - p.f) + (b.s - p.s) * (b.s - p.s); - return x < 0; - }); - - for (int j = 0, k = 0; j < i; ++j) { - while (k < N - i - 1 && (l[j].f - p.f) * (r[k].s - p.s) - (l[j].s - p.s) * (r[k].f - p.f) <= 0) ++k; - ans += (ll)(2 * j + N - 2 * i - 2 * k) * (p.s + l[j].s) * (p.f - l[j].f) + MOD * MOD; - ans %= MOD; - } - } - - cout << ans << '\n'; -} \ No newline at end of file diff --git a/2020/day2/triangles_gen.cpp b/2020/day2/triangles_gen.cpp deleted file mode 100644 index fec17ae..0000000 --- a/2020/day2/triangles_gen.cpp +++ /dev/null @@ -1,24 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -typedef pair ii; - -int M = 10000; - -int main() { - ofstream cout("triangles.in"); - - int N = 100; - cout << N << '\n'; - srand(time(0)); - vector v; - for (int i = 0; i < N; ++i) { - ii x; - do { - x.f = (rand() % (2 * M)) - M, x.s = (rand() % (2 * M)) - M; - } while (find(v.begin(), v.end(), x) != v.end()); - v.push_back(x); - cout << x.f << ' ' << x.s << '\n'; - } -} \ No newline at end of file diff --git a/2020/day3/treemst.cpp b/2020/day3/treemst.cpp deleted file mode 100644 index ad4bae2..0000000 --- a/2020/day3/treemst.cpp +++ /dev/null @@ -1,44 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ll = long long; -using ii = pair; - -int h[100001], p[100001], d[100001], l[100001], r[100001]; -ll ans; -set S; -vector G[100001]; - -void dfs(int u, int p) { - d[u] = d[p] + 1; - l[u] = r[u] = 2e9; - S.emplace(h[u], u); - for (auto& v : G[u]) { - if (v != p) dfs(v, u); - } - S.erase(ii(h[u], u)); - if (u == 1) return; - - auto it = S.lower_bound(ii(h[u], u)); - if (it != begin(S)) l[u] = min(h[u] - prev(it)->f, l[u]); - if (it != end(S)) r[u] = min(it->f - h[u], r[u]); - ans += min(l[u], r[u]); - int m = max(l[u], r[u]); - if (m < 2e9) { - int y = prev(it)->s, z = it->s; - d[y] > d[z] ? r[y] = min(m, r[y]) : l[z] = min(m, l[z]); - } -} - -int main() { - int N; - cin >> N; - for (int i = 1; i <= N; ++i) cin >> h[i]; - for (int i = 2; i <= N; ++i) { - cin >> p[i]; - G[p[i]].push_back(i); - } - dfs(1, 0); - cout << ans << '\n'; -} \ No newline at end of file diff --git a/2020/day4/extra.cpp b/2020/day4/extra.cpp deleted file mode 100644 index 360fa67..0000000 --- a/2020/day4/extra.cpp +++ /dev/null @@ -1,30 +0,0 @@ -#include -using namespace std; -constexpr int MOD = 1e9+7; - -int lcp[5005][5005], dp[5005][5005]; - -int main() { - string s; - cin >> s; - int n = s.size(); - for (int i = n - 1; i >= 0; --i) { - for (int j = n - 1; j >= i; --j) { - if (s[i] == s[j]) lcp[i][j] = 1 + lcp[i + 1][j + 1]; - } - } - - dp[0][0] = 1; - for (int i = 0; i < n; ++i) { - for (int j = i + 1; j <= n; ++j) { - dp[i][j] += dp[i][j - 1], dp[i][j] %= MOD; - int len = min(lcp[i][j], j - i); - if (i + len >= n || (len < j - i && s[i + len] > s[j + len])) continue; - dp[j][j + len + 1] += dp[i][j], dp[j][j + len + 1] %= MOD; - } - } - - int ans = 0; - for (int i = 0; i < n; ++i) ans += dp[i][n], ans %= MOD; - cout << ans << '\n'; -} \ No newline at end of file diff --git a/2020/day6/cowputing b/2020/day6/cowputing deleted file mode 100644 index f15e67a..0000000 --- a/2020/day6/cowputing +++ /dev/null @@ -1,29 +0,0 @@ -# g++ grader.cc && cp solution output && ./a.out - -# Blank lines and comment lines (start with '#') are allowed - -# TASK 1 -# Your machine is given as lines of rules. Each rule has the form: -# STATE SYMBOL -> NEW_STATE WRITE_SYMBOL ACTION -# STATE can be any string. The Cowputer always starts in state "0". -# SYMBOL can be any alphanumeric character (A-Z,a-z,0-9). -# ACTION is one of L(eft) R(ight) S(tay) H(alt) -# If your program encounters a state it has no rule for, that's WA. -# With these rules, the Cowputer will go left until it finds an 'X' and then halt. -# It won't change the array at all, because on every step it just writes whatever symbol -# was already there. -0 1 -> 0 1 L -# ^"If you are in state 0 and see symbol '1', go to state 0, write a '1' and move left" -# This means that the state stays the same, it writes a one on the current index -# in the array, and moves to index-1 in the array -0 0 -> 0 0 L -# ^"If you are in state 0 and see symbol '0', go to state 0, write a '0' and move left" -0 X -> 0 X H -# ^"If you are in state 0 and see symbol 'X', go to state 0, write an 'X', and halt" - -# TASK 2 -# You should submit all your programs in one file. Programs are separated by '# TASK ' lines. -# You would put your rules for TASK 2 here. -# This submission for TASK 2 just halts immediately. Unfortunately, that does not solve task 2. -0 0 -> 0 0 H -0 1 -> 0 1 H \ No newline at end of file diff --git a/2020/day6/friend.cpp b/2020/day6/friend.cpp deleted file mode 100644 index 6a9fdec..0000000 --- a/2020/day6/friend.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -typedef long long ll; -typedef pair ii; -constexpr ll MOD = 1e9+7; - -int a[100001], b[100001]; -map f, g; - -int main() { - int N; - cin >> N; - f[ii(1, 2)] = 1; - for (int i = 3; i <= N; ++i) { - cin >> a[i] >> b[i]; - f[ii(a[i], i)] = f[ii(b[i], i)] = 1; - } - g = f; - int ans = 0; - for (int i = N; i >= 3; --i) { - ii x(a[i], i), y(b[i], i), z(a[i], b[i]); - ans = (g[x] * f[y] % MOD * f[z] + f[x] * g[y] % MOD * f[z] + f[x] * f[y] % MOD * g[z] + ans) % MOD; - g[z] = (f[x] * g[y] + g[x] * f[y] + g[z]) % MOD; - f[z] = (f[x] * f[y] + f[z]) % MOD; - } - cout << 2 * ans % MOD << '\n'; -} \ No newline at end of file diff --git a/2020/day6/grader.cc b/2020/day6/grader.cc deleted file mode 100644 index b1c32c0..0000000 --- a/2020/day6/grader.cc +++ /dev/null @@ -1,467 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include - -int TRACE = -1; - -using ll = long long; -using namespace std; - -ostream& operator<<(ostream& o, const deque& ARRAY) { - for(int i=0; i(lo,hi)(RNG); -} - -void fassert(bool b, const string& msg) { - if(!b) { - cerr << msg << endl; - cout << "W" << endl; - assert(false); - } -} - -// STATE CHARACTER -> NEW_STATE NEW_CHARACTER {L(EFT),R(IGHT),S(TAY),H(ALT)} -using Cowputer = map>>; -constexpr ll LIMIT = static_cast(1e6); - -set symbols(const Cowputer& M) { - set ans; - for(auto& kv : M) { - for(auto& kv2 : kv.second) { - string new_state; char new_char; char action; - std::tie(new_state, new_char, action) = kv2.second; - ans.insert(kv2.first); - ans.insert(new_char); - } - } - return ans; -} - -struct State { - State(Cowputer m, deque& START, bool trace_) : RULES(m), ARRAY(START), pos(0), state("0"), time(0), tle(false), trace(trace_) { - if(ARRAY.size() == 0) { - ARRAY.push_back('X'); - } - } - deque& ARRAY; - int pos; - string state; - int time; - Cowputer RULES; - bool tle; - - bool trace; - - bool run() { - if(trace) { - cerr << "TRACE: STARTING ARRAY=" << ARRAY << endl; - } - while(!step(trace)) {} - if(trace) { - cerr << "TRACE: ENDING ARRAY=" << ARRAY << endl; - } - return tle; - } - - bool step(bool trace) { - if(time == LIMIT) { - tle = true; - return true; - } - if(trace) { cerr << "TRACE: " << show() << endl; } - fassert(0<=pos && pos ll_to_array(ll n) { - deque ARRAY; - ll tmp = n; - while(tmp > 0) { - ARRAY.push_front(static_cast('0'+(tmp%2))); - tmp /= 2; - } - return ARRAY; -} - -// Trim X off left and right -string read_array(const deque& ARRAY) { - stringstream ans; - ll start = 0; - while(start=0 && ARRAY[end]=='X') { end--; } - for(ll i=start; i<=end; i++) { - ans << ARRAY[i]; - } - return ans.str(); -} - -// Reads the first integer in binary on the array -ll from_binary(const string& S) { - ll ans = 0; - for(ll i=0; i GOAL; - for(ll i=0; i GOAL; - for(ll i=0; i syms = symbols(RULES); - if(syms.size() > 3) { - cerr << "Only 3 characters allowed for task 7" << endl; - } - - deque ARRAY; - State START(RULES,ARRAY,trace); - bool tle = START.run(); - if(tle) { - cerr << "TLE TASK 7" << endl; - return 0; - } - ll score = START.time; - if(trace) { - cerr << "TASK 7: TOOK " << score << " steps" << endl; - } - if(score >= 10000) { - return 5; - } else if(score >= 1000) { - return 4; - } else if(score >= 500) { - return 3; - } else if(score >= 100) { - return 2; - } else if(score >= 20) { - return 1; - } else { - return 0; - } -} - -int main() { - ifstream in; - in.open("output"); - if (!in) { - cerr << "No \"output\" file" << endl; - cout << "W" << endl; - exit(0); - } - using Checker = std::function; - vector TASKS{ - {task1}, - {task2}, - {task3}, - {task4}, - {task5}, - {task6}, - {task7}, - }; - - map MS; - Cowputer RULES; - ll task = -1; - while(!in.eof()) { - string line; - getline(in, line); - string PREFIX = "# TASK"; - if(line.find(PREFIX)==0) { - stringstream ss(line); - if(task != -1) { - fassert(MS.count(task)==0, "Already submitted a machine for task=" + std::to_string(task)); - MS[task] = RULES; - RULES.clear(); - } - string hash; string label; ll new_task; - ss >> hash >> label >> new_task; - fassert(hash == "#", "TASK LINE must start with '# TASK' line="+line); - fassert(label == "TASK", "TASK LINE must start with '# TASK' line="+line); - fassert(1<=new_task && new_task<=TASKS.size(), "Unknown TASK="+std::to_string(new_task)); - task = new_task-1; - } - bool isempty = true; - for(ll i=0; i", "BAD ARROW line="+line+" arrow=" + arrow); - assert(arrow == "->"); - if(RULES.count(state)==0) { - RULES[state] = map>{}; - } - fassert(set{'L', 'R', 'S', 'H'}.count(action)==1, "Action must be one of L(EFT) R(IGHT) S(TAY) H(ALT) got="+std::to_string(action)); - fassert(RULES[state].count(seen)==0, "Duplicate rule detected state="+state+" char="+std::string(1, seen)); - RULES[state][seen] = make_tuple(new_state, write, action); - } - if(task != -1) { - fassert(MS.count(task)==0, "Already submitted a machine for task=" + std::to_string(task)); - MS[task] = RULES; - } - - ll score = 0; - for(auto& kv : MS) { - ll task; Cowputer M; - std::tie(task, M) = kv; - if(M.size() > 1000) { - cerr << "You used more than 1000 internal states for task=" << task << endl; - continue; - } - Checker check = TASKS[task]; - ll points = check(M, TRACE==task+1); - score += points; - cerr << "Task " << (task+1) << ": " << points << endl; - } - cout << score << endl; -} diff --git a/2020/day6/milkvisits.cpp b/2020/day6/milkvisits.cpp deleted file mode 100644 index d18c457..0000000 --- a/2020/day6/milkvisits.cpp +++ /dev/null @@ -1,61 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -typedef pair ii; - -vector G[100001]; - -vector path16[17][17]; -ii ans16[17]; -void dfs16(int r, int u, int p) { - path16[r][u] = path16[r][p], path16[r][u].push_back(u); - for (auto& v : G[u]) if (v != p) dfs16(r, v, u); -} - -int main() { - int N, M; - cin >> N >> M; - for (int i = 1; i < N; ++i) { - int a, b; - cin >> a >> b; - G[a].push_back(b), G[b].push_back(a); - } - - if (N <= 16) { - pair Q[17]; - fill(ans16 + 1, ans16 + N + 1, ii(-1, 0)); - for (int i = 0; i < M; ++i) cin >> Q[i].f.f >> Q[i].f.s >> Q[i].s; - for (int u = 1; u <= N; ++u) dfs16(u, u, 0); - for (int y = 0; y < (1 << N); ++y) { - int m = 2 * y; - bool pass = 1; - for (int i = 0; i < M && pass; ++i) { - bool flag = 0; - for (auto& x : path16[Q[i].f.f][Q[i].f.s]) { - if ((1 & (m >> x)) == (Q[i].s == 'G')) flag = 1; - } - if (!flag) pass = 0; - } - if (pass) { - for (int i = 1; i <= N; ++i) { - if (ans16[i].f == -1) ans16[i].f = (1 & (m >> i)); - else if ((1 & (m >> i)) != ans16[i].f) ans16[i].s = 1; - ans16[i].f = (1 & (m >> i)); - } - } - } - if (ans16[1].f == -1) { - cout << "NO\n"; - } - else { - cout << "YES\n"; - for (int i = 1; i <= N; ++i) cout << (ans16[i].f ? 'G' : 'H') << (ans16[i].s ? '?' : '!') << '\n'; - } - } - else { - - - - } -} \ No newline at end of file diff --git a/2020/practice/babynames.cpp b/2020/practice/babynames.cpp deleted file mode 100644 index 42a5629..0000000 --- a/2020/practice/babynames.cpp +++ /dev/null @@ -1,93 +0,0 @@ -#include -using namespace std; -typedef long long ll; -constexpr int M1 = 8191, M2 = 1e9+7; - -string s[10001]; -vector h[10001]; -int r[10001], hs[2][10001]; - -inline void print(int x, int d) { - cout << "MOO "; - for (int i = 0; i < d; ++i) cout << (1 & (x >> i)); - cout << endl; -} - -inline int read(int d) { - int x = 0; - for (int i = 0; i < 16; ++i) { - char c; - cin >> c; - if (c == '1') x |= (1 << i); - } - return x; -} - -inline int hsh(string& s, int m) { - ll x = 0; - for (auto& c : s) x *= 31, x += c - 'a', x %= m; - return x; -} - -int main() { - ofstream debug("debug"); - - int c, n[2]; - cin >> c >> n[0]; - for (int i = 0; i < n[0]; ++i) { - cin >> s[i]; - hs[0][i] = hsh(s[i], M1); - hs[1][i] = hsh(s[i], M2); - } - if (c) { - print(n[0], 16); - debug << 1 << ' ' << n[1]; - n[1] = read(16); - - for (int i = 0; i < n[0]; ++i) { - print(hs[0][i], 13); - bool b; - cin >> b; - if (b == 1) { - print(hs[1][i], 30); - cin >> b; - if (b == 1) { - cout << "RETURN " << s[i] << endl; - return 0; - } - } - } - } - else { - n[1] = read(16); - debug << 0 << ' ' << n[1]; - print(n[0], 16); - - for (int i = 0; i < n[0]; ++i) { - h[hs[0][i]].push_back(i); - } - for (int i = 0; i < n[1]; ++i) { - r[i] = read(13); - if (h[r[i]].empty()) { - print(0, 1); - } - else { - print(1, 1); - int x; - x = read(30); - bool ans = 0; - for (auto& y : h[r[i]]) { - if (hs[1][y] == x) { - ans = 1; - cout << "RETURN " << s[y] << endl; - print(1, 1); - return 0; - } - } - if (!ans) { - print(0, 1); - } - } - } - } -} \ No newline at end of file diff --git a/2020/practice/cowforce.cpp b/2020/practice/cowforce.cpp deleted file mode 100644 index 71ef087..0000000 --- a/2020/practice/cowforce.cpp +++ /dev/null @@ -1,42 +0,0 @@ -#include -using namespace std; -typedef long long ll; - -ll t[303][303], dp[303][303][303]; - -int main() { - int N, M, K; - cin >> N >> M >> K; - for (int i = 0; i < N; ++i) { - for (int j = 0; j < M; ++j) cin >> t[i][j]; - } - - memset(dp, '?', sizeof dp); - memset(dp[0], 0, sizeof dp[0]); - for (int i = 0; i < N; ++i) { - for (int j = 0; j < M; ++j) { - for (int k = 0; k < M; ++k) { - if (j != k) dp[i + 1][j][k] = min(dp[i][j][k] + t[i][j] + t[i][k], dp[i + 1][j][k]); - } - } - for (int j = 0; j < M; ++j) { - for (int k = 0; k < M; ++k) { - if (j > 0 && j - 1 != k) dp[i + 1][j][k] = min(dp[i + 1][j - 1][k] + K, dp[i + 1][j][k]); - if (k > 0 && j != k - 1) dp[i + 1][j][k] = min(dp[i + 1][j][k - 1] + K, dp[i + 1][j][k]); - } - } - for (int j = M - 1; j >= 0; --j) { - for (int k = M - 1; k >= 0; --k) { - if (j < M - 1 && j + 1 != k) dp[i + 1][j][k] = min(dp[i + 1][j + 1][k] + K, dp[i + 1][j][k]); - if (k < M - 1 && j != k + 1) dp[i + 1][j][k] = min(dp[i + 1][j][k + 1] + K, dp[i + 1][j][k]); - } - } - } - ll ans = 1e18; - for (int i = 0; i < M; ++i) { - for (int j = 0; j < M; ++j) { - if (i != j) ans = min(dp[N][i][j], ans); - } - } - cout << ans << '\n'; -} \ No newline at end of file diff --git a/2020/practice/data b/2020/practice/data deleted file mode 100644 index 85ab75d..0000000 --- a/2020/practice/data +++ /dev/null @@ -1,10 +0,0 @@ -0 3 -candice -mark -john -1 5 -paul -qq -tjhance -candice -bob \ No newline at end of file diff --git a/2020/practice/debug b/2020/practice/debug deleted file mode 100644 index e69de29..0000000 diff --git a/2020/practice/guess.cpp b/2020/practice/guess.cpp deleted file mode 100644 index a9ff0e0..0000000 --- a/2020/practice/guess.cpp +++ /dev/null @@ -1,6 +0,0 @@ -#include -using namespace std; - -int main() { - cout << 42 << '\n'; -} \ No newline at end of file diff --git a/2020/practice/test_grader.cpp b/2020/practice/test_grader.cpp deleted file mode 100644 index b7d9162..0000000 --- a/2020/practice/test_grader.cpp +++ /dev/null @@ -1,264 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include -#include - -#include -#include -#include -#include -#include -#include - -using namespace std; - -#define L 1000000000000000LL - -#define RETRY(x) ({ \ - int _r = (x); \ - while (_r == -1 && errno == EINTR) { \ - _r = (x); \ - } \ - _r; \ -}) - -template -string to_string(const T& x) { - ostringstream sout; - sout << x; - return sout.str(); -} - -pid_t start_instance(int argc, char** argv, int* pipes) { - int pipe_a[2]; - int pipe_b[2]; - if (pipe(pipe_a) == -1 || pipe(pipe_b) == -1) { - perror("pipe"); - return -1; - } - - pid_t pid = fork(); - if (pid == -1) { - perror("fork"); - return -1; - } else if (pid == 0) { - close(0); - close(1); - dup2(pipe_b[0], 0); - dup2(pipe_a[1], 1); - close(pipe_a[0]); - close(pipe_a[1]); - close(pipe_b[0]); - close(pipe_b[1]); - - char** args = (char**)malloc(sizeof(char*) * (argc + 2)); - args[0] = strdup("stdbuf"); - args[1] = strdup("-oL"); - for (int i = 1; i < argc; i++) { - args[1 + i] = argv[i]; - } - args[argc + 1] = NULL; - execvp("stdbuf", args); - perror("execvp"); - exit(1); - } - - close(pipe_a[1]); - close(pipe_b[0]); - pipes[0] = pipe_a[0]; - pipes[1] = pipe_b[1]; - return pid; -} - -int main(int argc, char** argv) { - if (argc == 1) { - cout << "USAGE:" << endl; - cout << argv[0] << " ./test_program" << endl; - return 0; - } - if (signal(SIGPIPE, SIG_IGN)) { - perror("signal"); - return 1; - } - - int nfds = 1; - char buf[1024]; - int rfd[2]; - int wfd[2]; - pid_t pids[2]; - bool alive[2] = {true, true}; - bool returned[2] = {false, false}; - string return_val[2] = {"", ""}; - for (int i = 0; i < 2; i++) { - int pipe_tmp[2]; - pids[i] = start_instance(argc, argv, pipe_tmp); - if (pids[i] == -1) { - cerr << "failed to start solution program" << endl; - return 1; - } - - rfd[i] = pipe_tmp[0]; - wfd[i] = pipe_tmp[1]; - nfds = max(nfds, max(rfd[i], wfd[i])) + 1; - } - - int ign; - vector names[2]; - string in[2]; - string out[2]; - - set names_set[2]; - for (int i = 0; i < 2; i++) { - int sz; - cin >> ign >> sz; - names[i].resize(sz); - - out[i] = to_string(i) + " " + to_string(sz) + "\n"; - for (int j = 0; j < sz; j++) { - cin >> names[i][j]; - assert(0 <= names[i][j].size() && names[i][j].size() <= 100); - for(int k = 0; k < names[i][j].size(); k++){ - assert('a' <= names[i][j][k] && names[i][j][k] <= 'z'); - } - - if (j) out[i] += ' '; - out[i] += names[i][j]; - } - out[i] += '\n'; - - names_set[i] = set(names[i].begin(), names[i].end()); - assert(names_set[i].size() == names[i].size()); - } - vector intersection; - for(auto it = names_set[0].begin(); it != names_set[0].end(); ++it){ - if(names_set[1].count(*it)){ - cerr << "COMMON NAME: " << *it << endl; - intersection.push_back(*it); - } - } - assert(intersection.size() == 1); - string answer_val = intersection[0]; - - int total_bits = 0; - for (; alive[0] || alive[1]; ) { - fd_set rfds; - fd_set wfds; - FD_ZERO(&rfds); - FD_ZERO(&wfds); - for (int i = 0; i < 2; i++) { - if (!alive[i]) { - continue; - } - FD_SET(rfd[i], &rfds); - if (out[i].size()) { - FD_SET(wfd[i], &wfds); - } - } - - if (RETRY(select(nfds, &rfds, &wfds, NULL, NULL)) == -1) { - perror("select"); - cout << "E" << endl; - return 0; - } - - for (int i = 0; i < 2; i++) { - if (FD_ISSET(rfd[i], &rfds)) { - ssize_t amt = RETRY(read(rfd[i], buf, sizeof(buf))); - if (amt <= 0) { - close(rfd[i]); - close(wfd[i]); - alive[i] = false; - cerr << "Cow " << i << " communication closed" << endl; - continue; - } - in[i] += string(buf, amt); - cerr << "COW[" << i << "]: " << string(buf, amt) << endl; - - for(;;) { - int nline = in[i].find('\n'); - if (nline == -1) { - break; - } - string line = in[i].substr(0, nline); - in[i] = in[i].substr(nline + 1); - - istringstream sin(line); - string cmd; sin >> cmd; - if (cmd == "MOO") { - string data; sin >> data; - for (int j = 0; j < data.size(); j++) { - if (data[j] != '0' && data[j] != '1') { - cerr << "Cow " << i << " tried to moo non-binary" << endl; - return 1; - } - } - out[1 - i] += data + "\n"; - total_bits += data.size(); - } else if (cmd == "RETURN") { - string val; - sin >> val; - if (returned[i]) { - cerr << "Same cow cannot return twice" << endl; - return 1; - } else { - returned[i] = true; - return_val[i] = val; - } - } else { - cerr << "Unknown command from cow " << i << endl; - return 1; - } - } - if (in[i].size() > 7000000) { - cerr << "Line too long from cow " << i << endl; - return 1; - } - } - if (FD_ISSET(wfd[i], &wfds)) { - // cerr << "TO COW[" << i << "]: " << out[i] << endl; - ssize_t amt = RETRY(write(wfd[i], out[i].data(), out[i].size())); - if (amt <= 0) { - close(rfd[i]); - close(wfd[i]); - alive[i] = false; - cerr << "Cow " << i << " communication closed" << endl; - continue; - } else { - out[i] = out[i].substr(amt); - } - } - } - } - for (int i = 0; i < 2; i++) { - int status = 0; - if (RETRY(waitpid(pids[i], &status, 0)) == -1) { - perror("waitpid"); - return 1; - } - if (WIFSIGNALED(status)) { - cerr << "Cow " << i << " crashed" << endl; - return 1; - } - } - - for (int i = 0; i < 2; i++) { - if (returned[i] && return_val[i] != answer_val) { - cerr << "Cow " << i << " returned the wrong value" << endl; - return 1; - } - } - if (!returned[0] && !returned[1]) { - cerr << "Neither cow returned a value" << endl; - return 1; - } - - cerr << "Found correct name " << answer_val << " using " << - total_bits << " total bits." << endl; - - return 0; -} -- cgit v1.2.3-70-g09d2