Restructured directoriesHEADmaster

7 files changed, 191 insertions, 0 deletions

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 <bits/stdc++.h>
+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 <bits/stdc++.h>
+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 <bits/stdc++.h>
+#define f first
+#define s second
+#define eb emplace_back
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+constexpr int MAXN = 100001;
+constexpr ll INF = 1e9;
+
+int N, Q, H[MAXN];
+bitset<MAXN> ans;
+vector<ii> G[3 * MAXN];
+unordered_map<ll, int> 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 <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ii = pair<int, int>;
+
+vector<ii> 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<int> 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 <bits/stdc++.h>
+using namespace std;
+constexpr int MAXN = 100001;
+
+int c[MAXN];
+vector<int> G[MAXN];
+
+int cnt, scc_num, scc[MAXN], in[MAXN], low[MAXN];
+stack<int> s;
+bitset<MAXN> 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