I'm really sorry for the issue with the problem D difficulty, it was much harder than i expected, and there was a big difficulty gap between problems C and D. I hope in the next rounds it will never happen again.
UPD: I'd like to say a big thanks to kevinsogo for the great help with tutorials and the round preparation in general.
Tutorial
Tutorial is loading...
Solution (Vovuh)
#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];
int ans = 0;
while (!a.empty() && a.back() <= k) {
++ans;
a.pop_back();
}
reverse(a.begin(), a.end());
while (!a.empty() && a.back() <= k) {
++ans;
a.pop_back();
}
cout << ans << endl;
return 0;
}
Tutorial
Tutorial is loading...
Solution (Vovuh)
#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;
cin >> n >> s;
for (int i = 1; i <= n; ++i) {
if (n % i == 0) {
reverse(s.begin(), s.begin() + i);
}
}
cout << s << endl;
return 0;
}
Tutorial
Tutorial is loading...
Solution 1 (Vovuh)
#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;
string s;
cin >> s;
vector<int> cnt(26);
for (auto c : s) ++cnt[c - 'a'];
int pos = 26;
for (int i = 0; i < 26; ++i) {
if (k >= cnt[i]) {
k -= cnt[i];
} else {
pos = i;
break;
}
}
string ans;
int rem = k;
for (auto c : s) {
int cur = c - 'a';
if (cur > pos || (cur == pos && rem == 0)) {
ans += c;
} else if (cur == pos) {
--rem;
}
}
cout << ans << endl;
return 0;
}
Solution 2 (Vovuh)
#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;
string s;
cin >> s;
vector<pair<char, int>> c(n);
for (int i = 0; i < n; ++i)
c[i] = make_pair(s[i], i);
sort(c.begin(), c.end());
sort(c.begin() + k, c.end(), [&] (const pair<char, int> &a, const pair<char, int> &b) {
return a.second < b.second;
});
for (int i = k; i < n; ++i)
cout << c[i].first;
cout << endl;
return 0;
}
999D - Equalize the Remainders
Tutorial
Tutorial is loading...
Solution (Vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, m;
cin >> n >> m;
int k = n / m;
vector<int> a(n);
vector<vector<int>> val(m);
for (int i = 0; i < n; ++i) {
cin >> a[i];
val[a[i] % m].push_back(i);
}
long long ans = 0;
vector<pair<int, int>> fre;
for (int i = 0; i < 2 * m; ++i) {
int cur = i % m;
while (int(val[cur].size()) > k) {
int elem = val[cur].back();
val[cur].pop_back();
fre.push_back(make_pair(elem, i));
}
while (int(val[cur].size()) < k && !fre.empty()) {
int elem = fre.back().first;
int mmod = fre.back().second;
fre.pop_back();
val[cur].push_back(elem);
a[elem] += i - mmod;
ans += i - mmod;
}
}
cout << ans << endl;
for (int i = 0; i < n; ++i)
cout << a[i] << " ";
cout << endl;
return 0;
}
999E - Reachability from the Capital
Tutorial
Tutorial is loading...
Solution (Vovuh)
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int n, m, s;
vector<int> g[N];
bool used[N];
bool ok[N];
int cnt;
void dfs1(int v) {
ok[v] = true;
for (auto to : g[v])
if (!ok[to])
dfs1(to);
}
void dfs2(int v) {
used[v] = true;
++cnt;
for (auto to : g[v])
if (!used[to] && !ok[to])
dfs2(to);
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n >> m >> s;
--s;
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
g[x].push_back(y);
}
dfs1(s);
vector<pair<int, int>> val;
for (int i = 0; i < n; ++i) {
if (!ok[i]) {
cnt = 0;
memset(used, false, sizeof(used));
dfs2(i);
val.push_back(make_pair(cnt, i));
}
}
sort(val.begin(), val.end());
reverse(val.begin(), val.end());
int ans = 0;
for (auto it : val) {
if (!ok[it.second]) {
++ans;
dfs1(it.second);
}
}
cout << ans << endl;
return 0;
}
Linear Solution (Vovuh)
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int n, m, s;
vector<int> g[N];
vector<int> tg[N];
vector<int> cg[N];
vector<int> ord;
int indeg[N];
bool ucomp[N];
bool used[N];
int comp[N];
int cnt;
void dfs1(int v) {
used[v] = true;
for (auto to : g[v])
if (!used[to])
dfs1(to);
ord.push_back(v);
}
void dfs2(int v) {
comp[v] = cnt;
for (auto to : tg[v])
if (comp[to] == -1)
dfs2(to);
}
void dfs3(int v) {
ucomp[v] = true;
for (auto to : cg[v])
if (!ucomp[to])
dfs3(to);
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n >> m >> s;
--s;
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
g[x].push_back(y);
tg[y].push_back(x);
}
for (int i = 0; i < n; ++i) {
if (!used[i]) {
dfs1(i);
}
}
reverse(ord.begin(), ord.end());
memset(comp, -1, sizeof(comp));
for (int i = 0; i < n; ++i) {
if (comp[ord[i]] == -1) {
dfs2(ord[i]);
++cnt;
}
}
for (int v = 0; v < n; ++v) {
for (auto to : g[v]) {
if (comp[v] != comp[to]) {
cg[comp[v]].push_back(comp[to]);
++indeg[comp[to]];
}
}
}
dfs3(comp[s]);
int ans = 0;
for (int i = 0; i < cnt; ++i)
if (!ucomp[i] && indeg[i] == 0)
++ans;
cout << ans << endl;
return 0;
}
Tutorial
Tutorial is loading...
Solution (Vovuh)
#include <bits/stdc++.h>
using namespace std;
const int N = 520;
const int K = 12;
const int C = 100 * 1000 + 11;
int n, k;
int c[C];
int f[C];
vector<int> h;
int dp[N][K * N];
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n >> k;
h = vector<int>(k + 1);
for (int i = 0; i < n * k; ++i) {
int x;
cin >> x;
++c[x];
}
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
++f[x];
}
for (int i = 1; i <= k; ++i)
cin >> h[i];
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= n * k; ++j) {
for (int cur = 0; cur <= k; ++cur) {
dp[i + 1][j + cur] = max(dp[i + 1][j + cur], dp[i][j] + h[cur]);
}
}
}
int ans = 0;
for (int i = 0; i < C; ++i) {
if (f[i] != 0) ans += dp[f[i]][c[i]];
}
cout << ans << endl;
return 0;
}