[problem:454092A]
Idea: I_Love_noomaK, prepared: noomaK
Since $$$n \leq 100$$$ this problem can be easily solved by iterating over all pairs.
Although, it can be also solved by taking the maximum between the product of the largest or the smallest two numbers.
using namespace std;
typedef long long ll;
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cout << vars << " = ";
string delim = "";
(..., (cout << delim << values, delim = ", "));
cout << '\n';
}
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
int ans = -2000000;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
ans = max(ans, a[i] * a[j]);
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while(t--) {
solve();
}
}
[problem:454092B]
Idea: noomaK, prepared: noomaK
It's easy to see that the optimal strategy is to sort the queue in ascending or descending order, and then simulate the process.
But it also can be observed that the final answer is always the $$$max(A) - min(A)$$$.
Time complexity, either $$$O(N)$$$ or $$$O(NlogN)$$$ using sort.
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cout << vars << " = ";
string delim = "";
(..., (cout << delim << values, delim = ", "));
cout << '\n';
}
void solve() {
int n;
cin >> n;
int mn = 1e9, mx = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
mn = min(mn, x);
mx = max(mx, x);
}
cout << mx - mn << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while(t--) {
solve();
}
}
[problem:454092C]
Idea: noomaK, prepared: noomaK
It can be seen that if there is any number greater than the current mex or occured twice in the array, the answer won't change. Otherwise, it's always better to remove the largest number that occurred once and then calculate the mex.
Time complexity $$$O(N)$$$.
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cout << vars << " = ";
string delim = "";
(..., (cout << delim << values, delim = ", "));
cout << '\n';
}
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) {
cin >> x;
}
vector<int> freq(n);
sort(a.begin(), a.end());
int mex = 0;
int ok = 0;
for (int x : a) {
if (x == mex) ++mex;
if (x < n) ++freq[x];
else ok = 1;
}
for (int x : a) if (x > mex) ok = 1;
for (int i = 0; i < n; ++i) if (freq[i] > 1) ok = 1;
if (ok) {
cout << mex << '\n';
return;
}
for (int i = n - 1; i >= 0; --i) {
if (freq[i] == 1) {
cout << i << '\n';
return;
}
}
assert(false);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while(t--) {
solve();
}
}
[problem:454092D]
Idea: I_Love_noomaK, prepared: noomaK and I_Love_noomaK
We can see that in order for the OR to be not equal $$$x$$$ there has to be at least $$$1$$$ bit that's in a different state in $$$x$$$ than in the OR.
So assuming that the OR of the array is equal to $$$x$$$ because otherwise the answer is $$$n$$$, we can count the number of times the $$$i$$$-th bit is on in the array, then we take the $$$mn_bit$$$ as the minimum bit of $$$x$$$ occurring in $$$a$$$, we delete all the elements having this bit on and this our answer.
Time complexity $$$O(N * log2(A))$$$, where $$$A$$$ is the maximum element in the array.
#include "bits/stdc++.h"
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cout << vars << " = ";
string delim = "";
(..., (cout << delim << values, delim = ", "));
cout << '\n';
}
const int N = 1e5 * 30;
const int K = 2;
const int mod = 1e9 + 7;
const ll INF = 1e9;
void oh_shit_here_we_go_again() {
int n, x; cin >> n >> x;
vector<int> v(n);
for(auto &x : v) cin >> x;
for(int i = 0; i < n; ++i) {
if(v[i] & ~x) {
cout << n << '\n';
return;
}
}
vector<int> frq(32);
for(int i = 0; i < n; ++i) {
for(int mask = 0; mask <= 30; mask++) {
if(v[i] & (1 << mask)) {
frq[mask]++;
}
}
}
int mn = INF, mn_bit = -1;
for(int i = 0; i < 31; ++i) {
if(x & (1 << i)) {
if(frq[i] < mn) {
mn = frq[i];
mn_bit = i;
}
}
}
int cnt = 0;
for(int i = 0; i < n; ++i) {
if(v[i] & (1 << mn_bit)) continue;
cnt++;
}
cout << cnt << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int tt = 1;
// freopen("cross.in","r",stdin);
// cin>>tt;
while(tt--) {
oh_shit_here_we_go_again();
}
}
[problem:454092E]
Idea: noomaK, prepared: noomaK
Two Pointers ~~~~~
include "bits/stdc++.h"
using namespace std;
typedef long long ll;
define deb(...) logger(#__VA_ARGS__, VA_ARGS)
template<typename ...Args> void logger(string vars, Args&&... values) { cout << vars << " = "; string delim = ""; (..., (cout << delim << values, delim = ", ")); cout << '\n'; }
void solve() { int n; cin >> n; vector a(n); for (int &x : a) cin >> x; int j = 0, cp = 0, cn = 0; ll ans = 0; for (int i = 0; i < n; ++i) { cp += (a[i] == 1); cn += (a[i] == -1); while (max(cp, cn) > 1) { cp -= (a[j] == 1); cn -= (a[j] == -1); ++j; } ans += (i — j); } cout << ans << '\n'; }
int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; cin >> t; while(t--) { solve(); } }
~~~~~
Binary Search ~~~~~
include "bits/stdc++.h"
using namespace std;
typedef long long ll;
define deb(...) logger(#__VA_ARGS__, VA_ARGS)
template<typename ...Args> void logger(string vars, Args&&... values) { cout << vars << " = "; string delim = ""; (..., (cout << delim << values, delim = ", ")); cout << '\n'; }
void solve() { int n; cin >> n; vector pos(n), neg(n); for (int i = 0; i < n; ++i) { int x; cin >> x; if (x == 1) pos[i] += 1; else if (x == -1) neg[i] += 1; if (i > 0) { pos[i] += pos[i — 1]; neg[i] += neg[i — 1]; } } auto get = [&] (int l, int r, vector &x) { return x[r] — (l ? x[l — 1] : 0); }; auto check = [&] (int l, int r) { assert(l <= r && r < n); return get(l, r, pos) <= 1 && get(l, r, neg) <= 1; }; ll ans = 0; for (int i = 0; i < n — 1; ++i) { int l = 2, r = n — i, best = 1; while (l <= r) { int m = (l + r) / 2; if (check(i, i + m — 1)) { l = m + 1; best = m; } else r = m — 1; } ans += best — 1; } cout << ans << '\n'; }
int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; cin >> t; while(t--) { solve(); } }
~~~~~
[problem:454092F]
Idea: noomaK, prepared: noomaK
A lot of people would think this is a clever a problem that needs a lot of observations, but the only observation that matters is to realize that every turn the length of the array will be halved.
So we can just brute force the game and see who wins, at each turn we can try not reverse and reversing and if any of the ways lead to the other player losing we win, otherwise we lose.
Time Complexity: $$$O(Nlog(N))$$$.
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cout << vars << " = ";
string delim = "";
(..., (cout << delim << values, delim = ", "));
cout << '\n';
}
int ans;
bool dfs(vector<ll> a, int turn) {
int n = a.size();
if (n == 1) {
return a[0] % 2 == turn;
}
vector<ll> b;
for (int i = 0; i < n; i += 2) {
if (i + 1 < n) b.push_back((a[i] + a[i + 1] + 1) / 2);
else b.push_back(a[i]);
}
if (!dfs(b, !turn)) return true;
b.clear();
reverse(a.begin(), a.end());
for (int i = 0; i < n; i += 2) {
if (i + 1 < n) b.push_back((a[i] + a[i + 1] + 1) / 2);
else b.push_back(a[i]);
}
return !dfs(b, !turn);
}
void solve() {
int n;
cin >> n;
vector<ll> a(n);
for (ll &x : a) cin >> x;
cout << (dfs(a, 1) ? "Ahmad" : "Monther") << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while(t--) {
solve();
}
}
This problem was supposed to be div3D, but I thought it would be a little harder than that, and some how it seems like it's way harder than div3F too.
[problem:454092G1]
Idea: noomaK, prepared: noomaK
~~~~~ ~~~~~
[problem:454092G2]
Idea: noomaK, prepared: noomaK
Will be added soon.
~~~~~ ~~~~~
