1579A - Casimir's String Solitaire
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
cout << (count(s.begin(), s.end(), 'B') * 2 == s.size() ?
"YES\n" : "NO\n");
}
}
Idea: doreshnikov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
vector<pii> actions;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n - 1; i++) {
int min_pos = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[min_pos])
min_pos = j;
if (min_pos > i) {
actions.push_back({i, min_pos});
int opt = a[min_pos];
for (int j = min_pos; j > i; j--)
a[j] = a[j - 1];
a[i] = opt;
}
}
cout << actions.size() << '\n';
for (auto &lr: actions) {
cout << lr.first + 1 << ' ' << lr.second + 1 << ' ' << lr.second - lr.first << '\n';
}
}
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> status(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < m; j++)
if (s[j] == '*')
status[i][j] = 1;
}
for (int i = n - 1; i > -1; i--) {
for (int j = 0; j < m; j++) {
if (status[i][j] == 0)
continue;
int len = 0;
while (j > len && j + len + 1 < m && i > len) {
if (status[i - len - 1][j - len - 1] == 0 || status[i - len - 1][j + len + 1] == 0)
break;
len++;
}
if (len >= k) {
for (int d = 0; d <= len; d++) {
status[i - d][j - d] = 2;
status[i - d][j + d] = 2;
}
}
}
}
bool ok = true;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (status[i][j] == 1)
ok = false;
cout << (ok ? "YES" : "NO") << '\n';
}
}
Idea: doreshnikov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
auto cmp = [](pii const &x, pii const &y) {
return x > y;
};
set<pii, decltype(cmp)> a(cmp);
vector<pii> answer;
for (int i = 0; i < n; i++) {
int ai;
cin >> ai;
if (ai > 0)
a.emplace(ai, i + 1);
}
while (a.size() > 1) {
auto p1 = *a.begin();
a.erase(a.begin());
auto p2 = *a.begin();
a.erase(a.begin());
answer.emplace_back(p1.second, p2.second);
if (p1.first > 1) a.emplace(p1.first - 1, p1.second);
if (p2.first > 1) a.emplace(p2.first - 1, p2.second);
}
cout << answer.size() << '\n';
for (auto &p : answer) {
cout << p.first << ' ' << p.second << '\n';
}
}
}
1579E1 - Permutation Minimization by Deque
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, a;
cin >> n;
deque<int> d;
for (int i = 0; i < n; i++) {
cin >> a;
if (d.empty() || a < d[0])
d.push_front(a);
else
d.push_back(a);
}
for (int x : d)
cout << x << ' ';
cout << '\n';
}
}
1579E2 - Array Optimization by Deque
Idea: doreshnikov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef pair<int, int> node;
typedef tree<node, null_type, less<node>,
rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
ordered_set s;
long long cnt = 0;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
int less = s.order_of_key(node(a, 0)),
greater = i - s.order_of_key(node(a, n));
cnt += min(less, greater);
s.insert(node(a, i));
}
cout << cnt << '\n';
}
}
1579F - Array Stabilization (AND version)
Idea: doreshnikov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, d;
cin >> n >> d;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
vector<bool> used(n, false);
bool fail = false;
int res = 0;
for (int i = 0; i < n; i++) {
if (used[i])
continue;
int cur = i, pref = 0, last = 0, iter = 0, ans = 0;
do {
used[cur] = true;
if (a[cur] == 0) {
ans = max(ans, last);
last = 0;
} else {
last++;
if (iter == pref) {
pref++;
}
}
cur = (cur + d) % n;
iter++;
} while (cur != i);
if (iter != pref)
ans = max(ans, pref + last);
else {
fail = true;
break;
}
res = max(res, ans);
}
if (fail)
cout << "-1\n";
else
cout << res << '\n';
}
}
Idea: doreshnikov, MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
int maxl = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
maxl = max(maxl, a[i]);
}
vector<vector<int>> dp(n + 1, vector<int>(2 * maxl + 1, INF));
dp[0][0] = 0;
for (int i = 0; i < n; i++) {
for (int left = 0; left <= 2 * maxl; left++) {
if (dp[i][left] == INF)
continue;
dp[i + 1][max(left - a[i], 0)] = min(dp[i + 1][max(left - a[i], 0)], dp[i][left] + a[i]);
if (left + a[i] < dp[i + 1].size()) {
dp[i + 1][left + a[i]] = min(dp[i + 1][left + a[i]], max(dp[i][left] - a[i], 0));
}
}
}
int ans = 2 * maxl + 1;
for (int left = 0; left <= 2 * maxl; left++)
ans = min(ans, left + dp[n][left]);
cout << ans << '\n';
}
}