Restructure directories AGAIN so contests from the same season are in the same directory

3 files changed, 192 insertions, 0 deletions

diff --git a/21.5/dec/hilo.cpp b/21.5/dec/hilo.cpp
new file mode 100644
index 0000000..250bf49
--- /dev/null
+++ b/21.5/dec/hilo.cpp
@@ -0,0 +1,35 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+constexpr int MX = 5005, MOD = 1e9+7;
+
+inline ll pw(ll base, ll exp) {
+	ll res = 1;
+	while (exp) {
+		if (exp & 1) (res *= base) %= MOD;
+		exp >>= 1, (base *= base) %= MOD;
+	}
+	return res;
+}
+
+int inv[MX], pre[2][MX], DP[2][MX][MX];
+
+int main() {
+	cin.tie(0)->sync_with_stdio(0);
+	int N, x; cin >> N >> x;
+	for (int i = 1; i <= N; ++i) inv[i] = pw(i, MOD-2);
+	for (int i = 0; i <= x; ++i) {
+		for (int j = 0; j <= N-x; ++j) {
+			DP[0][i][j] = (ll)(pre[0][i] + pre[1][j]) * inv[i + j] % MOD;
+			DP[1][i][j] = (ll)(pre[0][i] + pre[1][j] + i) * inv[i + j] % MOD;
+			(pre[0][i] += DP[1][i][j]) %= MOD;
+			(pre[1][j] += DP[0][i][j]) %= MOD;
+		}
+	}
+	ll ans = DP[0][x][N-x];
+	for (int i = 1; i <= N; ++i) (ans *= i) %= MOD;
+	cout << ans;
+}
diff --git a/21.5/dec/tickets.cpp b/21.5/dec/tickets.cpp
new file mode 100644
index 0000000..cd6e006
--- /dev/null
+++ b/21.5/dec/tickets.cpp
@@ -0,0 +1,79 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+using pl = pair<ll, ll>;
+constexpr int MX = 1e5+5;
+
+int N, K;
+
+struct ticket_t {
+	int c, p, a, b;
+} T[MX];
+
+struct seg_tree {
+	int seg[4*MX];
+	inline int pull(const int & a, const int & b) { return max(a, b); }
+	void build(int l = 0, int r = MX-1, int n = 1) {
+		if (l == r) { seg[n] = T[l].b; return; }
+		int m = l+r>>1;
+		build(l, m, n<<1), build(m+1, r, n<<1|1);
+		seg[n] = pull(seg[n<<1], seg[n<<1|1]);
+	}
+	void remove(vector<int> & vc, int x, int l = 0, int r = MX-1, int n = 1) {
+		if (l >= K || T[l].a > x || seg[n] < x) return;
+		if (l == r) {
+			seg[n] = -1, vc.push_back(l);
+		}
+		else {
+			int m = l+r>>1;
+			remove(vc, x, l, m, n<<1), remove(vc, x, m+1, r, n<<1|1);
+			seg[n] = pull(seg[n<<1], seg[n<<1|1]);
+		}
+	}
+};
+
+void dijkstra(vector<ll> & dist) {
+	priority_queue<pl, vector<pl>, greater<>> pq;
+	for (int i = N; i < N+K; ++i)
+		dist[T[i-N].c] = min(dist[i]+T[i-N].p, dist[T[i-N].c]);
+	for (int i = 0; i < N; ++i) if (dist[i] < 1e18)
+		pq.emplace(dist[i], i);
+	seg_tree seg;
+	seg.build();
+	while (pq.size()) {
+		ll d = pq.top().f, u = pq.top().s;
+		pq.pop();
+		if (d > dist[u]) continue;
+		vector<int> vc;
+		seg.remove(vc, u);
+		for (int v : vc) {
+			if (dist[v+N] > d) {
+				dist[v+N] = d;
+				if (dist[T[v].c] > d+T[v].p)
+					dist[T[v].c] = d+T[v].p,
+					pq.emplace(dist[T[v].c], T[v].c);
+			}
+		}
+	}
+}
+
+int main() {
+	cin.tie(0)->sync_with_stdio(0);
+	cin >> N >> K;
+	for (int i = 0; i < K; ++i) {
+		cin >> T[i].c >> T[i].p >> T[i].a >> T[i].b;
+		--T[i].c, --T[i].a, --T[i].b;
+	}
+	sort(T, T+K, [](auto & a, auto & b) { return a.a < b.a; });
+	vector<ll> L(N+K, 1e18), R(N+K, 1e18), D(N+K);
+	L[0] = R[N-1] = 0;
+	dijkstra(L), dijkstra(R);
+	for (int i = 0; i < N+K; ++i) D[i] = L[i]+R[i];
+	dijkstra(D);
+	for (int i = 0; i < N; ++i)
+		cout << (D[i] < 1e18 ? D[i] : -1) << '\n';
+}
+
diff --git a/21.5/feb/plat/sleeping.cpp b/21.5/feb/plat/sleeping.cpp
new file mode 100644
index 0000000..4f1f5c8
--- /dev/null
+++ b/21.5/feb/plat/sleeping.cpp
@@ -0,0 +1,78 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+const int MX = 1e5+5;
+
+ll A[MX], P[MX], q[MX];
+int f[103680];
+vector<pair<ll, int>> pr;
+
+int num_factors() {
+	int ret = 1;
+	for (auto & p : pr) ret *= p.s+1;
+	return ret;
+}
+
+int & freq(ll x) {
+	ll code = 0;
+	for (auto & p : pr) {
+		int cnt = 0;
+		while (x%p.f == 0) x/= p.f, ++cnt;
+		code = (p.s+1)*code + min(p.s, cnt);
+	}
+	return f[code];
+}
+
+int main() {
+	cin.tie(0)->sync_with_stdio(0);
+	int N; cin >> N;
+	for (int i = 0; i < N; ++i) cin >> A[i];
+	partial_sum(A, A+N, P);
+	ll sum = P[N-1];
+	for (int p = 2; p < 1e6; ++p) {
+		if (sum%p == 0) {
+			int cnt = 0;
+			while (sum%p == 0) sum /= p, ++cnt;
+			pr.emplace_back(p, cnt);
+		}
+	}
+	for (int i = 0; i < N; ++i) {
+		ll tmp = gcd(P[i], sum);
+		if (tmp != 1 && tmp != sum) {
+			if (tmp > sum/tmp) tmp = sum/tmp;
+			if (tmp*tmp == sum) pr.emplace_back(tmp, 2);
+			else pr.emplace_back(tmp, 1), pr.emplace_back(sum/tmp, 1);
+			sum = 1;
+		}
+	}
+	int Q; cin >> Q;
+	for (int i = 0; i < Q; ++i) {
+		cin >> q[i];
+		ll tmp = q[i];
+		if (sum%tmp == 0 && tmp != 1 && tmp != sum) {
+			if (tmp > sum/tmp) tmp = sum/tmp;
+			if (tmp*tmp == sum) pr.emplace_back(tmp, 2);
+			else pr.emplace_back(tmp, 1), pr.emplace_back(sum/tmp, 1);
+			sum = 1;
+		}
+	}
+	if (sum > 1) pr.emplace_back(sum, 1);
+	for (int i = 0; i < N; ++i) ++freq(P[i]);
+	int block = 1;
+	for (int i = pr.size()-1; i >= 0; --i) {
+		for (int code = num_factors()-1; code >= 0; --code)
+			if (code/block%(pr[i].s+1)!=0) f[code-block] += f[code];
+		block *= pr[i].s+1;
+	}
+	for (int i = 0; i < Q; ++i) {
+		if (P[N-1]%q[i]) cout << -1 << '\n';
+		else {
+			ll ans = N+P[N-1]/q[i];
+			ans -= freq(q[i])*2;
+			cout << ans << '\n';
+		}
+	}
+}