#ifdef LC
#include "pch.h"
#else
#include <bits/stdc++.h>
#endif
using namespace std;
using ll = long long;
#define int ll
#define all(x) x.begin(), x.end()
#define x first
#define y second
#define mp make_pair
#define mt make_tuple
const int N = 52;
const int INF = 4e18;
int C[N][N];
int k;
int n = 49;
char a[N][N];
int dd[N][N], dr[N][N];
int calc() {
fill_n(dd[0], N * N, 0);
fill_n(dr[0], N * N, 0);
for (int i = 0; i < n; ++i) {
dd[i][n - 1] = dd[n - 1][i] = 1;
dr[i][n - 1] = dr[n - 1][i] = 1;
}
for (int i = n - 2; i >= 0; --i) {
for (int j = n - 2; j >= 0; --j) {
if (a[i][j] == '.') {
dd[i][j] = dd[i + 1][j];
dr[i][j] = dr[i][j + 1];
} else if (a[i][j] == 'r') {
dd[i][j] = dr[i][j] = dr[i][j + 1];
} else if (a[i][j] == 'd') {
dd[i][j] = dr[i][j] = dd[i + 1][j];
} else {
dd[i][j] = dr[i][j] = dd[i + 1][j] + dr[i][j + 1];
}
assert(dd[i][j] < INF && dr[i][j] < INF);
}
}
return dd[0][0];
}
signed main() {
#ifdef LC
assert(freopen("input.txt", "r", stdin));
#endif
ios::sync_with_stdio(0); cin.tie(0);
for (int i = 0; i < N; ++i) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; ++j) {
C[i][j] = min(INF, C[i - 1][j] + C[i - 1][j - 1]);
}
}
cin >> k;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
a[i][j] = '.';
}
}
a[0][0] = 'X';
for (int i = 1; i < 46; i += 2) {
a[i][i] = a[i][i + 1] = a[i + 1][i] = a[i + 1][i + 1] = 'X';
a[i + 2][i] = a[i + 2][i + 1] = 'r';
a[i][i + 2] = a[i + 1][i + 2] = 'd';
}
for (int i = 0; i < n - 1; ++i) {
a[i][n - 1] = 'd';
a[n - 1][i] = 'r';
}
for (int i = 1; i < n; ++i) {
a[i][0] = 'd';
a[0][i] = 'r';
}
vector<tuple<int, int, int>> kn;
auto upd = [&](int i, int j) {
char old = a[i][j];
int f0 = calc();
a[i][j] = 'X';
int f1 = calc();
a[i][j] = old;
kn.emplace_back(f1 - f0, i, j);
};
for (int i = 1; i < n - 1; ++i) {
upd(0, i);
upd(i, 0);
}
sort(kn.rbegin(), kn.rend());
int least = k - 2;
for (auto e : kn) {
int delta, i, j;
tie(delta, i, j) = e;
if (least >= delta) {
least -= delta;
a[i][j] = 'X';
}
}
assert(calc() == k);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << a[i][j];
}
cout << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
332 KB |
Expected integer, but "Xrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
332 KB |
Expected integer, but "XrrXrrrXrrrrrXrrrrrXrrrrrrrXrrrXrXrrrrrrrrrrrXrXr" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
