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 theplot and you are _not_ spoiled foractual plot — they're inspired by five theme songs actually — and I'm _not_ spoiling anyone of the series! ^ ^↵
↵
So for the impatient, hympathy for those failing system tests on B... This problem was intended to experience a lot of hacks but somehow there are not so many.↵
↵
Here are the detailedtutorials for problems A, B and C. More are being boiled in the teapot... Goo-doo goo-doosolutions to the problems. Feel free to write in the comments if there's anything incorrect or unclear.↵
↵
[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">↵
~~~~~↵
#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>↵
↵
[tutorial:814D]↵
↵
<spoiler summary="Solution 1 - DP on trees">↵
~~~~~↵
#include <cstdio>↵
#include <cmath>↵
#include <algorithm>↵
#include <vector>↵
typedef long long int64;↵
static const int MAXN = 1004;↵
#ifndef M_PI↵
static const double M_PI = acos(-1.0);↵
#endif↵
↵
int n;↵
int x[MAXN], y[MAXN], r[MAXN];↵
int par[MAXN];↵
std::vector<int> e[MAXN];↵
↵
// Whether one of C[u] and C[v] is contained in another↵
inline bool circle_contains(int u, int v)↵
{↵
return ((int64)(x[u] - x[v]) * (x[u] - x[v]) + (int64)(y[u] - y[v]) * (y[u] - y[v]) <= (int64)(r[u] - r[v]) * (r[u] - r[v]));↵
}↵
↵
int64 f[MAXN][2][2];↵
↵
void dfs_dp(int u)↵
{↵
int64 g[2][2] = {{ 0 }};↵
for (int v : e[u]) {↵
dfs_dp(v);↵
for (int i = 0; i <= 1; ++i)↵
for (int j = 0; j <= 1; ++j)↵
g[i][j] += f[v][i][j];↵
}↵
for (int i = 0; i <= 1; ++i)↵
for (int j = 0; j <= 1; ++j) {↵
f[u][i][j] = std::max(↵
// (1) <u> is assigned to the first group↵
g[i ^ 1][j] + (int64)r[u] * r[u] * (i == 0 ? +1 : -1),↵
// (2) <u> is assigned to the second group↵
g[i][j ^ 1] + (int64)r[u] * r[u] * (j == 0 ? +1 : -1)↵
);↵
}↵
}↵
↵
int main()↵
{↵
scanf("%d", &n);↵
for (int i = 0; i < n; ++i) scanf("%d%d%d", &x[i], &y[i], &r[i]);↵
↵
for (int i = 0; i < n; ++i) {↵
par[i] = -1;↵
for (int j = 0; j < n; ++j)↵
if (r[j] > r[i] && circle_contains(i, j)) {↵
if (par[i] == -1 || r[par[i]] > r[j]) par[i] = j;↵
}↵
e[par[i]].push_back(i);↵
}↵
↵
int64 ans = 0;↵
for (int i = 0; i < n; ++i) if (par[i] == -1) {↵
dfs_dp(i);↵
ans += f[i][0][0];↵
}↵
printf("%.8lf\n", (double)ans * M_PI);↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Solution 2 - Greedy">↵
~~~~~↵
#include <cstdio>↵
#include <cmath>↵
#include <algorithm>↵
#include <vector>↵
typedef long long int64;↵
static const int MAXN = 1004;↵
#ifndef M_PI↵
static const double M_PI = acos(-1.0);↵
#endif↵
↵
int n;↵
int x[MAXN], y[MAXN], r[MAXN];↵
int par[MAXN];↵
std::vector<int> e[MAXN];↵
↵
bool level[MAXN];↵
↵
// Whether one of C[u] and C[v] is contained in another↵
inline bool circle_contains(int u, int v)↵
{↵
return ((int64)(x[u] - x[v]) * (x[u] - x[v]) + (int64)(y[u] - y[v]) * (y[u] - y[v]) <= (int64)(r[u] - r[v]) * (r[u] - r[v]));↵
}↵
↵
void dfs_colour(int u, bool c)↵
{↵
level[u] = c;↵
for (int v : e[u]) dfs_colour(v, c ^ 1);↵
}↵
↵
int main()↵
{↵
scanf("%d", &n);↵
for (int i = 0; i < n; ++i) scanf("%d%d%d", &x[i], &y[i], &r[i]);↵
↵
for (int i = 0; i < n; ++i) {↵
par[i] = -1;↵
for (int j = 0; j < n; ++j)↵
if (r[j] > r[i] && circle_contains(i, j)) {↵
if (par[i] == -1 || r[par[i]] > r[j]) par[i] = j;↵
}↵
e[par[i]].push_back(i);↵
}↵
↵
for (int i = 0; i < n; ++i) if (par[i] == -1) dfs_colour(i, false);↵
int64 ans = 0;↵
for (int i = 0; i < n; ++i)↵
ans += (int64)r[i] * r[i] * (par[i] == -1 || (level[i] == true) ? +1 : -1);↵
printf("%.8lf\n", (double)ans * M_PI);↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
Goo-doo goo-doo...One more thing — Staying up late is bad for health.↵
↵
[tutorial:814E]↵
↵
<spoiler summary="Solution 1 - O(n^5)">↵
~~~~~↵
#include <cstdio>↵
#include <cstring>↵
typedef long long int64;↵
static const int MAXN = 52;↵
static const int MODULUS = 1e9 + 7;↵
#define _ % MODULUS↵
#define __ %= MODULUS↵
↵
int n, d[MAXN];↵
int64 f[2][MAXN][MAXN][MAXN][MAXN] = {{{{{ 0 }}}}};↵
↵
int main()↵
{↵
scanf("%d", &n);↵
for (int i = 0; i < n; ++i) scanf("%d", &d[i]);↵
↵
int cur = 0, next = 1;↵
f[cur][d[0] == 2][d[0] == 3][d[1] == 2][d[1] == 3] = 1;↵
for (int i = 1; i < n - 1; ++i) {↵
memset(f[next], 0, sizeof f[next]);↵
for (int p1 = 0; p1 <= n; ++p1)↵
for (int p2 = 0; p1 + p2 <= n; ++p2)↵
for (int c1 = 0; c1 + p1 + p2 <= n; ++c1)↵
for (int c2 = 0; c1 + c2 + p1 + p2 <= n; ++c2) if (f[cur][p1][p2][c1][c2] > 0) {↵
int64 val = f[cur][p1][p2][c1][c2];↵
// (1) Start a new level↵
if (p1 == 0 && p2 == 0) {↵
(f[cur][c1][c2][0][0] += val)__;↵
continue;↵
}↵
// (2) Stay on current level↵
// Which type of vertex in the last level?↵
for (int last_level = 0; last_level <= 1; ++last_level) {↵
int last_ways;↵
if (last_level == 0) {↵
last_ways = p1;↵
if (--p1 < 0) { ++p1; continue; }↵
} else {↵
last_ways = p2;↵
if (--p2 < 0) { ++p2; continue; } else ++p1;↵
}↵
// Which type of vertices in the current level?↵
if (d[i + 1] == 2) {↵
// a) Leave as it is↵
(f[next][p1][p2][c1 + 1][c2] += val * last_ways)__;↵
// b) 1-plug↵
if (c1 >= 1)↵
(f[next][p1][p2][c1 - 1][c2] += val * last_ways * c1)__;↵
// c) 2-plug↵
if (c2 >= 1)↵
(f[next][p1][p2][c1 + 1][c2 - 1] += val * last_ways * c2)__;↵
} else {↵
// a) Leave as it is↵
(f[next][p1][p2][c1][c2 + 1] += val * last_ways)__;↵
// b) 1-plug↵
if (c1 >= 1)↵
(f[next][p1][p2][c1][c2] += val * last_ways * c1)__;↵
// c) 2-plug↵
if (c2 >= 1)↵
(f[next][p1][p2][c1 + 2][c2 - 1] += val * last_ways * c2)__;↵
// d) 1-plug + 1-plug↵
if (c1 >= 2)↵
(f[next][p1][p2][c1 - 2][c2] += val * last_ways * c1 * (c1 - 1) / 2)__;↵
// e) 2-plug + 2-plug↵
if (c2 >= 2)↵
(f[next][p1][p2][c1 + 2][c2 - 2] += val * last_ways * c2 * (c2 - 1) / 2)__;↵
// f) 1-plug + 2-plug↵
if (c1 >= 1 && c2 >= 1)↵
(f[next][p1][p2][c1][c2 - 1] += val * last_ways * c1 * c2)__;↵
}↵
if (last_level == 0) ++p1; else ++p2, --p1;↵
}↵
}↵
cur ^= 1, next ^= 1;↵
}↵
↵
printf("%lld\n", f[cur][0][0][0][0]);↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Solution 2 - O(n^3) by KAN">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
using ll = long long;↵
using ld = long double;↵
using D = double;↵
using uint = unsigned int;↵
template<typename T>↵
using pair2 = pair<T, T>;↵
↵
#ifdef WIN32↵
#define LLD "%I64d"↵
#else↵
#define LLD "%lld"↵
#endif↵
↵
#define pb push_back↵
#define mp make_pair↵
#define all(x) (x).begin(),(x).end()↵
#define fi first↵
#define se second↵
↵
const int maxn = 55;↵
const int MOD = 1000000007;↵
↵
int ways[maxn][maxn][maxn];↵
int answer[maxn][maxn];↵
int n;↵
int d[maxn];↵
int sumd[maxn];↵
↵
inline void add(int &a, ll b)↵
{↵
a = (a + b) % MOD;↵
}↵
↵
int main()↵
{↵
scanf("%d", &n);↵
for (int i = 0; i < n; i++) scanf("%d", &d[i]);↵
↵
ways[0][0][0] = 1;↵
for (int c0 = 0; c0 <= n; c0++)↵
{↵
for (int c2 = 0; c2 <= n; c2++)↵
{↵
for (int c1 = 0; c1 <= n; c1++) if (c1 + c2 > 0)↵
{↵
if (c2 > 0)↵
{↵
if (c0 > 1) add(ways[c0][c1][c2], (ll)ways[c0 - 2][c1][c2 - 1] * (c0 * (c0 - 1) / 2)); // 2-0, 2-0↵
if (c2 > 1 && c0 > 0) add(ways[c0][c1][c2], (ll)ways[c0 - 1][c1 + 1][c2 - 2] * (c2 - 1) * c0); // 2-2, 2-0↵
if (c2 > 2) add(ways[c0][c1][c2], (ll)ways[c0][c1 + 2][c2 - 3] * ((c2 - 1) * (c2 - 2) / 2)); // 2-2, 2-2↵
if (c1 > 0 && c2 > 1) add(ways[c0][c1][c2], (ll)ways[c0][c1][c2 - 2] * c1 * (c2 - 1)); // 2-2, 2-1↵
if (c1 > 0 && c0 > 0) add(ways[c0][c1][c2], (ll)ways[c0 - 1][c1 - 1][c2 - 1] * c1 * c0); // 2-1, 2-0↵
if (c1 > 1) add(ways[c0][c1][c2], (ll)ways[c0][c1 - 2][c2 - 1] * (c1 * (c1 - 1) / 2)); // 2-1, 2-1↵
} else↵
{↵
if (c0 > 0) add(ways[c0][c1][c2], ways[c0 - 1][c1 - 1][c2] * c0); // 1-0↵
if (c1 > 1) add(ways[c0][c1][c2], (ll)ways[c0][c1 - 2][c2] * (c1 - 1)); // 1-1↵
}↵
}↵
}↵
}↵
↵
for (int i = 0; i < n; i++) sumd[i + 1] = sumd[i] + d[i];↵
answer[n][n - 1] = 1;↵
for (int l = n - 1; l > 0; l--)↵
{↵
for (int r = l; r < n; r++)↵
{↵
int cnt2 = sumd[r + 1] - sumd[l] - 2 * (r - l + 1);↵
int cnt1 = r - l + 1 - cnt2;↵
for (int nextlvl = 0; nextlvl <= 2 * cnt2 + cnt1 && nextlvl <= n; nextlvl++)↵
{↵
int curways = ways[nextlvl][cnt1][cnt2];↵
if (r + nextlvl < n)↵
{↵
add(answer[l][r], (ll)answer[r + 1][r + nextlvl] * curways);↵
}↵
}↵
}↵
}↵
if (d[0] + 1 > n) cout << 0 << endl;↵
else cout << answer[1][d[0]] << endl;↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
This is the round with the most solutions so far perhaps? There are at least $3 \times 2 \times 3 \times 3 \times 3 = 162$ different ways to pass all problems in this round =D↵
↵
> Pla-tinum happy though I'm supposed to be ↵
> Pla-tinum sad is somehow how I get↵
↵
Personally I'd like to express my gratitude to the community for creating this amazing first-time experience for me. Thank you, and see you next round. Probably it will be for Ha... Well, let's wait and see :)↵
↵
Cheers \\(^ ^)/
↵
[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
↵
S
↵
Here are the detailed
↵
[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">↵
~~~~~↵
#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>↵
↵
[tutorial:814D]↵
↵
<spoiler summary="Solution 1 - DP on trees">↵
~~~~~↵
#include <cstdio>↵
#include <cmath>↵
#include <algorithm>↵
#include <vector>↵
typedef long long int64;↵
static const int MAXN = 1004;↵
#ifndef M_PI↵
static const double M_PI = acos(-1.0);↵
#endif↵
↵
int n;↵
int x[MAXN], y[MAXN], r[MAXN];↵
int par[MAXN];↵
std::vector<int> e[MAXN];↵
↵
// Whether one of C[u] and C[v] is contained in another↵
inline bool circle_contains(int u, int v)↵
{↵
return ((int64)(x[u] - x[v]) * (x[u] - x[v]) + (int64)(y[u] - y[v]) * (y[u] - y[v]) <= (int64)(r[u] - r[v]) * (r[u] - r[v]));↵
}↵
↵
int64 f[MAXN][2][2];↵
↵
void dfs_dp(int u)↵
{↵
int64 g[2][2] = {{ 0 }};↵
for (int v : e[u]) {↵
dfs_dp(v);↵
for (int i = 0; i <= 1; ++i)↵
for (int j = 0; j <= 1; ++j)↵
g[i][j] += f[v][i][j];↵
}↵
for (int i = 0; i <= 1; ++i)↵
for (int j = 0; j <= 1; ++j) {↵
f[u][i][j] = std::max(↵
// (1) <u> is assigned to the first group↵
g[i ^ 1][j] + (int64)r[u] * r[u] * (i == 0 ? +1 : -1),↵
// (2) <u> is assigned to the second group↵
g[i][j ^ 1] + (int64)r[u] * r[u] * (j == 0 ? +1 : -1)↵
);↵
}↵
}↵
↵
int main()↵
{↵
scanf("%d", &n);↵
for (int i = 0; i < n; ++i) scanf("%d%d%d", &x[i], &y[i], &r[i]);↵
↵
for (int i = 0; i < n; ++i) {↵
par[i] = -1;↵
for (int j = 0; j < n; ++j)↵
if (r[j] > r[i] && circle_contains(i, j)) {↵
if (par[i] == -1 || r[par[i]] > r[j]) par[i] = j;↵
}↵
e[par[i]].push_back(i);↵
}↵
↵
int64 ans = 0;↵
for (int i = 0; i < n; ++i) if (par[i] == -1) {↵
dfs_dp(i);↵
ans += f[i][0][0];↵
}↵
printf("%.8lf\n", (double)ans * M_PI);↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Solution 2 - Greedy">↵
~~~~~↵
#include <cstdio>↵
#include <cmath>↵
#include <algorithm>↵
#include <vector>↵
typedef long long int64;↵
static const int MAXN = 1004;↵
#ifndef M_PI↵
static const double M_PI = acos(-1.0);↵
#endif↵
↵
int n;↵
int x[MAXN], y[MAXN], r[MAXN];↵
int par[MAXN];↵
std::vector<int> e[MAXN];↵
↵
bool level[MAXN];↵
↵
// Whether one of C[u] and C[v] is contained in another↵
inline bool circle_contains(int u, int v)↵
{↵
return ((int64)(x[u] - x[v]) * (x[u] - x[v]) + (int64)(y[u] - y[v]) * (y[u] - y[v]) <= (int64)(r[u] - r[v]) * (r[u] - r[v]));↵
}↵
↵
void dfs_colour(int u, bool c)↵
{↵
level[u] = c;↵
for (int v : e[u]) dfs_colour(v, c ^ 1);↵
}↵
↵
int main()↵
{↵
scanf("%d", &n);↵
for (int i = 0; i < n; ++i) scanf("%d%d%d", &x[i], &y[i], &r[i]);↵
↵
for (int i = 0; i < n; ++i) {↵
par[i] = -1;↵
for (int j = 0; j < n; ++j)↵
if (r[j] > r[i] && circle_contains(i, j)) {↵
if (par[i] == -1 || r[par[i]] > r[j]) par[i] = j;↵
}↵
e[par[i]].push_back(i);↵
}↵
↵
for (int i = 0; i < n; ++i) if (par[i] == -1) dfs_colour(i, false);↵
int64 ans = 0;↵
for (int i = 0; i < n; ++i)↵
ans += (int64)r[i] * r[i] * (par[i] == -1 || (level[i] == true) ? +1 : -1);↵
printf("%.8lf\n", (double)ans * M_PI);↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
[tutorial:814E]↵
↵
<spoiler summary="Solution 1 - O(n^5)">↵
~~~~~↵
#include <cstdio>↵
#include <cstring>↵
typedef long long int64;↵
static const int MAXN = 52;↵
static const int MODULUS = 1e9 + 7;↵
#define _ % MODULUS↵
#define __ %= MODULUS↵
↵
int n, d[MAXN];↵
int64 f[2][MAXN][MAXN][MAXN][MAXN] = {{{{{ 0 }}}}};↵
↵
int main()↵
{↵
scanf("%d", &n);↵
for (int i = 0; i < n; ++i) scanf("%d", &d[i]);↵
↵
int cur = 0, next = 1;↵
f[cur][d[0] == 2][d[0] == 3][d[1] == 2][d[1] == 3] = 1;↵
for (int i = 1; i < n - 1; ++i) {↵
memset(f[next], 0, sizeof f[next]);↵
for (int p1 = 0; p1 <= n; ++p1)↵
for (int p2 = 0; p1 + p2 <= n; ++p2)↵
for (int c1 = 0; c1 + p1 + p2 <= n; ++c1)↵
for (int c2 = 0; c1 + c2 + p1 + p2 <= n; ++c2) if (f[cur][p1][p2][c1][c2] > 0) {↵
int64 val = f[cur][p1][p2][c1][c2];↵
// (1) Start a new level↵
if (p1 == 0 && p2 == 0) {↵
(f[cur][c1][c2][0][0] += val)__;↵
continue;↵
}↵
// (2) Stay on current level↵
// Which type of vertex in the last level?↵
for (int last_level = 0; last_level <= 1; ++last_level) {↵
int last_ways;↵
if (last_level == 0) {↵
last_ways = p1;↵
if (--p1 < 0) { ++p1; continue; }↵
} else {↵
last_ways = p2;↵
if (--p2 < 0) { ++p2; continue; } else ++p1;↵
}↵
// Which type of vertices in the current level?↵
if (d[i + 1] == 2) {↵
// a) Leave as it is↵
(f[next][p1][p2][c1 + 1][c2] += val * last_ways)__;↵
// b) 1-plug↵
if (c1 >= 1)↵
(f[next][p1][p2][c1 - 1][c2] += val * last_ways * c1)__;↵
// c) 2-plug↵
if (c2 >= 1)↵
(f[next][p1][p2][c1 + 1][c2 - 1] += val * last_ways * c2)__;↵
} else {↵
// a) Leave as it is↵
(f[next][p1][p2][c1][c2 + 1] += val * last_ways)__;↵
// b) 1-plug↵
if (c1 >= 1)↵
(f[next][p1][p2][c1][c2] += val * last_ways * c1)__;↵
// c) 2-plug↵
if (c2 >= 1)↵
(f[next][p1][p2][c1 + 2][c2 - 1] += val * last_ways * c2)__;↵
// d) 1-plug + 1-plug↵
if (c1 >= 2)↵
(f[next][p1][p2][c1 - 2][c2] += val * last_ways * c1 * (c1 - 1) / 2)__;↵
// e) 2-plug + 2-plug↵
if (c2 >= 2)↵
(f[next][p1][p2][c1 + 2][c2 - 2] += val * last_ways * c2 * (c2 - 1) / 2)__;↵
// f) 1-plug + 2-plug↵
if (c1 >= 1 && c2 >= 1)↵
(f[next][p1][p2][c1][c2 - 1] += val * last_ways * c1 * c2)__;↵
}↵
if (last_level == 0) ++p1; else ++p2, --p1;↵
}↵
}↵
cur ^= 1, next ^= 1;↵
}↵
↵
printf("%lld\n", f[cur][0][0][0][0]);↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Solution 2 - O(n^3) by KAN">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
using ll = long long;↵
using ld = long double;↵
using D = double;↵
using uint = unsigned int;↵
template<typename T>↵
using pair2 = pair<T, T>;↵
↵
#ifdef WIN32↵
#define LLD "%I64d"↵
#else↵
#define LLD "%lld"↵
#endif↵
↵
#define pb push_back↵
#define mp make_pair↵
#define all(x) (x).begin(),(x).end()↵
#define fi first↵
#define se second↵
↵
const int maxn = 55;↵
const int MOD = 1000000007;↵
↵
int ways[maxn][maxn][maxn];↵
int answer[maxn][maxn];↵
int n;↵
int d[maxn];↵
int sumd[maxn];↵
↵
inline void add(int &a, ll b)↵
{↵
a = (a + b) % MOD;↵
}↵
↵
int main()↵
{↵
scanf("%d", &n);↵
for (int i = 0; i < n; i++) scanf("%d", &d[i]);↵
↵
ways[0][0][0] = 1;↵
for (int c0 = 0; c0 <= n; c0++)↵
{↵
for (int c2 = 0; c2 <= n; c2++)↵
{↵
for (int c1 = 0; c1 <= n; c1++) if (c1 + c2 > 0)↵
{↵
if (c2 > 0)↵
{↵
if (c0 > 1) add(ways[c0][c1][c2], (ll)ways[c0 - 2][c1][c2 - 1] * (c0 * (c0 - 1) / 2)); // 2-0, 2-0↵
if (c2 > 1 && c0 > 0) add(ways[c0][c1][c2], (ll)ways[c0 - 1][c1 + 1][c2 - 2] * (c2 - 1) * c0); // 2-2, 2-0↵
if (c2 > 2) add(ways[c0][c1][c2], (ll)ways[c0][c1 + 2][c2 - 3] * ((c2 - 1) * (c2 - 2) / 2)); // 2-2, 2-2↵
if (c1 > 0 && c2 > 1) add(ways[c0][c1][c2], (ll)ways[c0][c1][c2 - 2] * c1 * (c2 - 1)); // 2-2, 2-1↵
if (c1 > 0 && c0 > 0) add(ways[c0][c1][c2], (ll)ways[c0 - 1][c1 - 1][c2 - 1] * c1 * c0); // 2-1, 2-0↵
if (c1 > 1) add(ways[c0][c1][c2], (ll)ways[c0][c1 - 2][c2 - 1] * (c1 * (c1 - 1) / 2)); // 2-1, 2-1↵
} else↵
{↵
if (c0 > 0) add(ways[c0][c1][c2], ways[c0 - 1][c1 - 1][c2] * c0); // 1-0↵
if (c1 > 1) add(ways[c0][c1][c2], (ll)ways[c0][c1 - 2][c2] * (c1 - 1)); // 1-1↵
}↵
}↵
}↵
}↵
↵
for (int i = 0; i < n; i++) sumd[i + 1] = sumd[i] + d[i];↵
answer[n][n - 1] = 1;↵
for (int l = n - 1; l > 0; l--)↵
{↵
for (int r = l; r < n; r++)↵
{↵
int cnt2 = sumd[r + 1] - sumd[l] - 2 * (r - l + 1);↵
int cnt1 = r - l + 1 - cnt2;↵
for (int nextlvl = 0; nextlvl <= 2 * cnt2 + cnt1 && nextlvl <= n; nextlvl++)↵
{↵
int curways = ways[nextlvl][cnt1][cnt2];↵
if (r + nextlvl < n)↵
{↵
add(answer[l][r], (ll)answer[r + 1][r + nextlvl] * curways);↵
}↵
}↵
}↵
}↵
if (d[0] + 1 > n) cout << 0 << endl;↵
else cout << answer[1][d[0]] << endl;↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
This is the round with the most solutions so far perhaps? There are at least $3 \times 2 \times 3 \times 3 \times 3 = 162$ different ways to pass all problems in this round =D↵
↵
> Pla-tinum happy though I'm supposed to be ↵
> Pla-tinum sad is somehow how I get↵
↵
Personally I'd like to express my gratitude to the community for creating this amazing first-time experience for me. Thank you, and see you next round. Probably it will be for Ha... Well, let's wait and see :)↵
↵
Cheers \\(^ ^)/
