Greetings!
Codeforces Round 418 (Div. 2) has just come to an end. This is my first round here, and hope you all enjoyed the contest! > <
Seems the statements still created a few issues :( Anyway hope you liked it, and the characters feature the Monogatari anime series. Let me state again that the statements has little to do with the plot and you are not spoiled for the series! ^ ^
So for the impatient, here are the detailed tutorials for problems A, B and C. More are being boiled in the teapot... Goo-doo goo-doo.
Tutorial is loading...
Solution 1
#include <cstdio>
static const int MAXN = 102;
int n, k;
int a[MAXN], b[MAXN];
int main()
{
scanf("%d%d", &n, &k);
int last_zero = -1;
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
if (a[i] == 0) last_zero = i;
}
for (int i = 0; i < k; ++i) scanf("%d", &b[i]);
if (k > 1) {
puts("Yes");
} else {
a[last_zero] = b[0];
bool valid = false;
for (int i = 1; i < n; ++i)
if (a[i] <= a[i - 1]) { valid = true; break; }
puts(valid ? "Yes" : "No");
}
return 0;
}
Solution 2
#include <cstdio>
#include <algorithm>
static const int MAXN = 102;
int n, k;
int a[MAXN], b[MAXN];
int p[MAXN], r[MAXN];
inline bool check()
{
for (int i = 1; i < n; ++i) if (r[i] <= r[i - 1]) return true;
return false;
}
int main()
{
scanf("%d%d", &n, &k);
int last_zero = -1;
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
if (a[i] == 0) last_zero = i;
}
for (int i = 0; i < k; ++i) scanf("%d", &b[i]);
bool valid = false;
for (int i = 0; i < k; ++i) p[i] = i;
do {
for (int i = 0, ptr = 0; i < n; ++i) {
r[i] = (a[i] == 0) ? b[p[ptr++]] : a[i];
}
if (check()) { valid = true; break; }
} while (std::next_permutation(p, p + k));
puts(valid ? "Yes" : "No");
return 0;
}
Tutorial is loading...
Solution 1
#include <cstdio>
#include <cstring>
static const int MAXN = 1e3 + 4;
int n;
int a[MAXN], b[MAXN];
int pa[2][MAXN], pb[2][MAXN];
inline void try_recover(int *a, int *p1, int *p2)
{
int dup_ct = 0;
int dup1 = -1, dup2 = -1, absent = -1;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (a[i] == a[j]) dup1 = i, dup2 = j;
for (absent = 1; absent <= n; ++absent) {
bool occurred = false;
for (int i = 0; i < n; ++i) if (a[i] == absent) { occurred = true; break; }
if (!occurred) break;
}
memcpy(p1, a, n * sizeof(int));
memcpy(p2, a, n * sizeof(int));
p1[dup1] = absent;
p2[dup2] = absent;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
for (int i = 0; i < n; ++i) scanf("%d", &b[i]);
try_recover(a, pa[0], pa[1]);
try_recover(b, pb[0], pb[1]);
int *ans = NULL;
if (memcmp(pa[0], pb[0], n * sizeof(int)) == 0 || memcmp(pa[0], pb[1], n * sizeof(int)) == 0)
ans = pa[0];
else ans = pa[1];
for (int i = 0; i < n; ++i) printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');
return 0;
}
Solution 2 - Casework
#include <cstdio>
#include <utility>
static const int MAXN = 1e3 + 4;
int n;
int a[MAXN], b[MAXN];
std::pair<int, int> get_duplication(int *a)
{
static int occ[MAXN];
for (int i = 1; i <= n; ++i) occ[i] = -1;
for (int i = 0; i < n; ++i) {
if (occ[a[i]] != -1) return std::make_pair(occ[a[i]], i);
else occ[a[i]] = i;
}
return std::make_pair(-1, -1);
}
inline void fix_permutation(int pos)
{
static bool occ[MAXN];
for (int i = 1; i <= n; ++i) occ[i] = false;
for (int i = 0; i < n; ++i) if (i != pos) occ[a[i]] = true;
for (int i = 1; i <= n; ++i) if (!occ[i]) { a[pos] = i; return; }
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
for (int i = 0; i < n; ++i) scanf("%d", &b[i]);
std::pair<int, int> dup_a, dup_b;
dup_a = get_duplication(a);
dup_b = get_duplication(b);
if (dup_a == dup_b) {
a[dup_a.first] = b[dup_b.first];
} else if (dup_a.first == dup_b.first || dup_a.first == dup_b.second) {
a[dup_a.second] = b[dup_a.second];
fix_permutation(dup_a.first);
} else if (dup_a.second == dup_b.first || dup_a.second == dup_b.second) {
a[dup_a.first] = b[dup_a.first];
fix_permutation(dup_a.second);
} else {
a[dup_a.first] = b[dup_a.first];
a[dup_a.second] = b[dup_a.second];
}
for (int i = 0; i < n; ++i) printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
return 0;
}
Tutorial is loading...
Solution
#include <cstdio>
#include <algorithm>
static const int MAXN = 1502;
static const int ALPHABET = 26;
int n;
char s[MAXN];
int ans[ALPHABET][MAXN] = {{ 0 }};
int q, m_i;
char c_i;
int main()
{
scanf("%d", &n); getchar();
for (int i = 0; i < n; ++i) s[i] = getchar() — 'a';
for (char c = 0; c < ALPHABET; ++c) {
for (int i = 0; i < n; ++i) {
int replace_ct = 0;
for (int j = i; j < n; ++j) {
if (s[j] != c) ++replace_ct;
ans[c][replace_ct] = std::max(ans[c][replace_ct], j - i + 1);
}
}
for (int i = 1; i < MAXN; ++i)
ans[c][i] = std::max(ans[c][i], ans[c][i - 1]);
}
scanf("%d", &q);
for (int i = 0; i < q; ++i) {
scanf("%d %c", &m_i, &c_i);
printf("%d\n", ans[c_i - 'a'][m_i]);
}
return 0;
}
Goo-doo goo-doo...
(Second half of the night falls, and coming back after a bunch of hours. Thanks for understanding :P)
