From dc1f0c4c0096013799416664894c5194dc7e1f52 Mon Sep 17 00:00:00 2001 From: Yuqian Yang Date: Fri, 28 Feb 2025 23:13:39 +0800 Subject: chore(store): move everything to store. --- works/solutions/acwing/1204.cpp | 31 ------------ works/solutions/acwing/1208.cpp | 24 --------- works/solutions/acwing/1209.cpp | 48 ------------------ works/solutions/acwing/1210.cpp | 37 -------------- works/solutions/acwing/1211.cpp | 38 -------------- works/solutions/acwing/1212.cpp | 46 ----------------- works/solutions/acwing/1215.cpp | 59 ---------------------- works/solutions/acwing/1216.cpp | 19 ------- works/solutions/acwing/1217.cpp | 67 ------------------------- works/solutions/acwing/1219.cpp | 26 ---------- works/solutions/acwing/1220.cpp | 65 ------------------------ works/solutions/acwing/1221.cpp | 45 ----------------- works/solutions/acwing/1224.cpp | 33 ------------- works/solutions/acwing/1226.cpp | 55 --------------------- works/solutions/acwing/1227.cpp | 50 ------------------- works/solutions/acwing/1229.cpp | 106 ---------------------------------------- works/solutions/acwing/1230.cpp | 36 -------------- works/solutions/acwing/1233.cpp | 69 -------------------------- works/solutions/acwing/1236.cpp | 54 -------------------- works/solutions/acwing/1237.cpp | 49 ------------------- works/solutions/acwing/1238.cpp | 56 --------------------- works/solutions/acwing/1239.cpp | 52 -------------------- works/solutions/acwing/1240.cpp | 42 ---------------- works/solutions/acwing/1245.cpp | 29 ----------- works/solutions/acwing/1246.cpp | 34 ------------- works/solutions/acwing/1247.cpp | 39 --------------- works/solutions/acwing/2-2.cpp | 25 ---------- works/solutions/acwing/2.cpp | 30 ------------ works/solutions/acwing/2065.cpp | 16 ------ works/solutions/acwing/2066.cpp | 21 -------- works/solutions/acwing/2067.cpp | 22 --------- works/solutions/acwing/2068.cpp | 57 --------------------- works/solutions/acwing/2069.cpp | 82 ------------------------------- works/solutions/acwing/3-2.cpp | 25 ---------- works/solutions/acwing/3.cpp | 29 ----------- works/solutions/acwing/4.cpp | 51 ------------------- works/solutions/acwing/5.cpp | 49 ------------------- works/solutions/acwing/7.cpp | 54 -------------------- works/solutions/acwing/8.cpp | 29 ----------- 39 files changed, 1699 deletions(-) delete mode 100644 works/solutions/acwing/1204.cpp delete mode 100644 works/solutions/acwing/1208.cpp delete mode 100644 works/solutions/acwing/1209.cpp delete mode 100644 works/solutions/acwing/1210.cpp delete mode 100644 works/solutions/acwing/1211.cpp delete mode 100644 works/solutions/acwing/1212.cpp delete mode 100644 works/solutions/acwing/1215.cpp delete mode 100644 works/solutions/acwing/1216.cpp delete mode 100644 works/solutions/acwing/1217.cpp delete mode 100644 works/solutions/acwing/1219.cpp delete mode 100644 works/solutions/acwing/1220.cpp delete mode 100644 works/solutions/acwing/1221.cpp delete mode 100644 works/solutions/acwing/1224.cpp delete mode 100644 works/solutions/acwing/1226.cpp delete mode 100644 works/solutions/acwing/1227.cpp delete mode 100644 works/solutions/acwing/1229.cpp delete mode 100644 works/solutions/acwing/1230.cpp delete mode 100644 works/solutions/acwing/1233.cpp delete mode 100644 works/solutions/acwing/1236.cpp delete mode 100644 works/solutions/acwing/1237.cpp delete mode 100644 works/solutions/acwing/1238.cpp delete mode 100644 works/solutions/acwing/1239.cpp delete mode 100644 works/solutions/acwing/1240.cpp delete mode 100644 works/solutions/acwing/1245.cpp delete mode 100644 works/solutions/acwing/1246.cpp delete mode 100644 works/solutions/acwing/1247.cpp delete mode 100644 works/solutions/acwing/2-2.cpp delete mode 100644 works/solutions/acwing/2.cpp delete mode 100644 works/solutions/acwing/2065.cpp delete mode 100644 works/solutions/acwing/2066.cpp delete mode 100644 works/solutions/acwing/2067.cpp delete mode 100644 works/solutions/acwing/2068.cpp delete mode 100644 works/solutions/acwing/2069.cpp delete mode 100644 works/solutions/acwing/3-2.cpp delete mode 100644 works/solutions/acwing/3.cpp delete mode 100644 works/solutions/acwing/4.cpp delete mode 100644 works/solutions/acwing/5.cpp delete mode 100644 works/solutions/acwing/7.cpp delete mode 100644 works/solutions/acwing/8.cpp (limited to 'works/solutions/acwing') diff --git a/works/solutions/acwing/1204.cpp b/works/solutions/acwing/1204.cpp deleted file mode 100644 index e3e5395..0000000 --- a/works/solutions/acwing/1204.cpp +++ /dev/null @@ -1,31 +0,0 @@ -#include -#include -#include - -int main() { - std::ios_base::sync_with_stdio(false); - - int repeat; - - int n; - std::cin >> n; - - std::set 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/works/solutions/acwing/1208.cpp b/works/solutions/acwing/1208.cpp deleted file mode 100644 index 84f60f1..0000000 --- a/works/solutions/acwing/1208.cpp +++ /dev/null @@ -1,24 +0,0 @@ -#include -#include - -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/works/solutions/acwing/1209.cpp b/works/solutions/acwing/1209.cpp deleted file mode 100644 index 3f3ff7a..0000000 --- a/works/solutions/acwing/1209.cpp +++ /dev/null @@ -1,48 +0,0 @@ -#include -#include -#include - -int number; -int count = 0; -std::array used{false}; -std::array 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/works/solutions/acwing/1210.cpp b/works/solutions/acwing/1210.cpp deleted file mode 100644 index 4c9c0ba..0000000 --- a/works/solutions/acwing/1210.cpp +++ /dev/null @@ -1,37 +0,0 @@ -#include - -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/works/solutions/acwing/1211.cpp b/works/solutions/acwing/1211.cpp deleted file mode 100644 index 18c564e..0000000 --- a/works/solutions/acwing/1211.cpp +++ /dev/null @@ -1,38 +0,0 @@ -#include -#include - -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/works/solutions/acwing/1212.cpp b/works/solutions/acwing/1212.cpp deleted file mode 100644 index e60e993..0000000 --- a/works/solutions/acwing/1212.cpp +++ /dev/null @@ -1,46 +0,0 @@ -#include - -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/works/solutions/acwing/1215.cpp b/works/solutions/acwing/1215.cpp deleted file mode 100644 index d6832b3..0000000 --- a/works/solutions/acwing/1215.cpp +++ /dev/null @@ -1,59 +0,0 @@ -#include -#include - -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/works/solutions/acwing/1216.cpp b/works/solutions/acwing/1216.cpp deleted file mode 100644 index 61d1848..0000000 --- a/works/solutions/acwing/1216.cpp +++ /dev/null @@ -1,19 +0,0 @@ -#include - -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/works/solutions/acwing/1217.cpp b/works/solutions/acwing/1217.cpp deleted file mode 100644 index e729547..0000000 --- a/works/solutions/acwing/1217.cpp +++ /dev/null @@ -1,67 +0,0 @@ -#include -#include - -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/works/solutions/acwing/1219.cpp b/works/solutions/acwing/1219.cpp deleted file mode 100644 index 9538e94..0000000 --- a/works/solutions/acwing/1219.cpp +++ /dev/null @@ -1,26 +0,0 @@ -#include -#include - -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/works/solutions/acwing/1220.cpp b/works/solutions/acwing/1220.cpp deleted file mode 100644 index 443ed43..0000000 --- a/works/solutions/acwing/1220.cpp +++ /dev/null @@ -1,65 +0,0 @@ -#include -#include - -const int N = 100010; - -struct Node { - int w; - std::vector 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/works/solutions/acwing/1221.cpp b/works/solutions/acwing/1221.cpp deleted file mode 100644 index 9ba4229..0000000 --- a/works/solutions/acwing/1221.cpp +++ /dev/null @@ -1,45 +0,0 @@ -#include -#include - -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/works/solutions/acwing/1224.cpp b/works/solutions/acwing/1224.cpp deleted file mode 100644 index 8cdd9f0..0000000 --- a/works/solutions/acwing/1224.cpp +++ /dev/null @@ -1,33 +0,0 @@ -#include -#include - -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/works/solutions/acwing/1226.cpp b/works/solutions/acwing/1226.cpp deleted file mode 100644 index cbfea98..0000000 --- a/works/solutions/acwing/1226.cpp +++ /dev/null @@ -1,55 +0,0 @@ -#include - -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/works/solutions/acwing/1227.cpp b/works/solutions/acwing/1227.cpp deleted file mode 100644 index ff14be2..0000000 --- a/works/solutions/acwing/1227.cpp +++ /dev/null @@ -1,50 +0,0 @@ -#include - -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/works/solutions/acwing/1229.cpp b/works/solutions/acwing/1229.cpp deleted file mode 100644 index e3b16ba..0000000 --- a/works/solutions/acwing/1229.cpp +++ /dev/null @@ -1,106 +0,0 @@ -#include -#include -#include - -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 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/works/solutions/acwing/1230.cpp b/works/solutions/acwing/1230.cpp deleted file mode 100644 index 958cbdd..0000000 --- a/works/solutions/acwing/1230.cpp +++ /dev/null @@ -1,36 +0,0 @@ -#include - -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/works/solutions/acwing/1233.cpp b/works/solutions/acwing/1233.cpp deleted file mode 100644 index 117b2fb..0000000 --- a/works/solutions/acwing/1233.cpp +++ /dev/null @@ -1,69 +0,0 @@ -#include -#include - -const int M = 1010; - -int N; -char map[M][M]; -bool visited[M][M]; - -int not_sink_count; - -const std::pair 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/works/solutions/acwing/1236.cpp b/works/solutions/acwing/1236.cpp deleted file mode 100644 index a89a890..0000000 --- a/works/solutions/acwing/1236.cpp +++ /dev/null @@ -1,54 +0,0 @@ -#include - -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/works/solutions/acwing/1237.cpp b/works/solutions/acwing/1237.cpp deleted file mode 100644 index a3b8810..0000000 --- a/works/solutions/acwing/1237.cpp +++ /dev/null @@ -1,49 +0,0 @@ -#include -#include - -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/works/solutions/acwing/1238.cpp b/works/solutions/acwing/1238.cpp deleted file mode 100644 index 2c9d899..0000000 --- a/works/solutions/acwing/1238.cpp +++ /dev/null @@ -1,56 +0,0 @@ -#include -#include -#include - -const int M = 100010; - -int N, D, K; - -std::map> vote_map; - -bool check(const std::multiset &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/works/solutions/acwing/1239.cpp b/works/solutions/acwing/1239.cpp deleted file mode 100644 index c670cd4..0000000 --- a/works/solutions/acwing/1239.cpp +++ /dev/null @@ -1,52 +0,0 @@ -#include -#include - -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/works/solutions/acwing/1240.cpp b/works/solutions/acwing/1240.cpp deleted file mode 100644 index 8ebae33..0000000 --- a/works/solutions/acwing/1240.cpp +++ /dev/null @@ -1,42 +0,0 @@ -#include - -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/works/solutions/acwing/1245.cpp b/works/solutions/acwing/1245.cpp deleted file mode 100644 index ba51a8f..0000000 --- a/works/solutions/acwing/1245.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include - -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/works/solutions/acwing/1246.cpp b/works/solutions/acwing/1246.cpp deleted file mode 100644 index 5c0454c..0000000 --- a/works/solutions/acwing/1246.cpp +++ /dev/null @@ -1,34 +0,0 @@ -#include -#include -#include - -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/works/solutions/acwing/1247.cpp b/works/solutions/acwing/1247.cpp deleted file mode 100644 index 1fd4412..0000000 --- a/works/solutions/acwing/1247.cpp +++ /dev/null @@ -1,39 +0,0 @@ -#include -#include - -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/works/solutions/acwing/2-2.cpp b/works/solutions/acwing/2-2.cpp deleted file mode 100644 index fb0fb3b..0000000 --- a/works/solutions/acwing/2-2.cpp +++ /dev/null @@ -1,25 +0,0 @@ -#include -#include - -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/works/solutions/acwing/2.cpp b/works/solutions/acwing/2.cpp deleted file mode 100644 index 1a75c19..0000000 --- a/works/solutions/acwing/2.cpp +++ /dev/null @@ -1,30 +0,0 @@ -#include -#include - -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/works/solutions/acwing/2065.cpp b/works/solutions/acwing/2065.cpp deleted file mode 100644 index a0c47c2..0000000 --- a/works/solutions/acwing/2065.cpp +++ /dev/null @@ -1,16 +0,0 @@ -#include - -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/works/solutions/acwing/2066.cpp b/works/solutions/acwing/2066.cpp deleted file mode 100644 index 7a6132b..0000000 --- a/works/solutions/acwing/2066.cpp +++ /dev/null @@ -1,21 +0,0 @@ -#include -#include - -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/works/solutions/acwing/2067.cpp b/works/solutions/acwing/2067.cpp deleted file mode 100644 index 3ebd61d..0000000 --- a/works/solutions/acwing/2067.cpp +++ /dev/null @@ -1,22 +0,0 @@ -#include - -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/works/solutions/acwing/2068.cpp b/works/solutions/acwing/2068.cpp deleted file mode 100644 index 592f43f..0000000 --- a/works/solutions/acwing/2068.cpp +++ /dev/null @@ -1,57 +0,0 @@ -#include -#include -#include -#include - -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/works/solutions/acwing/2069.cpp b/works/solutions/acwing/2069.cpp deleted file mode 100644 index fbfa6d2..0000000 --- a/works/solutions/acwing/2069.cpp +++ /dev/null @@ -1,82 +0,0 @@ -#include -#include - -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/works/solutions/acwing/3-2.cpp b/works/solutions/acwing/3-2.cpp deleted file mode 100644 index c099838..0000000 --- a/works/solutions/acwing/3-2.cpp +++ /dev/null @@ -1,25 +0,0 @@ -#include -#include - -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/works/solutions/acwing/3.cpp b/works/solutions/acwing/3.cpp deleted file mode 100644 index 21bd8dc..0000000 --- a/works/solutions/acwing/3.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include -#include - -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/works/solutions/acwing/4.cpp b/works/solutions/acwing/4.cpp deleted file mode 100644 index 3270402..0000000 --- a/works/solutions/acwing/4.cpp +++ /dev/null @@ -1,51 +0,0 @@ -#include -#include - -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/works/solutions/acwing/5.cpp b/works/solutions/acwing/5.cpp deleted file mode 100644 index a88fba6..0000000 --- a/works/solutions/acwing/5.cpp +++ /dev/null @@ -1,49 +0,0 @@ -#include -#include - -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/works/solutions/acwing/7.cpp b/works/solutions/acwing/7.cpp deleted file mode 100644 index fcc0fb1..0000000 --- a/works/solutions/acwing/7.cpp +++ /dev/null @@ -1,54 +0,0 @@ -#include -#include - -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/works/solutions/acwing/8.cpp b/works/solutions/acwing/8.cpp deleted file mode 100644 index f62d21e..0000000 --- a/works/solutions/acwing/8.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include -#include - -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 -- cgit v1.2.3