diff options
39 files changed, 968 insertions, 0 deletions
diff --git a/codeforces/HalloumiBoxes/main.rs b/codeforces/HalloumiBoxes/main.rs new file mode 100644 index 0000000..cbc73cd --- /dev/null +++ b/codeforces/HalloumiBoxes/main.rs @@ -0,0 +1,32 @@ +#[allow(dead_code)] +fn read<T: std::str::FromStr>() -> T { + let mut s = String::new(); + std::io::stdin().read_line(&mut s).ok(); + s.trim().parse().ok().unwrap() +} + +#[allow(dead_code)] +fn read_vec<T: std::str::FromStr>() -> Vec<T> { + read::<String>() + .split_whitespace() + .map(|e| e.parse().ok().unwrap()) + .collect() +} + +#[allow(dead_code)] +fn read_mat<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> { + (0..n).map(|_| read_vec()).collect() +} + +fn solve() { + let (k, n) = (read::<usize>(), read::<usize>()); + let mut v = read_vec::<usize>(); +} + +fn main() { + let mut tt = read::<u64>(); + while tt > 0 { + solve(); + tt -= 1; + } +} diff --git a/codeforces/HalloumiBoxes/rust-project.json b/codeforces/HalloumiBoxes/rust-project.json new file mode 100644 index 0000000..a195582 --- /dev/null +++ b/codeforces/HalloumiBoxes/rust-project.json @@ -0,0 +1,11 @@ +{ + "sysroot": "/home/omar/.rustup/toolchains/stable-x86_64-unknown-linux-gnu", + "sysroot_src": "/home/omar/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/", + "crates": [ + { + "root_module": "main.rs", + "edition": "2021", + "deps": [] + } + ] +} diff --git a/codeforces/MovingChips/main.cpp b/codeforces/MovingChips/main.cpp new file mode 100755 index 0000000..f847d53 --- /dev/null +++ b/codeforces/MovingChips/main.cpp @@ -0,0 +1,104 @@ +#include <algorithm> +#include <bits/stdc++.h> + +using namespace std; + +using ll = long long; +using pii = pair<int, int>; +using vpii = vector<pii>; +using vi = vector<int>; +using vll = vector<long long>; +using mpii = map<int, int>; +using mpll = map<ll, ll>; +using db = long double; + +#define pb push_back +#define all(x) (x).begin(), (x).end() +#define rall(x) (x).rbegin(), (x).rend() +#define lb lower_bound +#define ub upper_bound +#define make_unique(x) \ + sort(all((x))); \ + (x).resize(unique(all((x))) - (x).begin()) +#define ceil(a, b) ((a) + (b)-1) / (b) + +const int mod = (int)1e9 + 7; +const db pi = acos((db)-1); +const int dx[4]{1, 0, -1, 0}; +const int dy[4]{0, 1, 0, -1}; + +#ifdef LOCAL +#include "debug.h" +#else +#define dbg(...) 42 +#endif + +/* stuff you should look for: + --------------------------- + * special cases (n=1?) + * int overflow, array bounds + * do smth instead of nothing and stay organized + * WRITE STUFF DOWN + * DON'T GET STUCK ON ONE APPROACH + */ + +bool isChip(vi v) { + v.resize(unique(all(v)) - v.begin()); + int n = v.size(); + if (n == 2) { + return true; + } else if (n == 1 && v[0] == 1) { + return true; + } else if (n == 3 && v[0] == 0 && v[1] == 1 && v[2] == 0) { + return true; + } else { + return false; + } +} + +int rfind(vi &v) { + int n = v.size(); + for (int i = n - 1; i >= 0; --i) { + if (v[i] == 1) { + return i; + } + } + return -1; +} + +int helper(vi &v, int idx) { + int n = v.size(); + for (int i = idx; i >= 0; --i) { + if (v[i] == 0) { + return i; + } + } + return -1; +} + +void solve() { + int n; + cin >> n; + vi v(n); + for (auto &x : v) { + cin >> x; + } + int cnt = 0; + while (!isChip(v)) { + auto last_one = rfind(v); + auto first_zero_before_last_one = helper(v, last_one); + swap(v[last_one], v[first_zero_before_last_one]); + cnt++; + } + cout << cnt << '\n'; +} + +int main() { + ios_base::sync_with_stdio(false); + cin.tie(NULL); + int tt; + cin >> tt; + while (tt--) { + solve(); + } +} diff --git a/codeforces/MovingChips/main_input0.txt b/codeforces/MovingChips/main_input0.txt new file mode 100644 index 0000000..5945cde --- /dev/null +++ b/codeforces/MovingChips/main_input0.txt @@ -0,0 +1,11 @@ +5 +8 +0 1 1 1 0 1 1 0 +6 +0 1 0 0 0 0 +6 +1 1 1 1 1 1 +5 +1 0 1 0 1 +9 +0 1 1 0 0 0 1 1 0 diff --git a/codeforces/MovingChips/main_output0.txt b/codeforces/MovingChips/main_output0.txt new file mode 100644 index 0000000..dff77c1 --- /dev/null +++ b/codeforces/MovingChips/main_output0.txt @@ -0,0 +1,5 @@ +1 +0 +0 +2 +3 diff --git a/codeforces/TurtleMath/main.cpp b/codeforces/TurtleMath/main.cpp new file mode 100755 index 0000000..c602443 --- /dev/null +++ b/codeforces/TurtleMath/main.cpp @@ -0,0 +1,82 @@ +#include <bits/stdc++.h> + +using namespace std; + +using ll = long long; +using pii = pair<int, int>; +using vpii = vector<pii>; +using vi = vector<int>; +using vll = vector<long long>; +using mpii = map<int, int>; +using mpll = map<ll, ll>; +using db = long double; + +#define pb push_back +#define all(x) (x).begin(), (x).end() +#define rall(x) (x).rbegin(), (x).rend() +#define lb lower_bound +#define ub upper_bound +#define make_unique(x) \ + sort(all((x))); \ + (x).resize(unique(all((x))) - (x).begin()) +#define ceil(a, b) ((a) + (b)-1) / (b) + +const int mod = (int)1e9 + 7; +const db pi = acos((db)-1); +const int dx[4]{1, 0, -1, 0}; +const int dy[4]{0, 1, 0, -1}; + +#ifdef LOCAL +#include "debug.h" +#else +#define dbg(...) 42 +#endif + +/* stuff you should look for: + --------------------------- + * special cases (n=1?) + * int overflow, array bounds + * do smth instead of nothing and stay organized + * WRITE STUFF DOWN + * DON'T GET STUCK ON ONE APPROACH + */ + +set<int> st1; + +void solve() { + int n; + cin >> n; + vector<int> v(n); + long long sum = 0; + for (auto &x : v) { + cin >> x; + sum += x; + } + if (sum % 3 == 0) { + cout << 0 << '\n'; + return; + } else { + if (sum % 3 == 1) { + for (int i = 0; i < n; ++i) { + if (st1.count(v[i])) { + cout << 1 << '\n'; + return; + } + } + } + } + cout << 3 - (sum % 3) << '\n'; +} + +int main() { + for (int i = 0; i < 1e5; i++) { + st1.insert(1 + i * 3); + } + ios_base::sync_with_stdio(false); + cin.tie(NULL); + int tt; + cin >> tt; + while (tt--) { + solve(); + } +} diff --git a/contests/Round928/A/main.cpp b/contests/Round928/A/main.cpp new file mode 100755 index 0000000..539fdb0 --- /dev/null +++ b/contests/Round928/A/main.cpp @@ -0,0 +1,54 @@ +#include <bits/stdc++.h> + +using namespace std; + +using ll = long long; +using pii = pair<int, int>; +using vpii = vector<pii>; +using vi = vector<int>; +using vll = vector<long long>; +using mpii = map<int, int>; +using mpll = map<ll, ll>; +using db = long double; + +#define pb push_back +#define all(x) (x).begin(), (x).end() +#define rall(x) (x).rbegin(), (x).rend() +#define lb lower_bound +#define ub upper_bound +#define make_unique(x) \ + sort(all((x))); \ + (x).resize(unique(all((x))) - (x).begin()) +#define ceil(a, b) ((a) + (b)-1) / (b) + +const int mod = (int)1e9 + 7; +const db pi = acos((db)-1); +const int dx[4]{1, 0, -1, 0}; +const int dy[4]{0, 1, 0, -1}; + +#ifdef LOCAL +#include "debug.h" +#else +#define dbg(...) 42 +#endif + +/* stuff you should look for: + --------------------------- + * special cases (n=1?) + * int overflow, array bounds + * do smth instead of nothing and stay organized + * WRITE STUFF DOWN + * DON'T GET STUCK ON ONE APPROACH + */ + +void solve() { <()> } + +int main() { + ios_base::sync_with_stdio(false); + cin.tie(NULL); + int tt; + cin >> tt; + while (tt--) { + solve(); + } +} diff --git a/contests/Round928/B/main.cpp b/contests/Round928/B/main.cpp new file mode 100755 index 0000000..539fdb0 --- /dev/null +++ b/contests/Round928/B/main.cpp @@ -0,0 +1,54 @@ +#include <bits/stdc++.h> + +using namespace std; + +using ll = long long; +using pii = pair<int, int>; +using vpii = vector<pii>; +using vi = vector<int>; +using vll = vector<long long>; +using mpii = map<int, int>; +using mpll = map<ll, ll>; +using db = long double; + +#define pb push_back +#define all(x) (x).begin(), (x).end() +#define rall(x) (x).rbegin(), (x).rend() +#define lb lower_bound +#define ub upper_bound +#define make_unique(x) \ + sort(all((x))); \ + (x).resize(unique(all((x))) - (x).begin()) +#define ceil(a, b) ((a) + (b)-1) / (b) + +const int mod = (int)1e9 + 7; +const db pi = acos((db)-1); +const int dx[4]{1, 0, -1, 0}; +const int dy[4]{0, 1, 0, -1}; + +#ifdef LOCAL +#include "debug.h" +#else +#define dbg(...) 42 +#endif + +/* stuff you should look for: + --------------------------- + * special cases (n=1?) + * int overflow, array bounds + * do smth instead of nothing and stay organized + * WRITE STUFF DOWN + * DON'T GET STUCK ON ONE APPROACH + */ + +void solve() { <()> } + +int main() { + ios_base::sync_with_stdio(false); + cin.tie(NULL); + int tt; + cin >> tt; + while (tt--) { + solve(); + } +} diff --git a/contests/Round928/C/main.cpp b/contests/Round928/C/main.cpp new file mode 100755 index 0000000..539fdb0 --- /dev/null +++ b/contests/Round928/C/main.cpp @@ -0,0 +1,54 @@ +#include <bits/stdc++.h> + +using namespace std; + +using ll = long long; +using pii = pair<int, int>; +using vpii = vector<pii>; +using vi = vector<int>; +using vll = vector<long long>; +using mpii = map<int, int>; +using mpll = map<ll, ll>; +using db = long double; + +#define pb push_back +#define all(x) (x).begin(), (x).end() +#define rall(x) (x).rbegin(), (x).rend() +#define lb lower_bound +#define ub upper_bound +#define make_unique(x) \ + sort(all((x))); \ + (x).resize(unique(all((x))) - (x).begin()) +#define ceil(a, b) ((a) + (b)-1) / (b) + +const int mod = (int)1e9 + 7; +const db pi = acos((db)-1); +const int dx[4]{1, 0, -1, 0}; +const int dy[4]{0, 1, 0, -1}; + +#ifdef LOCAL +#include "debug.h" +#else +#define dbg(...) 42 +#endif + +/* stuff you should look for: + --------------------------- + * special cases (n=1?) + * int overflow, array bounds + * do smth instead of nothing and stay organized + * WRITE STUFF DOWN + * DON'T GET STUCK ON ONE APPROACH + */ + +void solve() { <()> } + +int main() { + ios_base::sync_with_stdio(false); + cin.tie(NULL); + int tt; + cin >> tt; + while (tt--) { + solve(); + } +} diff --git a/contests/Round928/D/main.cpp b/contests/Round928/D/main.cpp new file mode 100755 index 0000000..05b3cc4 --- /dev/null +++ b/contests/Round928/D/main.cpp @@ -0,0 +1,106 @@ +#include <algorithm> +#include <bits/stdc++.h> + +using namespace std; + +using ll = long long; +using pii = pair<int, int>; +using vpii = vector<pii>; +using vi = vector<int>; +using vll = vector<long long>; +using mpii = map<int, int>; +using mpll = map<ll, ll>; +using db = long double; + +#define pb push_back +#define all(x) (x).begin(), (x).end() +#define rall(x) (x).rbegin(), (x).rend() +#define lb lower_bound +#define ub upper_bound +#define make_unique(x) \ + sort(all((x))); \ + (x).resize(unique(all((x))) - (x).begin()) +#define ceil(a, b) ((a) + (b)-1) / (b) + +const int mod = (int)1e9 + 7; +const db pi = acos((db)-1); +const int dx[4]{1, 0, -1, 0}; +const int dy[4]{0, 1, 0, -1}; + +#ifdef LOCAL +#include "debug.h" +#else +#define dbg(...) 42 +#endif + +/* stuff you should look for: + --------------------------- + * special cases (n=1?) + * int overflow, array bounds + * do smth instead of nothing and stay organized + * WRITE STUFF DOWN + * DON'T GET STUCK ON ONE APPROACH + */ + +int binarySearch(const std::vector<int> &arr, int target) { + int left = 0; + int right = arr.size() - 1; + + while (left <= right) { + int mid = left + (right - left) / 2; + + if (arr[mid] == target) { + return mid; + } else if (arr[mid] < target) { + left = mid + 1; + } else { + right = mid - 1; + } + } + + return -1; +} + +int negateNumber(int num) { + int signMask = 1 << (sizeof(int) * 8 - 1); + + int inverted = ~num & (signMask - 1); + + return inverted + 1; +} + +void solve() { + random_device rd; + mt19937 gen(rd()); + uniform_int_distribution<> distribution(1, INT_MAX); + int n; + cin >> n; + vi v(n); + for (auto &x : v) { + cin >> x; + } + sort(all(v)); + int ans = 0; + vector<bool> marked(n, false); + for (int i = 0; i < n; i++) { + auto it = binarySearch(v, negateNumber(v[i]) - 1); + if (it != -1) { + ans++; + v[it] = distribution(gen); + marked[i] = true; + marked[it] = true; + } + } + int cnt = count(all(marked), false); + cout << ans + cnt << '\n'; +} + +int main() { + ios_base::sync_with_stdio(false); + cin.tie(NULL); + int tt; + cin >> tt; + while (tt--) { + solve(); + } +} diff --git a/contests/Round928/D/main_input0.txt b/contests/Round928/D/main_input0.txt new file mode 100644 index 0000000..b9e8c65 --- /dev/null +++ b/contests/Round928/D/main_input0.txt @@ -0,0 +1,19 @@ +9 +4 +1 4 3 4 +2 +0 2147483647 +5 +476319172 261956880 2136179468 1671164475 1885526767 +3 +1335890506 811593141 1128223362 +4 +688873446 627404104 1520079543 1458610201 +4 +61545621 2085938026 1269342732 1430258575 +4 +0 0 2147483647 2147483647 +3 +0 0 2147483647 +8 +1858058912 289424735 1858058912 2024818580 1858058912 289424735 122665067 289424735 diff --git a/contests/Round928/D/main_output0.txt b/contests/Round928/D/main_output0.txt new file mode 100644 index 0000000..6572dc5 --- /dev/null +++ b/contests/Round928/D/main_output0.txt @@ -0,0 +1,9 @@ +4 +1 +3 +2 +2 +3 +2 +2 +4 diff --git a/contests/Round928/E/main.cpp b/contests/Round928/E/main.cpp new file mode 100755 index 0000000..539fdb0 --- /dev/null +++ b/contests/Round928/E/main.cpp @@ -0,0 +1,54 @@ +#include <bits/stdc++.h> + +using namespace std; + +using ll = long long; +using pii = pair<int, int>; +using vpii = vector<pii>; +using vi = vector<int>; +using vll = vector<long long>; +using mpii = map<int, int>; +using mpll = map<ll, ll>; +using db = long double; + +#define pb push_back +#define all(x) (x).begin(), (x).end() +#define rall(x) (x).rbegin(), (x).rend() +#define lb lower_bound +#define ub upper_bound +#define make_unique(x) \ + sort(all((x))); \ + (x).resize(unique(all((x))) - (x).begin()) +#define ceil(a, b) ((a) + (b)-1) / (b) + +const int mod = (int)1e9 + 7; +const db pi = acos((db)-1); +const int dx[4]{1, 0, -1, 0}; +const int dy[4]{0, 1, 0, -1}; + +#ifdef LOCAL +#include "debug.h" +#else +#define dbg(...) 42 +#endif + +/* stuff you should look for: + --------------------------- + * special cases (n=1?) + * int overflow, array bounds + * do smth instead of nothing and stay organized + * WRITE STUFF DOWN + * DON'T GET STUCK ON ONE APPROACH + */ + +void solve() { <()> } + +int main() { + ios_base::sync_with_stdio(false); + cin.tie(NULL); + int tt; + cin >> tt; + while (tt--) { + solve(); + } +} diff --git a/contests/Round928/F/main.cpp b/contests/Round928/F/main.cpp new file mode 100755 index 0000000..539fdb0 --- /dev/null +++ b/contests/Round928/F/main.cpp @@ -0,0 +1,54 @@ +#include <bits/stdc++.h> + +using namespace std; + +using ll = long long; +using pii = pair<int, int>; +using vpii = vector<pii>; +using vi = vector<int>; +using vll = vector<long long>; +using mpii = map<int, int>; +using mpll = map<ll, ll>; +using db = long double; + +#define pb push_back +#define all(x) (x).begin(), (x).end() +#define rall(x) (x).rbegin(), (x).rend() +#define lb lower_bound +#define ub upper_bound +#define make_unique(x) \ + sort(all((x))); \ + (x).resize(unique(all((x))) - (x).begin()) +#define ceil(a, b) ((a) + (b)-1) / (b) + +const int mod = (int)1e9 + 7; +const db pi = acos((db)-1); +const int dx[4]{1, 0, -1, 0}; +const int dy[4]{0, 1, 0, -1}; + +#ifdef LOCAL +#include "debug.h" +#else +#define dbg(...) 42 +#endif + +/* stuff you should look for: + --------------------------- + * special cases (n=1?) + * int overflow, array bounds + * do smth instead of nothing and stay organized + * WRITE STUFF DOWN + * DON'T GET STUCK ON ONE APPROACH + */ + +void solve() { <()> } + +int main() { + ios_base::sync_with_stdio(false); + cin.tie(NULL); + int tt; + cin >> tt; + while (tt--) { + solve(); + } +} diff --git a/contests/Round933/A/main.cpp b/contests/Round933/A/main.cpp new file mode 100755 index 0000000..23f4fd3 --- /dev/null +++ b/contests/Round933/A/main.cpp @@ -0,0 +1,74 @@ +#include <bits/stdc++.h> + +using namespace std; + +using ll = long long; +using pii = pair<int, int>; +using vpii = vector<pii>; +using vi = vector<int>; +using vll = vector<long long>; +using mpii = map<int, int>; +using mpll = map<ll, ll>; +using db = long double; + +#define pb push_back +#define all(x) (x).begin(), (x).end() +#define rall(x) (x).rbegin(), (x).rend() +#define lb lower_bound +#define ub upper_bound +#define make_unique(x) \ + sort(all((x))); \ + (x).resize(unique(all((x))) - (x).begin()) +#define ceil(a, b) ((a) + (b)-1) / (b) + +const int mod = (int)1e9 + 7; +const db pi = acos((db)-1); +const int dx[4]{1, 0, -1, 0}; +const int dy[4]{0, 1, 0, -1}; + +#ifdef LOCAL +#include "debug.h" +#else +#define dbg(...) 42 +#endif + +/* stuff you should look for: + --------------------------- + * special cases (n=1?) + * int overflow, array bounds + * do smth instead of nothing and stay organized + * WRITE STUFF DOWN + * DON'T GET STUCK ON ONE APPROACH + */ + +void solve() { + int n, m, k; + cin >> n >> m >> k; + int cnt = 0; + vi b(n); + vi c(m); + for (auto &x : b) { + cin >> x; + } + for (auto &x : c) { + cin >> x; + } + for (int i = 0; i < n; i++) { + for (int j = 0; j < m; j++) { + if (b[i] + c[j] <= k) { + cnt++; + } + } + } + cout << cnt << '\n'; +} + +int main() { + ios_base::sync_with_stdio(false); + cin.tie(NULL); + int tt; + cin >> tt; + while (tt--) { + solve(); + } +} diff --git a/contests/Round933/A/main_input0.txt b/contests/Round933/A/main_input0.txt new file mode 100644 index 0000000..3b4a7e5 --- /dev/null +++ b/contests/Round933/A/main_input0.txt @@ -0,0 +1,13 @@ +4 +4 4 8 +1 5 10 14 +2 1 8 1 +2 3 4 +4 8 +1 2 3 +4 2 7 +1 1 1 1 +2 7 +3 4 2000 +1 1 1 +1 1 1 1 diff --git a/contests/Round933/A/main_output0.txt b/contests/Round933/A/main_output0.txt new file mode 100644 index 0000000..a649b49 --- /dev/null +++ b/contests/Round933/A/main_output0.txt @@ -0,0 +1,4 @@ +6 +0 +4 +12 diff --git a/contests/Round933/B/main.cpp b/contests/Round933/B/main.cpp new file mode 100755 index 0000000..eae9018 --- /dev/null +++ b/contests/Round933/B/main.cpp @@ -0,0 +1,80 @@ +#include <bits/stdc++.h> + +using namespace std; + +using ll = long long; +using pii = pair<int, int>; +using vpii = vector<pii>; +using vi = vector<int>; +using vll = vector<long long>; +using mpii = map<int, int>; +using mpll = map<ll, ll>; +using db = long double; + +#define pb push_back +#define all(x) (x).begin(), (x).end() +#define rall(x) (x).rbegin(), (x).rend() +#define lb lower_bound +#define ub upper_bound +#define make_unique(x) \ + sort(all((x))); \ + (x).resize(unique(all((x))) - (x).begin()) +#define ceil(a, b) ((a) + (b)-1) / (b) + +const int mod = (int)1e9 + 7; +const db pi = acos((db)-1); +const int dx[4]{1, 0, -1, 0}; +const int dy[4]{0, 1, 0, -1}; + +#ifdef LOCAL +#include "debug.h" +#else +#define dbg(...) 42 +#endif + +/* stuff you should look for: + --------------------------- + * special cases (n=1?) + * int overflow, array bounds + * do smth instead of nothing and stay organized + * WRITE STUFF DOWN |