diff options
| author | Yuqian Yang <crupest@crupest.life> | 2025-02-28 23:13:39 +0800 |
|---|---|---|
| committer | Yuqian Yang <crupest@crupest.life> | 2025-02-28 23:13:39 +0800 |
| commit | dc1f0c4c0096013799416664894c5194dc7e1f52 (patch) | |
| tree | 2f5d235f778cd720f4c39ec3e56b77ba6d99f375 /store/works/solutions/acwing | |
| parent | 7299d424d90b1effb6db69e3476ddd5af72eeba4 (diff) | |
| download | crupest-dc1f0c4c0096013799416664894c5194dc7e1f52.tar.gz crupest-dc1f0c4c0096013799416664894c5194dc7e1f52.tar.bz2 crupest-dc1f0c4c0096013799416664894c5194dc7e1f52.zip | |
chore(store): move everything to store.
Diffstat (limited to 'store/works/solutions/acwing')
39 files changed, 1699 insertions, 0 deletions
diff --git a/store/works/solutions/acwing/1204.cpp b/store/works/solutions/acwing/1204.cpp new file mode 100644 index 0000000..e3e5395 --- /dev/null +++ b/store/works/solutions/acwing/1204.cpp @@ -0,0 +1,31 @@ +#include <ios>
+#include <iostream>
+#include <set>
+
+int main() {
+ std::ios_base::sync_with_stdio(false);
+
+ int repeat;
+
+ int n;
+ std::cin >> n;
+
+ std::set<int> ids;
+
+ while (std::cin >> n) {
+ auto result = ids.insert(n);
+ if (!result.second)
+ repeat = n;
+ }
+
+ auto iter = ids.cbegin();
+
+ int last = *iter++;
+
+ while (++last == *iter++)
+ ;
+
+ std::cout << last << ' ' << repeat;
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1208.cpp b/store/works/solutions/acwing/1208.cpp new file mode 100644 index 0000000..84f60f1 --- /dev/null +++ b/store/works/solutions/acwing/1208.cpp @@ -0,0 +1,24 @@ +#include <iostream>
+#include <string>
+
+inline void toggle(char &c) { c = c == '*' ? 'o' : '*'; }
+
+int main() {
+ std::string original, expected;
+ std::cin >> original >> expected;
+
+ int size = original.size();
+
+ int count = 0;
+
+ for (int i = 0; i < size - 1; i++) {
+ if (original[i] != expected[i]) {
+ count++;
+ toggle(original[i + 1]);
+ }
+ }
+
+ std::cout << count;
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1209.cpp b/store/works/solutions/acwing/1209.cpp new file mode 100644 index 0000000..3f3ff7a --- /dev/null +++ b/store/works/solutions/acwing/1209.cpp @@ -0,0 +1,48 @@ +#include <array>
+#include <iostream>
+#include <vector>
+
+int number;
+int count = 0;
+std::array<bool, 10> used{false};
+std::array<int, 9> current;
+
+int calc(int start, int end) {
+ int n = 0;
+ for (int i = start; i < end; i++) {
+ n *= 10;
+ n += current[i];
+ }
+ return n;
+}
+
+void dfs(int n) {
+ if (n == 9) {
+ for (int i = 1; i <= 7; i++)
+ for (int j = i + 1; j <= 8; j++) {
+ int a = calc(0, i);
+ int b = calc(i, j);
+ int c = calc(j, 9);
+ if ((number - a) * b == c) {
+ count++;
+ }
+ }
+ return;
+ }
+
+ for (int i = 1; i <= 9; i++) {
+ if (!used[i]) {
+ used[i] = true;
+ current[n] = i;
+ dfs(n + 1);
+ used[i] = false;
+ }
+ }
+}
+
+int main() {
+ std::cin >> number;
+ dfs(0);
+ std::cout << count;
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1210.cpp b/store/works/solutions/acwing/1210.cpp new file mode 100644 index 0000000..4c9c0ba --- /dev/null +++ b/store/works/solutions/acwing/1210.cpp @@ -0,0 +1,37 @@ +#include <iostream>
+
+int N;
+int seq[10000];
+
+int main() {
+ std::cin >> N;
+ for (int i = 0; i < N; i++) {
+ std::cin >> seq[i];
+ }
+
+ int count = N;
+
+ for (int start = 0; start < N; start++) {
+ int min = seq[start], max = seq[start];
+
+ for (int end = start + 1; end < N; end++) {
+ int current = seq[end];
+
+ if (current > max) {
+ max = current;
+ }
+
+ if (current < min) {
+ min = current;
+ }
+
+ if (max - min == end - start) {
+ count++;
+ }
+ }
+ }
+
+ std::cout << count;
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1211.cpp b/store/works/solutions/acwing/1211.cpp new file mode 100644 index 0000000..18c564e --- /dev/null +++ b/store/works/solutions/acwing/1211.cpp @@ -0,0 +1,38 @@ +#include <cmath>
+#include <iostream>
+
+int main() {
+ std::ios_base::sync_with_stdio(false);
+
+ int n;
+ std::cin >> n;
+
+ int fever_ant;
+ std::cin >> fever_ant;
+
+ int fever_position = std::abs(fever_ant);
+
+ int left = 0, right = 0;
+
+ for (int i = 1; i < n; i++) {
+ int ant;
+ std::cin >> ant;
+ int position = std::abs(ant);
+ if (position < fever_position && ant > 0) {
+ left++;
+ }
+ if (position > fever_position && ant < 0) {
+ right++;
+ }
+ }
+
+ if (fever_ant < 0 && left == 0) {
+ std::cout << 1;
+ } else if (fever_ant > 0 && right == 0) {
+ std::cout << 1;
+ } else {
+ std::cout << left + right + 1;
+ }
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1212.cpp b/store/works/solutions/acwing/1212.cpp new file mode 100644 index 0000000..e60e993 --- /dev/null +++ b/store/works/solutions/acwing/1212.cpp @@ -0,0 +1,46 @@ +#include <iostream>
+
+int n, m, k;
+int v[51][51];
+int f[51][51][14][14]; // row col count max
+const int MOD = 1000000007;
+
+int main() {
+ std::ios_base::sync_with_stdio(false);
+ std::cin >> n >> m >> k;
+
+ for (int i = 1; i <= n; i++)
+ for (int j = 1; j <= m; j++) {
+ std::cin >> v[i][j];
+ v[i][j]++;
+ }
+
+ f[1][1][0][0] = 1;
+ f[1][1][1][v[1][1]] = 1;
+
+ for (int i = 1; i <= n; i++) {
+ for (int j = 1; j <= m; j++) {
+ for (int c = 0; c <= k; c++) {
+ for (int m = 0; m <= 13; m++) {
+ f[i][j][c][m] = (f[i][j][c][m] + f[i][j - 1][c][m]) % MOD;
+ f[i][j][c][m] = (f[i][j][c][m] + f[i - 1][j][c][m]) % MOD;
+
+ if (c && v[i][j] == m) {
+ for (int max = 0; max < v[i][j]; max++) {
+ f[i][j][c][m] = (f[i][j][c][m] + f[i][j - 1][c - 1][max]) % MOD;
+ f[i][j][c][m] = (f[i][j][c][m] + f[i - 1][j][c - 1][max]) % MOD;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ int result = 0;
+ for (int i = 1; i <= 13; i++)
+ result = (result + f[n][m][k][i]) % MOD;
+
+ std::cout << result;
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1215.cpp b/store/works/solutions/acwing/1215.cpp new file mode 100644 index 0000000..d6832b3 --- /dev/null +++ b/store/works/solutions/acwing/1215.cpp @@ -0,0 +1,59 @@ +#include <cstring>
+#include <iostream>
+
+const int MAX = 1000010; // Why 1000001 is not ok!?
+
+int n;
+int H[100001];
+int bit[MAX];
+int reverse_pairs[100001];
+
+int lowbit(int x) { return x & -x; }
+
+void add(int x, int y) {
+ for (int i = x; i < MAX; i += lowbit(i)) {
+ bit[i] += y;
+ }
+}
+
+int query(int x) {
+ int result = 0;
+ for (int i = x; i != 0; i -= lowbit(i)) {
+ result += bit[i];
+ }
+ return result;
+}
+
+int main() {
+ std::ios_base::sync_with_stdio(false);
+ std::cin.tie(nullptr);
+
+ std::cin >> n;
+
+ for (int i = 1; i <= n; i++) {
+ std::cin >> H[i];
+ H[i]++;
+ }
+
+ for (int i = 1; i <= n; i++) {
+ add(H[i], 1);
+ reverse_pairs[i] = i - query(H[i]);
+ }
+
+ std::memset(bit, 0, sizeof bit);
+
+ for (int i = n; i >= 1; i--) {
+ add(H[i], 1);
+ reverse_pairs[i] += query(H[i] - 1);
+ }
+
+ long long result = 0;
+
+ for (int i = 1; i <= n; i++) {
+ result += (1LL + reverse_pairs[i]) * reverse_pairs[i] / 2;
+ }
+
+ std::cout << result;
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1216.cpp b/store/works/solutions/acwing/1216.cpp new file mode 100644 index 0000000..61d1848 --- /dev/null +++ b/store/works/solutions/acwing/1216.cpp @@ -0,0 +1,19 @@ +#include <iostream>
+
+int main() {
+ int n;
+ std::cin >> n;
+
+ int result = n;
+
+ while (n >= 3) {
+ int exchange = n / 3;
+ int rest = n % 3;
+ result += exchange;
+ n = exchange + rest;
+ }
+
+ std::cout << result;
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1217.cpp b/store/works/solutions/acwing/1217.cpp new file mode 100644 index 0000000..e729547 --- /dev/null +++ b/store/works/solutions/acwing/1217.cpp @@ -0,0 +1,67 @@ +#include <cstring>
+#include <iostream>
+
+const int MOD = 1e9 + 7;
+
+int n, m;
+bool conflict_matrix[7][7];
+
+long long f[7];
+long long temp[7];
+
+int back(int x) {
+ switch (x) {
+ case 1:
+ return 4;
+ case 2:
+ return 5;
+ case 3:
+ return 6;
+ case 4:
+ return 1;
+ case 5:
+ return 2;
+ case 6:
+ return 3;
+ default:
+ return 0;
+ }
+}
+
+int main() {
+ std::ios_base::sync_with_stdio(false);
+ std::cin.tie(nullptr);
+
+ std::cin >> n >> m;
+
+ for (int i = 0; i < m; i++) {
+ int a, b;
+ std::cin >> a >> b;
+ conflict_matrix[a][b] = true;
+ conflict_matrix[b][a] = true;
+ }
+
+ for (int i = 1; i <= 6; i++)
+ f[i] = 4;
+
+ for (int c = 2; c <= n; c++) {
+ for (int up = 1; up <= 6; up++) {
+ for (int down = 1; down <= 6; down++) {
+ if (!conflict_matrix[back(down)][up]) {
+ temp[up] = (temp[up] + f[down] * 4) % MOD;
+ }
+ }
+ }
+ std::memcpy(f, temp, sizeof f);
+ std::memset(temp, 0, sizeof temp);
+ }
+
+ long long result = 0;
+ for (int i = 1; i <= 6; i++) {
+ result = (result + f[i]) % MOD;
+ }
+
+ std::cout << result;
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1219.cpp b/store/works/solutions/acwing/1219.cpp new file mode 100644 index 0000000..9538e94 --- /dev/null +++ b/store/works/solutions/acwing/1219.cpp @@ -0,0 +1,26 @@ +#include <cmath>
+#include <iostream>
+
+int w, m, n;
+
+int row(int x) { return (x - 1) / w; }
+
+int col(int x, int r) {
+ int result = (x - 1) % w;
+ if (r % 2) {
+ result = w - 1 - result;
+ }
+ return result;
+}
+
+int main() {
+ std::cin >> w >> m >> n;
+ int m_r = row(m);
+ int m_c = col(m, m_r);
+ int n_r = row(n);
+ int n_c = col(n, n_r);
+
+ std::cout << std::abs(m_r - n_r) + std::abs(m_c - n_c);
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1220.cpp b/store/works/solutions/acwing/1220.cpp new file mode 100644 index 0000000..443ed43 --- /dev/null +++ b/store/works/solutions/acwing/1220.cpp @@ -0,0 +1,65 @@ +#include <iostream>
+#include <vector>
+
+const int N = 100010;
+
+struct Node {
+ int w;
+ std::vector<int> children;
+};
+
+int n;
+Node nodes[N];
+bool visited[N];
+long long contain_root[N];
+long long contain_or_not_contain_root[N];
+
+void dfs(int i) {
+ visited[i] = true;
+ long long this_contain_root = nodes[i].w;
+ long long this_contain_or_not_contain_root = nodes[i].w;
+
+ for (auto next : nodes[i].children) {
+ if (!visited[next]) {
+ dfs(next);
+ if (contain_root[next] > 0) {
+ this_contain_root += contain_root[next];
+ }
+ if (contain_or_not_contain_root[next] >
+ this_contain_or_not_contain_root) {
+ this_contain_or_not_contain_root = contain_or_not_contain_root[next];
+ }
+ }
+ }
+
+ if (this_contain_root > this_contain_or_not_contain_root) {
+ this_contain_or_not_contain_root = this_contain_root;
+ }
+
+ contain_root[i] = this_contain_root;
+ contain_or_not_contain_root[i] = this_contain_or_not_contain_root;
+}
+
+int main() {
+ std::ios_base::sync_with_stdio(false);
+ std::cin.tie(nullptr);
+
+ std::cin >> n;
+
+ for (int i = 1; i <= n; i++) {
+ std::cin >> nodes[i].w;
+ }
+
+ for (int i = 1; i < n; i++) {
+ int a, b;
+ std::cin >> a >> b;
+ nodes[a].children.push_back(b);
+ nodes[b].children.push_back(a);
+ }
+
+ dfs(1);
+
+ std::cout << contain_or_not_contain_root[1];
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1221.cpp b/store/works/solutions/acwing/1221.cpp new file mode 100644 index 0000000..9ba4229 --- /dev/null +++ b/store/works/solutions/acwing/1221.cpp @@ -0,0 +1,45 @@ +#include <cmath>
+#include <iostream>
+
+const int M = 5000010;
+const int SM = std::sqrt(M / 2);
+
+int s[M];
+
+int main() {
+ int n;
+ std::cin >> n;
+
+ for (int i = 0; i <= SM; i++) {
+ const int i2 = i * i;
+ const int SMB = M - i2;
+ for (int j = i; j * j < SMB; j++) {
+ const int a = i2 + j * j;
+
+ if (s[a] == 0) {
+ s[a] = i + 1;
+ }
+ }
+ }
+
+ int sm = std::sqrt(n);
+
+ for (int a = 0; a <= sm; a++) {
+ int as = a * a;
+ int bsm = n - 3 * a * a;
+ for (int b = a; b * b <= bsm; b++) {
+ int bs = b * b + as;
+
+ int c = s[n - bs];
+
+ if (c != 0) {
+ c = c - 1;
+ std::cout << a << ' ' << b << ' ' << c << ' '
+ << std::sqrt(n - bs - c * c);
+ return 0;
+ }
+ }
+ }
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1224.cpp b/store/works/solutions/acwing/1224.cpp new file mode 100644 index 0000000..8cdd9f0 --- /dev/null +++ b/store/works/solutions/acwing/1224.cpp @@ -0,0 +1,33 @@ +#include <iostream> +#include <utility> + +int N; +int x[10010]; + +int main() { + std::ios_base::sync_with_stdio(false); + std::cin.tie(nullptr); + + std::cin >> N; + for (int i = 1; i <= N; i++) { + std::cin >> x[i]; + } + + int result = 0; + + for (int i = 1; i <= N - 1; i++) { + if (x[i] != i) { + for (int j = i + 1; j <= N; j++) { + if (x[j] == i) { + x[j] = x[i]; + result++; + break; + } + } + } + } + + std::cout << result; + + return 0; +} diff --git a/store/works/solutions/acwing/1226.cpp b/store/works/solutions/acwing/1226.cpp new file mode 100644 index 0000000..cbfea98 --- /dev/null +++ b/store/works/solutions/acwing/1226.cpp @@ -0,0 +1,55 @@ +#include <iostream> + +int gcd(int a, int b) { + if (b == 0) + return a; + return gcd(b, a % b); +} + +int N; +int A[110]; + +const int M = 10000; + +bool f[M + 10]; + +int main() { + std::ios_base::sync_with_stdio(false); + std::cin.tie(nullptr); + + std::cin >> N; + + for (int i = 1; i <= N; i++) { + std::cin >> A[i]; + } + + int a = A[1]; + + for (int i = 2; i <= N; i++) { + a = gcd(a, A[i]); + } + + if (a != 1) { + std::cout << "INF"; + return 0; + } + + f[0] = true; + + for (int i = 1; i <= N; i++) { + for (int w = A[i]; w <= M; w++) { + f[w] = f[w] || f[w - A[i]]; + } + } + + int count = 0; + + for (int i = 1; i <= M; i++) { + if (f[i] == false) + count++; + } + + std::cout << count; + + return 0; +} diff --git a/store/works/solutions/acwing/1227.cpp b/store/works/solutions/acwing/1227.cpp new file mode 100644 index 0000000..ff14be2 --- /dev/null +++ b/store/works/solutions/acwing/1227.cpp @@ -0,0 +1,50 @@ +#include <iostream> + +const int M = 1e5 + 10; + +int N, K; +int H[M]; +int W[M]; + +bool check(int l) { + if (l == 0) + return true; + + int count = 0; + + for (int i = 1; i <= N; i++) { + count += (H[i] / l) * (W[i] / l); + if (K <= count) { + return true; + } + } + + return false; +} + +int main() { + std::ios_base::sync_with_stdio(false); + std::cin.tie(nullptr); + + std::cin >> N >> K; + + for (int i = 1; i <= N; i++) { + std::cin >> H[i] >> W[i]; + } + + int l = 0, r = M; + + while (l != r) { + int m = l + ((r - l + 1) / 2); + + if (check(m)) { + l = m; + } else { + r = m - 1; + } + } + + std::cout << l; + + return 0; +} diff --git a/store/works/solutions/acwing/1229.cpp b/store/works/solutions/acwing/1229.cpp new file mode 100644 index 0000000..e3b16ba --- /dev/null +++ b/store/works/solutions/acwing/1229.cpp @@ -0,0 +1,106 @@ +#include <algorithm>
+#include <cstdio>
+#include <vector>
+
+int ConvertYear(int x) {
+ if (x >= 60)
+ return 1900 + x;
+ return 2000 + x;
+}
+
+bool CheckMonth(int x) {
+ if (x <= 0 && x >= 13) {
+ return false;
+ }
+
+ return true;
+}
+
+bool IsLeapYear(int y) {
+ if (y == 2000)
+ return false;
+ if (y % 4)
+ return false;
+ return true;
+}
+
+int days[] = {0, 31, 0, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
+
+bool CheckDay(int day, int month, int year) {
+ if (month == 2) {
+ const bool leap = IsLeapYear(year);
+ if (leap) {
+ return day >= 1 && day <= 29;
+ } else {
+ return day >= 1 && day <= 28;
+ }
+ }
+
+ return day >= 1 && day <= days[month];
+}
+
+struct Date {
+ int year;
+ int month;
+ int day;
+};
+
+bool operator==(const Date &l, const Date &r) {
+ return l.year == r.year && l.month == r.month && l.day == r.day;
+}
+
+bool operator<(const Date &l, const Date &r) {
+ if (l.year < r.year)
+ return true;
+ else if (l.year > r.year)
+ return false;
+ else if (l.month < r.month)
+ return true;
+ else if (l.month > r.month)
+ return false;
+ else if (l.day < r.day)
+ return true;
+ return false;
+}
+
+bool Check(int year, int month, int day, Date *result) {
+ if (!CheckMonth(month))
+ return false;
+ const auto y = ConvertYear(year);
+ if (!CheckDay(day, month, y))
+ return false;
+
+ result->year = y;
+ result->month = month;
+ result->day = day;
+ return true;
+}
+
+int main() {
+ std::vector<Date> results;
+
+ int a, b, c;
+ std::scanf("%d/%d/%d", &a, &b, &c);
+
+ Date temp;
+ if (Check(a, b, c, &temp)) {
+ results.push_back(temp);
+ }
+
+ if (Check(c, a, b, &temp)) {
+ results.push_back(temp);
+ }
+
+ if (Check(c, b, a, &temp)) {
+ results.push_back(temp);
+ }
+
+ results.erase(std::unique(results.begin(), results.end()), results.end());
+ std::sort(results.begin(), results.end());
+
+ for (const auto &r : results) {
+ std::printf("%d-%02d-%02d\n", r.year, r.month, r.day);
+ }
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1230.cpp b/store/works/solutions/acwing/1230.cpp new file mode 100644 index 0000000..958cbdd --- /dev/null +++ b/store/works/solutions/acwing/1230.cpp @@ -0,0 +1,36 @@ +#include <iostream>
+
+using ll = long long;
+
+const int M = 100010;
+
+int N, K;
+ll p;
+int c[M];
+ll result;
+
+int main() {
+ std::ios_base::sync_with_stdio(false);
+ std::cin.tie(nullptr);
+
+ std::cin >> N >> K;
+
+ c[0] = 1;
+
+ for (int i = 1; i <= N; i++) {
+ int a;
+ std::cin >> a;
+
+ p += a;
+
+ int r = p % K;
+
+ result += c[r];
+
+ c[r]++;
+ }
+
+ std::cout << result;
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1233.cpp b/store/works/solutions/acwing/1233.cpp new file mode 100644 index 0000000..117b2fb --- /dev/null +++ b/store/works/solutions/acwing/1233.cpp @@ -0,0 +1,69 @@ +#include <iostream>
+#include <utility>
+
+const int M = 1010;
+
+int N;
+char map[M][M];
+bool visited[M][M];
+
+int not_sink_count;
+
+const std::pair<int, int> moves[]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
+
+void dfs(int r, int c) {
+ if (visited[r][c])
+ return;
+ if (map[r][c] != '#')
+ return;
+
+ visited[r][c] = true;
+
+ bool sink = false;
+
+ for (const auto &move : moves) {
+ if (map[r + move.first][c + move.second] == '.') {
+ sink = true;
+ break;
+ }
+ }
+
+ if (!sink) {
+ not_sink_count++;
+ }
+
+ for (const auto &move : moves) {
+ dfs(r + move.first, c + move.second);
+ }
+}
+
+int main() {
+ std::ios_base::sync_with_stdio(false);
+ std::cin.tie(nullptr);
+
+ std::cin >> N;
+
+ for (int i = 1; i <= N; i++) {
+ for (int j = 1; j <= N; j++) {
+ std::cin >> map[i][j];
+ }
+ }
+
+ int result = 0;
+
+ for (int i = 1; i <= N; i++) {
+ for (int j = 1; j <= N; j++) {
+ if (map[i][j] == '#' && !visited[i][j]) {
+ dfs(i, j);
+ if (not_sink_count == 0) {
+ result++;
+ }
+ not_sink_count = 0;
+ }
+ }
+ }
+
+ std::cout << result;
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1236.cpp b/store/works/solutions/acwing/1236.cpp new file mode 100644 index 0000000..a89a890 --- /dev/null +++ b/store/works/solutions/acwing/1236.cpp @@ -0,0 +1,54 @@ +#include <iostream>
+
+const int MAX = 100000;
+const int MM = 100010;
+
+int N;
+
+long long ca[MM];
+long long cb[MM];
+
+int main() {
+ std::ios_base::sync_with_stdio(false);
+ std::cin.tie(nullptr);
+
+ std::cin >> N;
+
+ for (int i = 0; i < N; i++) {
+ int a;
+ std::cin >> a;
+ ca[a]++;
+ }
+
+ for (int n = 1; n <= MAX; n++) {
+ ca[n] = ca[n - 1] + ca[n];
+ }
+
+ for (int i = 0; i < N; i++) {
+ int b;
+ std::cin >> b;
+ cb[b]++;
+ }
+
+ for (int n = 1; n <= MAX; n++) {
+ cb[n] *= ca[n - 1];
+ }
+
+ for (int n = 2; n <= MAX; n++) {
+ cb[n] = cb[n - 1] + cb[n];
+ }
+
+ long long result = 0;
+
+ for (int i = 0; i < N; i++) {
+ int c;
+ std::cin >> c;
+ if (c >= 2) {
+ result += cb[c - 1];
+ }
+ }
+
+ std::cout << result;
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1237.cpp b/store/works/solutions/acwing/1237.cpp new file mode 100644 index 0000000..a3b8810 --- /dev/null +++ b/store/works/solutions/acwing/1237.cpp @@ -0,0 +1,49 @@ +#include <cmath>
+#include <iostream>
+
+using ll = long long;
+
+int main() {
+ ll X, Y;
+ std::cin >> X >> Y;
+
+ ll result = 0;
+
+ if (X == 0 && Y == 0) {
+ return 0;
+ }
+
+ if (std::abs(X) > std::abs(Y) ||
+ (std::abs(X) == std::abs(Y) && !(X < 0 && Y < 0))) {
+ ll c = std::abs(X);
+
+ result += ((c - 1) * 4 + 2) * (c - 1);
+
+ if (X > 0) {
+ result += (c * 2 - 1) * 2;
+ result += c * 2;
+ result += (c - Y);
+ } else {
+ result += (c * 2 - 1);
+ result += (Y - (-c + 1));
+ }
+
+ } else {
+ ll c = std::abs(Y);
+
+ result += ((c - 1) * 4 + 2) * (c - 1);
+
+ if (Y > 0) {
+ result += (c * 2 - 1) * 2;
+ result += (X - (-c));
+ } else {
+ result += (c * 2 - 1) * 2;
+ result += c * 2 * 2;
+ result += c - X;
+ }
+ }
+
+ std::cout << result;
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1238.cpp b/store/works/solutions/acwing/1238.cpp new file mode 100644 index 0000000..2c9d899 --- /dev/null +++ b/store/works/solutions/acwing/1238.cpp @@ -0,0 +1,56 @@ +#include <iostream>
+#include <map>
+#include <set>
+
+const int M = 100010;
+
+int N, D, K;
+
+std::map<int, std::multiset<int>> vote_map;
+
+bool check(const std::multiset<int> &v) {
+ auto iter1 = v.cbegin();
+ auto iter2 = v.cbegin();
+
+ const auto end = v.cend();
+
+ int count = 1;
+
+ while (iter2 != end) {
+ while (*iter2 - *iter1 >= D) {
+ ++iter1;
+ count--;
+ }
+
+ if (count >= K)
+ return true;
+
+ ++iter2;
+ count++;
+ }
+
+ return false;
+}
+
+int main() {
+ std::ios_base::sync_with_stdio(false);
+ std::cin.tie(nullptr);
+
+ std::cin >> N >> D >> K;
+
+ for (int i = 1; i <= N; i++) {
+ int ts, id;
+ std::cin >> ts >> id;
+ vote_map[id].insert(ts);
+ }
+
+ int result;
+
+ for (const auto &vote : vote_map) {
+ if (check(vote.second)) {
+ std::cout << vote.first << "\n";
+ }
+ }
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1239.cpp b/store/works/solutions/acwing/1239.cpp new file mode 100644 index 0000000..c670cd4 --- /dev/null +++ b/store/works/solutions/acwing/1239.cpp @@ -0,0 +1,52 @@ +#include <algorithm>
+#include <iostream>
+
+int N, K;
+long long A[100010];
+
+long long M = 1000000009;
+
+int main() {
+ std::ios_base::sync_with_stdio(false);
+ std::cin.tie(nullptr);
+
+ std::cin >> N >> K;
+
+ for (int i = 0; i < N; i++) {
+ std::cin >> A[i];
+ }
+
+ std::sort(A, A + N);
+
+ long long result = 1;
+ int left = 0, right = N - 1;
+ long long sign = 1;
+ int k = K;
+
+ if (k % 2) {
+ result = A[N - 1];
+ right--;
+ k--;
+
+ if (result < 0) {
+ sign = -1;
+ }
+ }
+
+ while (k) {
+ long long x = A[left] * A[left + 1], y = A[right] * A[right - 1];
+
+ if (x * sign > y * sign) {
+ result = x % M * result % M;
+ left += 2;
+ } else {
+ result = y % M * result % M;
+ right -= 2;
+ }
+ k -= 2;
+ }
+
+ std::cout << result;
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1240.cpp b/store/works/solutions/acwing/1240.cpp new file mode 100644 index 0000000..8ebae33 --- /dev/null +++ b/store/works/solutions/acwing/1240.cpp @@ -0,0 +1,42 @@ +#include <iostream>
+
+int main() {
+ std::ios_base::sync_with_stdio(false);
+ std::cin.tie(nullptr);
+
+ int n;
+ std::cin >> n;
+
+ int current_count = 0;
+ int current_level_count = 1;
+ int current_level = 1;
+ long long current_sum = 0;
+ long long max_sum = -1000000;
+ int result = 1;
+
+ for (int i = 0; i < n; i++) {
+ long long a;
+ std::cin >> a;
+ current_sum += a;
+ current_count++;
+
+ if (current_count == current_level_count) {
+ if (current_sum > max_sum) {
+ max_sum = current_sum;
+ result = current_level;
+ }
+ current_count = 0;
+ current_level_count *= 2;
+ current_sum = 0;
+ current_level++;
+ }
+ }
+
+ if (current_count && current_sum > max_sum) {
+ result = current_level;
+ }
+
+ std::cout << result;
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1245.cpp b/store/works/solutions/acwing/1245.cpp new file mode 100644 index 0000000..ba51a8f --- /dev/null +++ b/store/works/solutions/acwing/1245.cpp @@ -0,0 +1,29 @@ +#include <iostream>
+
+bool check(int n) {
+ while (n != 0) {
+ int k = n % 10;
+ if (k == 2 || k == 0 || k == 1 || k == 9) {
+ return true;
+ }
+ n /= 10;
+ }
+ return false;
+}
+
+int main() {
+ int n;
+ std::cin >> n;
+
+ long long sum;
+
+ for (int i = 1; i <= n; i++) {
+ if (check(i)) {
+ sum += i;
+ }
+ }
+
+ std::cout << sum;
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/1246.cpp b/store/works/solutions/acwing/1246.cpp new file mode 100644 index 0000000..5c0454c --- /dev/null +++ b/store/works/solutions/acwing/1246.cpp @@ -0,0 +1,34 @@ +#include <algorithm>
+#include <iostream>
+#include <numeric>
+
+int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
+
+int N;
+int A[100010];
+
+int main() {
+ std::ios_base::sync_with_stdio(false);
+ std::cin.tie(nullptr);
+
+ std::cin >> N;
+
+ for (int i = 0; i < N; i++) {
+ std::cin >> A[i];
+ }
+
+ std::sort(A, A + N);
+
+ int g = A[1] - A[0];
+ for (int i = 1; i < N - 1; i++) {
+ g = gcd(g, A[i + 1] - A[i]);
+ }
+
+ if (g == 0) {
+ std::cout << N;
+ } else {
+ std::cout << (A[N - 1] - A[0]) / g + 1;
+ }
+
+ return 0;
+}
\ No newline at end of file diff --git a/store/works/solutions/acwing/1247.cpp b/store/works/solutions/acwing/1247.cpp new file mode 100644 index 0000000..1fd4412 --- /dev/null +++ b/store/works/solutions/acwing/1247.cpp @@ -0,0 +1,39 @@ +#include <cmath>
+#include <iostream>
+
+int main() {
+ std::ios_base::sync_with_stdio(false);
+ std::cin.tie(nullptr);
+
+ int N, M;
+ std::cin >> N >> M;
+
+ long long result = 0;
+
+ long long min = 1e9 + 1;
+ long long max = -1e9 - 1;
+
+ for (int i = 0; i < N + M + 1; i++) {
+ long long a;
+ std::cin >> a;
+ max = std::max(a, max);
+ min = std::min(a, min);
+ if (M == 0) {
+ result += a;
+ } else {
+ result += std::abs(a);
+ }
+ }
+
+ if (M != 0 && max < 0) {
+ result += 2 * max;
+ }
+
+ if (M != 0 && min > 0) {
+ result -= 2 * min;
+ }
+
+ std::cout << result;
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/2-2.cpp b/store/works/solutions/acwing/2-2.cpp new file mode 100644 index 0000000..fb0fb3b --- /dev/null +++ b/store/works/solutions/acwing/2-2.cpp @@ -0,0 +1,25 @@ +#include <algorithm>
+#include <iostream>
+
+int N, V;
+int v[1001];
+int w[1001];
+int states[1001];
+
+int main() {
+ std::cin >> N >> V;
+
+ for (int i = 1; i <= N; i++) {
+ std::cin >> v[i] >> w[i];
+ }
+
+ for (int i = 1; i <= N; i++) {
+ for (int j = V; j >= v[i]; j--) {
+ states[j] = std::max(states[j], states[j - v[i]] + w[i]);
+ }
+ }
+
+ std::cout << states[V];
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/2.cpp b/store/works/solutions/acwing/2.cpp new file mode 100644 index 0000000..1a75c19 --- /dev/null +++ b/store/works/solutions/acwing/2.cpp @@ -0,0 +1,30 @@ +#include <algorithm>
+#include <iostream>
+
+int N, V;
+int v[1001];
+int w[1001];
+int states[1001][1001];
+
+int main() {
+ std::cin >> N >> V;
+
+ for (int i = 1; i <= N; i++) {
+ std::cin >> v[i] >> w[i];
+ }
+
+ for (int i = 1; i <= N; i++) {
+ for (int j = V; j >= 0; j--) {
+ if (j >= v[i]) {
+ states[i][j] =
+ std::max(states[i - 1][j], states[i - 1][j - v[i]] + w[i]);
+ } else {
+ states[i][j] = states[i - 1][j];
+ }
+ }
+ }
+
+ std::cout << states[N][V];
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/2065.cpp b/store/works/solutions/acwing/2065.cpp new file mode 100644 index 0000000..a0c47c2 --- /dev/null +++ b/store/works/solutions/acwing/2065.cpp @@ -0,0 +1,16 @@ +#include <iostream>
+
+int main() {
+ std::ios_base::sync_with_stdio(false);
+ std::cin.tie(nullptr);
+
+ long long n;
+ std::cin >> n;
+
+ while (n) {
+ std::cout << n << ' ';
+ n /= 2;
+ }
+
+ return 0;
+}
\ No newline at end of file diff --git a/store/works/solutions/acwing/2066.cpp b/store/works/solutions/acwing/2066.cpp new file mode 100644 index 0000000..7a6132b --- /dev/null +++ b/store/works/solutions/acwing/2066.cpp @@ -0,0 +1,21 @@ +#include <cctype>
+#include <iostream>
+
+int main() {
+ std::string input;
+ std::cin >> input;
+ std::string result;
+
+ for (int i = 0; i < input.size(); i++) {
+ if (std::isalpha(input[i])) {
+ result.push_back(input[i]);
+ } else {
+ int c = input[i] - '1';
+ result.append(c, input[i - 1]);
+ }
+ }
+
+ std::cout << result;
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/2067.cpp b/store/works/solutions/acwing/2067.cpp new file mode 100644 index 0000000..3ebd61d --- /dev/null +++ b/store/works/solutions/acwing/2067.cpp @@ -0,0 +1,22 @@ +#include <iostream>
+
+int n, m;
+long long f[31][31];
+
+int main() {
+ std::cin >> n >> m;
+
+ f[1][1] = 1;
+
+ for (int r = 1; r <= n; r++) {
+ for (int c = 1; c <= m; c++) {
+ if (!(r == 1 && c == 1) && !(r % 2 == 0 && c % 2 == 0)) {
+ f[r][c] = f[r - 1][c] + f[r][c - 1];
+ }
+ }
+ }
+
+ std::cout << f[n][m];
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/2068.cpp b/store/works/solutions/acwing/2068.cpp new file mode 100644 index 0000000..592f43f --- /dev/null +++ b/store/works/solutions/acwing/2068.cpp @@ -0,0 +1,57 @@ +#include <algorithm>
+#include <cmath>
+#include <cstring>
+#include <iostream>
+
+int n, K;
+int A[100010];
+int c[11][100010];
+long long result;
+
+int CalcDigitCount(int n) {
+ int c = 0;
+ while (n != 0) {
+ c++;
+ n /= 10;
+ }
+ return c;
+}
+
+void work() {
+ for (int i = 0; i < n; i++) {
+ result += c[CalcDigitCount(A[i])][(K - A[i] % K) % K];
+ // Wrong Code I don't know why!
+ // int a = A[i];
+ // for (int j = 1; j < 11; j++) {
+ // a *= 10;
+ // a %= K;
+ // c[j][a]++;
+ // }
+ for (int j = 0, power = 1; j < 11; j++) {
+ c[j][power * 1ll * A[i] % K]++;
+ power = power * 10 % K;
+ }
+ }
+}
+
+int main() {
+ std::ios_base::sync_with_stdio(false);
+ std::cin.tie(nullptr);
+
+ std::cin >> n >> K;
+
+ for (int i = 0; i < n; i++) {
+ std::cin >> A[i];
+ }
+
+ work();
+
+ std::reverse(A, A + n);
+ std::memset(c, 0, sizeof c);
+
+ work();
+
+ std::cout << result;
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/2069.cpp b/store/works/solutions/acwing/2069.cpp new file mode 100644 index 0000000..fbfa6d2 --- /dev/null +++ b/store/works/solutions/acwing/2069.cpp @@ -0,0 +1,82 @@ +#include <iostream>
+#include <vector>
+
+struct Node {
+ int m = 0;
+ Node *set;
+ Node *left = nullptr;
+ Node *right = nullptr;
+
+ Node() : set(this) {}
+
+ void SetParent(Node *parent, bool l) {
+ set = parent;
+ l ? parent->left = this : parent->right = this;
+ }
+
+ Node *GetSetRepresentative() {
+ Node *r = this;
+ while (r->set != r) {
+ r = r->set;
+ }
+ set = r;
+ return set;
+ }
+
+ bool has_dfs = false;
+
+ void Dfs() {
+ if (has_dfs)
+ return;
+ has_dfs = true;
+ if (left != nullptr)
+ left->Dfs(m);
+ if (right != nullptr)
+ right->Dfs(m);
+ }
+
+ void Dfs(int c) {
+ m += c;
+ if (left != nullptr)
+ left->Dfs(m);
+ if (right != nullptr)
+ right->Dfs(m);
+ }
+};
+
+Node nodes[10010];
+
+int main() {
+ std::ios_base::sync_with_stdio(false);
+ std::cin.tie(nullptr);
+
+ int n, m;
+
+ std::cin >> n >> m;
+
+ for (int i = 0; i < m; i++) {
+ int operation, a, b;
+ std::cin >> operation >> a >> b;
+
+ if (operation == 1) {
+ auto ra = nodes[a].GetSetRepresentative(),
+ rb = nodes[b].GetSetRepresentative();
+
+ if (ra != rb) {
+ auto node = new Node;
+ ra->SetParent(node, true);
+ rb->SetParent(node, false);
+ }
+ } else {
+ nodes[a].GetSetRepresentative()->m += b;
+ }
+ }
+
+ for (int i = 1; i <= n; i++) {
+ auto &node = nodes[i];
+ node.GetSetRepresentative()->Dfs();
+ std::cout << node.m << ' ';
+ }
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/3-2.cpp b/store/works/solutions/acwing/3-2.cpp new file mode 100644 index 0000000..c099838 --- /dev/null +++ b/store/works/solutions/acwing/3-2.cpp @@ -0,0 +1,25 @@ +#include <algorithm>
+#include <iostream>
+
+int N, V;
+int v[1001];
+int w[1001];
+int states[1001];
+
+int main() {
+ std::cin >> N >> V;
+
+ for (int i = 1; i <= N; i++) {
+ std::cin >> v[i] >> w[i];
+ }
+
+ for (int i = 1; i <= N; i++) {
+ for (int j = v[i]; j <= V; j++) {
+ states[j] = std::max(states[j], states[j - v[i]] + w[i]);
+ }
+ }
+
+ std::cout << states[V];
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/3.cpp b/store/works/solutions/acwing/3.cpp new file mode 100644 index 0000000..21bd8dc --- /dev/null +++ b/store/works/solutions/acwing/3.cpp @@ -0,0 +1,29 @@ +#include <algorithm>
+#include <iostream>
+
+int N, V;
+int v[1001];
+int w[1001];
+int states[1001][1001];
+
+int main() {
+ std::cin >> N >> V;
+
+ for (int i = 1; i <= N; i++) {
+ std::cin >> v[i] >> w[i];
+ }
+
+ for (int i = 1; i <= N; i++) {
+ for (int j = 0; j <= V; j++) {
+ if (j >= v[i]) {
+ states[i][j] = std::max(states[i - 1][j], states[i][j - v[i]] + w[i]);
+ } else {
+ states[i][j] = states[i - 1][j];
+ }
+ }
+ }
+
+ std::cout << states[N][V];
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/4.cpp b/store/works/solutions/acwing/4.cpp new file mode 100644 index 0000000..3270402 --- /dev/null +++ b/store/works/solutions/acwing/4.cpp @@ -0,0 +1,51 @@ +#include <algorithm>
+#include <iostream>
+
+int N, V;
+int v[101];
+int w[101];
+int s[101];
+int states[101];
+
+void CompletePack(int v, int w) {
+ for (int j = v; j <= V; j++) {
+ states[j] = std::max(states[j], states[j - v] + w);
+ }
+}
+
+void ZeroOnePack(int v, int w) {
+ for (int j = V; j >= v; j--) {
+ states[j] = std::max(states[j], states[j - v] + w);
+ }
+}
+
+int main() {
+ std::cin >> N >> V;
+
+ for (int i = 1; i <= N; i++) {
+ std::cin >> v[i] >> w[i] >> s[i];
+ }
+
+ for (int i = 1; i <= N; i++) {
+ if (v[i] * s[i] >= V) {
+ CompletePack(v[i], w[i]);
+ } else {
+ int k = 1;
+ int amount = s[i];
+
+ while (k < amount) {
+ ZeroOnePack(k * v[i], k * w[i]);
+ amount -= k;
+ k *= 2;
+ }
+
+ if (amount != 0) {
+ ZeroOnePack(amount * v[i], amount * w[i]);
+ }
+ }
+ }
+
+ std::cout << states[V];
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/5.cpp b/store/works/solutions/acwing/5.cpp new file mode 100644 index 0000000..a88fba6 --- /dev/null +++ b/store/works/solutions/acwing/5.cpp @@ -0,0 +1,49 @@ +#include <algorithm>
+#include <iostream>
+
+int N, V;
+int v[1001];
+int w[1001];
+int s[1001];
+int states[2001];
+
+void CompletePack(int v, int w) {
+ for (int j = v; j <= V; j++) {
+ states[j] = std::max(states[j], states[j - v] + w);
+ }
+}
+
+void ZeroOnePack(int v, int w) {
+ for (int j = V; j >= v; j--) {
+ states[j] = std::max(states[j], states[j - v] + w);
+ }
+}
+
+int main() {
+ std::cin >> N >> V;
+
+ for (int i = 1; i <= N; i++) {
+ std::cin >> v[i] >> w[i] >> s[i];
+ }
+
+ for (int i = 1; i <= N; i++) {
+ if (v[i] * s[i] >= V) {
+ CompletePack(v[i], w[i]);
+ } else {
+ int k = 1;
+ int amount = s[i];
+
+ while (k < amount) {
+ ZeroOnePack(k * v[i], k * w[i]);
+ amount -= k;
+ k *= 2;
+ }
+
+ ZeroOnePack(amount * v[i], amount * w[i]);
+ }
+ }
+
+ std::cout << states[V];
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/7.cpp b/store/works/solutions/acwing/7.cpp new file mode 100644 index 0000000..fcc0fb1 --- /dev/null +++ b/store/works/solutions/acwing/7.cpp @@ -0,0 +1,54 @@ +#include <algorithm>
+#include <iostream>
+
+int N, V;
+int v[1001];
+int w[1001];
+int s[1001];
+int states[1001];
+
+void CompletePack(int v, int w) {
+ for (int j = v; j <= V; j++) {
+ states[j] = std::max(states[j], states[j - v] + w);
+ }
+}
+
+void ZeroOnePack(int v, int w) {
+ for (int j = V; j >= v; j--) {
+ states[j] = std::max(states[j], states[j - v] + w);
+ }
+}
+
+void MultiplePack(int v, int w, int s) {
+ int k = 1;
+
+ while (k < s) {
+ ZeroOnePack(k * v, k * w);
+ s -= k;
+ k *= 2;
+ }
+
+ ZeroOnePack(s * v, s * w);
+}
+
+int main() {
+ std::cin >> N >> V;
+
+ for (int i = 1; i <= N; i++) {
+ std::cin >> v[i] >> w[i] >> s[i];
+ }
+
+ for (int i = 1; i <= N; i++) {
+ if (s[i] < 0) {
+ ZeroOnePack(v[i], w[i]);
+ } else if (s[i] == 0) {
+ CompletePack(v[i], w[i]);
+ } else {
+ MultiplePack(v[i], w[i], s[i]);
+ }
+ }
+
+ std::cout << states[V];
+
+ return 0;
+}
diff --git a/store/works/solutions/acwing/8.cpp b/store/works/solutions/acwing/8.cpp new file mode 100644 index 0000000..f62d21e --- /dev/null +++ b/store/works/solutions/acwing/8.cpp @@ -0,0 +1,29 @@ +#include <algorithm>
+#include <iostream>
+
+int N, V, M;
+int v[1001];
+int w[1001];
+int m[1001];
+int states[101][101];
+
+int main() {
+ std::cin >> N >> V >> M;
+
+ for (int i = 1; i <= N; i++) {
+ std::cin >> v[i] >> m[i] >> w[i];
+ }
+
+ for (int i = 1; i <= N; i++) {
+ for (int j = V; j >= v[i]; j--) {
+ for (int k = M; k >= m[i]; k--) {
+ states[j][k] =
+ std::max(states[j][k], states[j - v[i]][k - m[i]] + w[i]);
+ }
+ }
+ }
+
+ std::cout << states[V][M];
+
+ return 0;
+}
\ No newline at end of file |