1579A - Casimir's String Solitaire
Idea: MikeMirzayanov
#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
~~~~~
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 a(n); vector 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({l, 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
~~~~~
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> status(n, vector(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
~~~~~
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 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
#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
~~~~~
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, 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
~~~~~
include <bits/stdc++.h>
using namespace std;
int main() { int t; cin >> t; while (t--) { int n, d; cin >> n >> d; vector a(n); for (int i = 0; i < n; i++) cin >> a[i]; vector 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
~~~~~
include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector a(n); int maxl = 0; for (int i = 0; i < n; i++) { cin >> a[i]; maxl = max(maxl, a[i]); } vector<vector> dp(n + 1, vector(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'; }
}~~~~~