All problems were invented MikeMirzayanov and developed by me Supermagzzz and Stepavly.
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int w, h, n;
cin >> w >> h >> n;
int res = 1;
while (w % 2 == 0) {
w /= 2;
res *= 2;
}
while (h % 2 == 0) {
h /= 2;
res *= 2;
}
cout << (res >= n ? "YES\n" : "NO\n");
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n;
cin >> n;
int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < n; i++) {
int c;
cin >> c;
if (c == 1) {
cnt1++;
} else {
cnt2++;
}
}
if ((cnt1 + 2 * cnt2) % 2 != 0) {
cout << "NO\n";
} else {
int sum = (cnt1 + 2 * cnt2) / 2;
if (sum % 2 == 0 || (sum % 2 == 1 && cnt1 != 0)) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) {
cin >> x;
}
vector<int> dp(n);
for (int i = n - 1; i >= 0; i--) {
dp[i] = a[i];
int j = i + a[i];
if (j < n) {
dp[i] += dp[j];
}
}
cout << *max_element(dp.begin(), dp.end()) << endl;
}
int main() {
int tests;
cin >> tests;
while (tests-- > 0) {
solve();
}
return 0;
}
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n;
cin >> n;
vector<int> v(n);
for (int &e : v) {
cin >> e;
}
sort(v.rbegin(), v.rend());
ll ans = 0;
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
if (v[i] % 2 == 0) {
ans += v[i];
}
} else {
if (v[i] % 2 == 1) {
ans -= v[i];
}
}
}
if (ans == 0) {
cout << "Tie\n";
} else if (ans > 0) {
cout << "Alice\n";
} else {
cout << "Bob\n";
}
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
struct man {
int h, w, id;
};
bool operator<(const man &a, const man &b) {
return tie(a.h, a.w, a.id) < tie(b.h, b.w, b.id);
}
struct my_min {
pii mn1, mn2;
};
vector<pair<int, my_min>> createPrefMins(const vector<man>& a) {
vector<pair<int, my_min>> prefMin;
my_min curMin{pii(INT_MAX, -1), pii(INT_MAX, -1)};
for (auto x : a) {
if (x.w < curMin.mn1.first) {
curMin.mn2 = curMin.mn1;
curMin.mn1 = pii(x.w, x.id);
} else {
curMin.mn2 = min(curMin.mn2, pii(x.w, x.id));
}
prefMin.emplace_back(x.h, curMin);
}
return prefMin;
}
int findAny(const vector<pair<int, my_min>> &mins, int h, int w, int id) {
int l = -1, r = (int) mins.size();
while (r - l > 1) {
int m = (l + r) / 2;
if (mins[m].first < h) {
l = m;
} else {
r = m;
}
}
if (l == -1) {
return -1;
}
auto mn1 = mins[l].second.mn1;
auto mn2 = mins[l].second.mn2;
if (mn1.second != id) {
return mn1.first < w ? mn1.second + 1 : -1;
}
return mn2.first < w ? mn2.second + 1 : -1;
}
void solve() {
int n;
cin >> n;
vector<man> hor, ver;
vector<pii> a;
for (int i = 0; i < n; i++) {
int h, w;
cin >> h >> w;
hor.push_back({h, w, i});
ver.push_back({w, h, i});
a.emplace_back(h, w);
}
sort(hor.begin(), hor.end());
sort(ver.begin(), ver.end());
auto horMins = createPrefMins(hor);
auto verMins = createPrefMins(ver);
for (int i = 0; i < n; i++) {
auto[h, w] = a[i];
int id = findAny(horMins, h, w, i);
if (id == -1) {
id = findAny(verMins, h, w, i);
}
cout << id << " ";
}
cout << endl;
}
int main() {
int tests;
cin >> tests;
while (tests-- > 0) {
solve();
}
return 0;
}
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n, m;
cin >> n >> m;
map<int, int> v;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
v[y] |= (1 << (x - 1));
}
const int FULL = 3;
v[2e9] = FULL;
int hasLast = 0, lastColor = 0;
for (auto[x, mask] : v) {
if (mask != FULL && hasLast) {
int color = (x + mask) % 2;
if (lastColor == color) {
cout << "NO\n";
return;
} else {
hasLast = false;
}
} else if (mask == FULL && hasLast) {
cout << "NO\n";
return;
} else if (mask != FULL) {
lastColor = (x + mask) % 2;
hasLast = true;
}
}
cout << "YES\n";
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
vector<int> calcDist(vector<vector<int>> const &g) {
vector<int> dist(g.size(), -1);
dist[1] = 0;
queue<int> pq;
pq.push(1);
while (!pq.empty()) {
int u = pq.front();
pq.pop();
for (int v : g[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
pq.push(v);
}
}
}
return dist;
}
void dfs(int u, vector<vector<int>> const &g, vector<int> const &dist, vector<int> &dp, vector<bool> &used) {
used[u] = true;
dp[u] = dist[u];
for (int v : g[u]) {
if (!used[v] && dist[u] < dist[v]) {
dfs(v, g, dist, dp, used);
}
if (dist[u] < dist[v]) {
dp[u] = min(dp[u], dp[v]);
} else {
dp[u] = min(dp[u], dist[v]);
}
}
}
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
}
vector<int> dist = calcDist(g);
vector<int> dp(n + 1);
vector<bool> used(n + 1);
dfs(1, g, dist, dp, used);
for (int i = 1; i <= n; i++) {
cout << dp[i] << " ";
}
cout << endl;
}
int main() {
int tests;
cin >> tests;
while (tests-- > 0) {
solve();
}
return 0;
}