All ideas except the problem C belong to MikeMirzayanov.
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
int cnto = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
cnto += x & 1;
}
cout << min(cnto, n - cnto) << endl;
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
int n;
cin >> n;
vector<int> a(n);
forn(i, n)
cin >> a[i];
int ans = 0;
int right_min = INT_MAX;
for (int i = n - 1; i >= 0; i--) {
if (a[i] > right_min)
ans++;
right_min = min(right_min, a[i]);
}
cout << ans << endl;
}
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int q;
cin >> q;
forn(i, q) {
long long n, m;
cin >> n >> m;
n = n / m;
vector<int> digits(10);
forn(i, 10)
digits[i] = ((i + 1) * m) % 10;
long long sum = 0;
forn(i, n % 10)
sum += digits[i];
cout << sum + n / 10 * accumulate(digits.begin(), digits.end(), 0LL) << endl;
}
}
1213D1 - Equalizing by Division (easy version)
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<int> poss;
for (int i = 0; i < n; ++i) {
int x = a[i];
while (x > 0) {
poss.push_back(x);
x /= 2;
}
}
int ans = 1e9;
for (auto res : poss) {
vector<int> cnt;
for (int i = 0; i < n; ++i) {
int x = a[i];
int cur = 0;
while (x > res) {
x /= 2;
++cur;
}
if (x == res) {
cnt.push_back(cur);
}
}
if (int(cnt.size()) < k) continue;
sort(cnt.begin(), cnt.end());
ans = min(ans, accumulate(cnt.begin(), cnt.begin() + k, 0));
}
cout << ans << endl;
return 0;
}
1213D2 - Equalizing by Division (hard version)
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<vector<int>> vals(200 * 1000 + 11);
for (int i = 0; i < n; ++i) {
int x = a[i];
int cur = 0;
while (x > 0) {
vals[x].push_back(cur);
x /= 2;
++cur;
}
}
int ans = 1e9;
for (int i = 0; i <= 200 * 1000; ++i) {
sort(vals[i].begin(), vals[i].end());
if (int(vals[i].size()) < k) continue;
ans = min(ans, accumulate(vals[i].begin(), vals[i].begin() + k, 0));
}
cout << ans << endl;
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
string s, t;
cin >> n >> s >> t;
string abc = "abc";
vector<string> res;
do {
string cur;
for (int i = 0; i < n; ++i) cur += abc;
res.push_back(cur);
res.push_back(string(n, abc[0]) + string(n, abc[1]) + string(n, abc[2]));
} while (next_permutation(abc.begin(), abc.end()));
for (auto str : res) {
if (str.find(s) == string::npos && str.find(t) == string::npos) {
cout << "YES" << endl << str << endl;
return 0;
}
}
assert(false);
cout << "NO" << endl;
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, k;
cin >> n >> k;
vector<int> p1(n), p2(n);
for (int i = 0; i < n; ++i) {
cin >> p1[i];
--p1[i];
}
for (int i = 0; i < n; ++i) {
cin >> p2[i];
--p2[i];
}
set<int> vals1, vals2;
vector<int> rb;
for (int i = 0; i < n; ++i) {
if (vals2.count(p1[i])) {
vals2.erase(p1[i]);
} else {
vals1.insert(p1[i]);
}
if (vals1.count(p2[i])) {
vals1.erase(p2[i]);
} else {
vals2.insert(p2[i]);
}
if (vals1.empty() && vals2.empty()) {
rb.push_back(i);
}
}
if (int(rb.size()) < k) {
cout << "NO" << endl;
} else {
string s(n, ' ');
int l = 0;
for (int it = 0; it < int(rb.size()); ++it) {
int r = rb[it];
char c = 'a' + min(it, 25);
for (int i = l; i <= r; ++i) {
s[p1[i]] = c;
}
l = r + 1;
}
cout << "YES" << endl << s << endl;
}
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
vector<int> p, rk;
int getp(int v) {
if (v == p[v]) return v;
return p[v] = getp(p[v]);
}
long long res;
long long get(int cnt) {
return cnt * 1ll * (cnt - 1) / 2;
}
void merge(int u, int v) {
u = getp(u);
v = getp(v);
if (rk[u] < rk[v]) swap(u, v);
res -= get(rk[u]);
res -= get(rk[v]);
rk[u] += rk[v];
res += get(rk[u]);
p[v] = u;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, m;
cin >> n >> m;
res = 0;
p = rk = vector<int>(n, 1);
iota(p.begin(), p.end(), 0);
vector<pair<int, pair<int, int>>> e(n - 1);
for (int i = 0; i < n - 1; ++i) {
cin >> e[i].second.first >> e[i].second.second >> e[i].first;
--e[i].second.first;
--e[i].second.second;
}
vector<pair<int, int>> q(m);
vector<long long> ans(m);
for (int i = 0; i < m; ++i) {
cin >> q[i].first;
q[i].second = i;
}
sort(e.begin(), e.end());
sort(q.begin(), q.end());
int pos = 0;
for (int i = 0; i < m; ++i) {
while (pos < n - 1 && e[pos].first <= q[i].first) {
int u = e[pos].second.first;
int v = e[pos].second.second;
merge(u, v);
++pos;
}
ans[q[i].second] = res;
}
for (int i = 0; i < m; ++i) {
cout << ans[i] << " ";
}
cout << endl;
return 0;
}