We know about FST and we are really, really sorry about it. Even though we still hope that you liked the problems.
A: Digit Minimization
Editorial
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T --> 0) {
string n;
cin >> n;
if (n.size() == 2) {
cout << n[1] << '\n';
} else {
cout << *min_element(n.begin(), n.end()) << '\n';
}
}
return 0;
}
B: Z mod X = C
Editorial
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
void solve() {
int a, b, c;
cin >> a >> b >> c;
cout << a + b + c << " " << b + c << " " << c << "\n";
}
int main() {
int t;
cin >> t;
while (t--) solve();
return 0;
}
C: Column Swapping
Editorial
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
void solve(vector<vector<int>> &a) {
int n = a.size(), m = a[0].size();
vector<int> bad;
for (int i = 0; i < n && bad.empty(); i++) {
vector<int> b = a[i];
sort(b.begin(), b.end());
for (int j = 0; j < m; j++) {
if (a[i][j] != b[j]) bad.push_back(j);
}
}
if ((int)bad.size() == 0) {
cout << 1 << " " << 1 << "\n";
return;
}
if ((int)bad.size() > 2) {
cout << -1 << "\n";
return;
}
for (int i = 0; i < n; i++) {
swap(a[i][bad[0]], a[i][bad[1]]);
}
for (int i = 0; i < n; i++) {
for (int j = 1; j < m; j++) {
if (a[i][j] < a[i][j - 1]) {
cout << -1 << "\n";
return;
}
}
}
cout << bad[0] + 1 << " " << bad[1] + 1 << "\n";
return;
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#endif
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
solve(a);
}
return 0;
}
D: Traps
Editorial
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
void solve() {
int n, k;
cin >> n >> k;
long long ans = 0;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
ans += a[i];
a[i] += i + 1;
}
sort(all(a));
reverse(all(a));
for (int i = 0; i < k; i++) ans -= a[i];
for (int i = 0; i < k; i++) {
ans += n;
ans -= i;
}
cout << ans << "\n";
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#endif
int t;
cin >> t;
while (t--) solve();
return 0;
}
E: MEX vs DIFF
Editorial
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define pii pair<int, int>
#define puu pair<unsigned, unsigned>
#define ll long long
#define mp make_pair
#define ui unsigned
#define ull unsigned long long
#define ld double
#define pld pair<ld, ld>
#define pll pair<ll, ll>
const int INF = 1e9 + 1;
const ll INFLL = 1e18;
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (auto &c : a) cin >> c;
map<int, int> cnt;
for (auto &c : a) cnt[c]++;
set<pii> s1, s2;
int sum1 = 0;
for (auto &c : cnt) s2.insert(mp(c.se, c.fi));
int ans = INF;
int skip = 0;
for (int x = 0; x <= n; x++) {
if (s1.find(mp(cnt[x - 1], x - 1)) != s1.end()) {
sum1 -= cnt[x - 1];
s1.erase(mp(cnt[x - 1], x - 1));
}
if (s2.find(mp(cnt[x - 1], x - 1)) != s2.end()) {
s2.erase(mp(cnt[x - 1], x - 1));
}
while (s2.size() && sum1 + s2.begin()->fi <= k) {
s1.insert(*s2.begin());
sum1 += s2.begin()->fi;
s2.erase(s2.begin());
}
if (k < skip) break;
int now = x + s2.size();
if (x == 0) {
now = max(1, (int)s2.size());
}
ans = min(ans, now - x);
if (cnt[x] == 0) skip++;
}
cout << ans << "\n";
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#endif
int t;
cin >> t;
while (t--) solve();
return 0;
}
F: Diverse Segments
Editorial
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define pii pair<int, int>
#define puu pair<unsigned, unsigned>
#define ll long long
#define mp make_pair
#define ui unsigned
#define ull unsigned long long
#define ld double
#define pld pair<ld, ld>
#define pll pair<ll, ll>
const int INF = 1e9 + 1;
const ll INFLL = 1e18;
vector<int> f;
void incr(int x, int d) {
for (; x < (int)f.size(); x |= (x + 1)) f[x] = max(f[x], d);
}
int get(int x) {
int ans = -1;
for (; x >= 0; x = (x & (x + 1)) - 1) ans = max(ans, f[x]);
return ans;
}
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n);
for (auto &c : a) cin >> c;
map<int, vector<int>> gist;
for (int i = 0; i < n; i++) gist[a[i]].pb(i);
vector<pii> seg(m);
f.assign(n, -1);
for (auto &c : seg) {
cin >> c.fi >> c.se; c.fi--; c.se--;
incr(c.fi, c.se);
}
vector<int> mnl(n);
set<int> s;
int l = n;
for (int r = n - 1; r >= 0; r--) {
while (l - 1 >= 0 && !s.count(a[l - 1])) {
l--;
s.insert(a[l]);
}
mnl[r] = l;
s.erase(a[r]);
}
int mnr = -1;
for (auto &c : seg) {
int l = c.fi, r = c.se;
if (mnl[r] <= l) continue;
mnr = max(mnr, mnl[r] - 1);
}
if (mnr == -1) {
cout << 0 << "\n";
return;
}
int ans = mnr + 1;
for (int l = 0; l + 1 < n; l++) {
if (gist[a[l]][0] != l) {
int id = lower_bound(all(gist[a[l]]), l) - gist[a[l]].begin() - 1;
int pr = gist[a[l]][id];
if (get(pr) >= l) {
break;
}
}
int id = upper_bound(all(gist[a[l]]), mnr) - gist[a[l]].begin();
if (id != (int)gist[a[l]].size()) {
int nxt = gist[a[l]][id];
if (get(l) >= nxt) {
mnr = nxt;
}
}
mnr = max(mnr, l + 1);
ans = min(ans, mnr - l);
}
cout << ans << "\n";
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#endif
int t;
cin >> t;
while (t--) solve();
return 0;
}
G: Euclid Guess
Editorial
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define pii pair<int, int>
#define puu pair<unsigned, unsigned>
#define ll long long
#define mp make_pair
#define ui unsigned
#define ull unsigned long long
#define ld double
#define pld pair<ld, ld>
#define pll pair<ll, ll>
#define int ll
const int INF = 1e9 + 1;
const ll INFLL = 1e18;
vector<vector<int>> g;
vector<int> with;
vector<int> usd;
int dfs(int v) {
if (usd[v]) return 0;
usd[v] = 1;
for (auto &to : g[v]) {
if (with[to] == -1) {
with[to] = v;
return 1;
}
}
for (auto &to : g[v]) {
if (dfs(with[to])) {
with[to] = v;
return 1;
}
}
return 0;
}
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#endif
int n, A;
cin >> n >> A;
vector<int> a(n);
vector<int> l, r;
for (auto &c : a) {
cin >> c;
if (3 * c > A) {
l.pb(c);
} else {
r.pb(c);
}
}
g.resize(l.size());
with.resize(r.size(), -1);
for (int i = 0; i < (int)l.size(); i++) {
for (int j = 0; j < (int)r.size(); j++) {
if (l[i] % r[j] == 0 && 2 * l[i] + r[j] <= A) {
g[i].pb(j);
}
}
}
int cnt = 0;
for (int i = 0; i < (int)l.size(); i++) {
usd.assign(l.size(), 0);
cnt += dfs(i);
}
if (cnt < (int)l.size()) {
cout << -1;
return 0;
}
vector<pii> ans;
for (int j = 0; j < (int)r.size(); j++) {
if (with[j] == -1) {
ans.pb(3 * r[j], 2 * r[j]);
} else {
ans.pb(2 * l[with[j]] + r[j], l[with[j]] + r[j]);
}
}
cout << ans.size() << "\n";
for (auto &c : ans) cout << c.fi << " " << c.se << "\n";
return 0;
}
H: Hard Cut
Editorial
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6;
int g[MAXN + 1];
string s;
vector<pair<int, int>> segments; // [l, r]
int get(int k, int i) { // get k-th '1' on [i, |s|)
--i;
while (k --> 0) i = s.find('1', i + 1);
return i;
}
void five() {
int first = get(1, 0), last = get(5, 0);
int r = (int)s.size() - 1;
if (last - first + 1 == 5) { // creating 16: ['001111', '1', '0000']
segments.emplace_back(0, last - 1);
segments.emplace_back(last, last);
if (last < r) segments.emplace_back(last + 1, r);
} else { // creating 8: cut out '101' or '100' and cut everything in single digits
int pos = s.find("101");
if (pos == string::npos) pos = s.find("100");
for (int i = 0; i < pos; ++i) segments.emplace_back(i, i);
segments.emplace_back(pos, pos + 2);
for (int i = pos + 3; i <= r; ++i) segments.emplace_back(i, i);
}
}
void solve(int l, int r, int k, int n) { // [l; r]
if (k == n) { // cutting into single digits
for (int i = l; i <= r; ++i) segments.emplace_back(i, i);
} else if (k == 2 && n == 3) {
int pos = get(1, l);
if (s[pos + 1] == '1') { // ['11', '00...00']
segments.emplace_back(l, pos + 1);
if (pos + 2 <= r) segments.emplace_back(pos + 2, r);
} else { // ['10', '0001', '00000']
int newpos = get(1, pos + 1);
segments.emplace_back(l, pos + 1);
segments.emplace_back(pos + 2, newpos);
if (newpos + 1 <= r) segments.emplace_back(newpos + 1, r);
}
} else if (3 * k / 2 >= n) { // using previous if technique
int pos = get(2, l);
solve(l, pos, 2, 3);
if (k > 2) solve(pos + 1, r, k - 2, n - 3);
} else if ((k == 4 && n == 8) || (k == 9 && n == 16)) {
int pos = get(1, l);
string sub = s.substr(pos, 3);
segments.emplace_back(l, pos + 2);
if (sub == "100") solve(pos + 3, r, k - 1, n - 4);
if (sub == "101") solve(pos + 3, r, k - 2, n - 5);
if (sub == "110") solve(pos + 3, r, k - 2, n - 6);
if (sub == "111") solve(pos + 3, r, k - 3, n - 7);
} else if ((k == 7 && n == 11) || (k == 10 && n == 16)) {
int mid = get(4, l);
solve(l, mid, 4, 8);
solve(mid + 1, r, k - 4, n - 8);
} else { // common case
int mid = get(k / 2, l);
solve(l, mid, k / 2, n / 2);
solve(mid + 1, r, k - k / 2, n / 2);
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
g[1] = 1;
for (int i = 2; i <= MAXN; ++i) g[i] = g[(i + 1) / 2] * 2;
int T;
cin >> T;
while (T --> 0) {
cin >> s;
int k = count(s.begin(), s.end(), '1');
if (!k) {
cout << -1 << '\n';
continue;
}
segments.clear();
if (k == 5) five();
else solve(0, (int)s.size() - 1, k, g[k]);
cout << segments.size() << '\n';
for (auto &[l, r] : segments) {
cout << l + 1 << ' ' << r + 1 << '\n';
}
}
return 0;
}