Greetings!↵
↵
[contest:814] 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:814A]↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:814B]↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:814C]↵
↵
<spoiler summary="Solution 1">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵
↵
Goo-doo goo-doo...
↵
[contest:814] 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:814A]↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:814B]↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:814C]↵
↵
<spoiler summary="Solution 1">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵
↵
Goo-doo goo-doo...
