Idea: MikeMirzayanov
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 n;
cin >> n;
forn(i, n) {
string s;
cin >> s;
if (set<char>(s.begin(), s.end()).size() == s.length()
&& *max_element(s.begin(), s.end()) == char(*min_element(s.begin(), s.end()) + (s.length() - 1)))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
1144B - Parity Alternated Deletions
Idea: 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 sum = 0;
vector<int> even, odd;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
sum += x;
if (x & 1) odd.push_back(x);
else even.push_back(x);
}
sort(odd.rbegin(), odd.rend());
sort(even.rbegin(), even.rend());
int k = min(odd.size(), even.size());
int rem = sum;
rem -= accumulate(odd.begin(), odd.begin() + k, 0);
rem -= accumulate(even.begin(), even.begin() + k, 0);
if (int(odd.size()) > k) {
rem -= odd[k];
}
if (int(even.size()) > k) {
rem -= even[k];
}
cout << rem << endl;
return 0;
}
1144C - Two Shuffled Sequences
Idea: 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;
vector<int> cnt(200 * 1000 + 1);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
++cnt[x];
if (cnt[x] > 2) {
cout << "NO" << endl;
return 0;
}
}
cout << "YES" << endl << count(cnt.begin(), cnt.end(), 2) << endl;
for (int i = 0; i <= 200 * 1000; ++i) {
if (cnt[i] == 2) {
cout << i << " ";
--cnt[i];
}
}
cout << endl << count(cnt.begin(), cnt.end(), 1) << endl;
for (int i = 200 * 1000; i >= 0; --i) {
if (cnt[i] == 1) {
cout << i << " ";
--cnt[i];
}
}
cout << endl;
assert(count(cnt.begin(), cnt.end(), 0) == 200 * 1000 + 1);
return 0;
}
Idea: vovuh
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;
vector<int> a(n), cnt(200 * 1000 + 1);
for (int i = 0; i < n; ++i) {
cin >> a[i];
++cnt[a[i]];
}
int val = max_element(cnt.begin(), cnt.end()) - cnt.begin();
int pos = find(a.begin(), a.end(), val) - a.begin();
cout << n - cnt[val] << endl;
int siz = 0;
for (int i = pos - 1; i >= 0; --i) {
cout << 1 + (a[i] > a[i + 1]) << " " << i + 1 << " " << i + 2 << " " << endl;
a[i] = a[i + 1];
++siz;
}
for (int i = 0; i < n - 1; ++i) {
if (a[i + 1] != val) {
assert(a[i] == val);
cout << 1 + (a[i + 1] > a[i]) << " " << i + 2 << " " << i + 1 << " " << endl;
a[i + 1] = a[i];
++siz;
}
}
assert(siz == n - cnt[val]);
return 0;
}
Idea: vovuh
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
vector<int> get(const string &s) {
vector<int> res(s.size() + 1);
for (int i = 0; i < int(s.size()); ++i) {
res[i + 1] = s[i] - 'a';
}
return res;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int k;
string s, t;
cin >> k >> s >> t;
vector<int> a = get(s), b = get(t);
for (int i = k; i >= 0; --i) {
a[i] += b[i];
if (i) {
a[i - 1] += a[i] / 26;
a[i] %= 26;
}
}
for (int i = 0; i <= k; ++i) {
int rem = a[i] % 2;
a[i] /= 2;
if (i + 1 <= k) {
a[i + 1] += rem * 26;
} else {
assert(rem == 0);
}
}
for (int i = 1; i <= k; ++i) {
cout << char('a' + a[i]);
}
cout << endl;
return 0;
}
1144F - Graph Without Long Directed Paths
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int N = 200 * 1000 + 11;
int n, m;
vector<int> g[N];
vector<pair<int, int>> e;
bool bipartite;
vector<int> color;
void dfs(int v, int c) {
color[v] = c;
for (auto to : g[v]) {
if (color[to] == -1) {
dfs(to, c ^ 1);
} else {
if (color[to] == color[v]) {
bipartite = false;
}
}
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
g[x].push_back(y);
g[y].push_back(x);
e.push_back(make_pair(x, y));
}
bipartite = true;
color = vector<int>(n, -1);
dfs(0, 0);
if (!bipartite) {
cout << "NO" << endl;
return 0;
}
cout << "YES" << endl;
for (int i = 0; i < m; ++i) {
cout << (color[e[i].first] < color[e[i].second]);
}
cout << endl;
return 0;
}
There is different solution for the problem, it is pretty interesting! Thanks, Roundgod!
Idea: vovuh
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<vector<int>> dp(n, vector<int>({-INF, INF}));
vector<vector<int>> p(n, vector<int>(2, -1));
dp[0][0] = INF;
dp[0][1] = -INF;
for (int i = 1; i < n; ++i) {
{
if (a[i] > a[i - 1] && dp[i][0] < dp[i - 1][0]) {
dp[i][0] = dp[i - 1][0];
p[i][0] = 0;
}
if (a[i] < dp[i - 1][0] && dp[i][1] > a[i - 1]) {
dp[i][1] = a[i - 1];
p[i][1] = 0;
}
}
{
if (a[i] < a[i - 1] && dp[i][1] > dp[i - 1][1]) {
dp[i][1] = dp[i - 1][1];
p[i][1] = 1;
}
if (a[i] > dp[i - 1][1] && dp[i][0] < a[i - 1]) {
dp[i][0] = a[i - 1];
p[i][0] = 1;
}
}
}
int pos = -1;
if (dp[n - 1][0] != -INF) {
pos = 0;
}
if (dp[n - 1][1] != INF) {
pos = 1;
}
if (pos == -1) {
cout << "NO" << endl;
return 0;
}
vector<int> inInc(n);
for (int i = n - 1; i >= 0; --i) {
if (pos == 0) {
inInc[i] = 1;
}
pos = p[i][pos];
}
cout << "YES" << endl;
for (int i = 0; i < n; ++i) {
cout << !inInc[i] << " ";
}
cout << endl;
return 0;
}