From c1bbcb6c2a6d02a4ac06d3c41afcfc51993ec1d3 Mon Sep 17 00:00:00 2001 From: omagdy7 Date: Thu, 14 Mar 2024 00:22:45 +0200 Subject: Solved 3 problems in the last Div3 --- contests/Round928/A/main.cpp | 54 ++++++++++++++++++ contests/Round928/B/main.cpp | 54 ++++++++++++++++++ contests/Round928/C/main.cpp | 54 ++++++++++++++++++ contests/Round928/D/main.cpp | 106 +++++++++++++++++++++++++++++++++++ contests/Round928/D/main_input0.txt | 19 +++++++ contests/Round928/D/main_output0.txt | 9 +++ contests/Round928/E/main.cpp | 54 ++++++++++++++++++ contests/Round928/F/main.cpp | 54 ++++++++++++++++++ 8 files changed, 404 insertions(+) create mode 100755 contests/Round928/A/main.cpp create mode 100755 contests/Round928/B/main.cpp create mode 100755 contests/Round928/C/main.cpp create mode 100755 contests/Round928/D/main.cpp create mode 100644 contests/Round928/D/main_input0.txt create mode 100644 contests/Round928/D/main_output0.txt create mode 100755 contests/Round928/E/main.cpp create mode 100755 contests/Round928/F/main.cpp (limited to 'contests/Round928') 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 + +using namespace std; + +using ll = long long; +using pii = pair; +using vpii = vector; +using vi = vector; +using vll = vector; +using mpii = map; +using mpll = map; +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 + +using namespace std; + +using ll = long long; +using pii = pair; +using vpii = vector; +using vi = vector; +using vll = vector; +using mpii = map; +using mpll = map; +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 + +using namespace std; + +using ll = long long; +using pii = pair; +using vpii = vector; +using vi = vector; +using vll = vector; +using mpii = map; +using mpll = map; +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 +#include + +using namespace std; + +using ll = long long; +using pii = pair; +using vpii = vector; +using vi = vector; +using vll = vector; +using mpii = map; +using mpll = map; +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 &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 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 + +using namespace std; + +using ll = long long; +using pii = pair; +using vpii = vector; +using vi = vector; +using vll = vector; +using mpii = map; +using mpll = map; +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 + +using namespace std; + +using ll = long long; +using pii = pair; +using vpii = vector; +using vi = vector; +using vll = vector; +using mpii = map; +using mpll = map; +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(); + } +} -- cgit v1.2.3