#include <iostream>
#include <vector>
#include <bitset>
using ll = long long;
using namespace std;
void solve_smallk(int k) {
for (int m = 1; m < (1 << 16); m += 2) {
vector<bitset<4>> v(4);
for (int i = 0; i < 4; ++i) for (int j = 0; j < 4; ++j) {
v[i][j] = m & (1 << (i * 4 + j));
}
vector<vector<pair<int, int>>> dp(5, vector<pair<int, int>>(5, {0, 0}));
dp[0][0] = {1, 0};
for (int i = 0; i < 4; ++i) for (int j = 0; j < 4; ++j) {
if (v[i][j]) {
dp[i + 1][j].first += dp[i][j].first + dp[i][j].second;
dp[i][j + 1].second += dp[i][j].first + dp[i][j].second;
} else {
dp[i + 1][j].first += dp[i][j].first;
dp[i][j + 1].second += dp[i][j].second;
}
}
int ans = 0;
for (int i = 0; i < 5; ++i) {
ans += dp[4][i].first + dp[i][4].second;
}
if (ans == k) {
cout << "5 5\n";
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
cout << (v[i][j] ? 'X' : '.');
}
cout << "d\n";
}
cout << "rrrr.\n";
return;
}
}
cout << "-1\n";
}
struct cell {
int i;
int j;
int t;
cell() {}
cell(int i_, int j_, int t_): i(i_), j(j_), t(t_) {}
cell reverse() {
return {j, i, (3 - t) % 3};
}
};
vector<cell> solve_recurs(ll k, int n, int m) {
if (n <= 0)
return {};
if (k == 1)
return {{0, 0, 1}};
if (n > m) {
vector<cell> ans = solve_recurs(k, m , n);
for (auto& x : ans)
x = x.reverse();
return ans;
}
if (k % 2 == 0) {
vector<cell> ans = solve_recurs(k / 2, n - 1, m - 1);
if (ans.empty())
return {};
for (auto& x : ans)
++x.i, ++x.j;
ans.push_back({0, 0, 0});
ans.push_back({0, 1, 1});
ans.push_back({1, 0, 2});
return ans;
}
vector<cell> ans = solve_recurs(k - 1, n, m - 1);
if (ans.empty())
return {};
for (auto& x : ans)
++x.j;
ans.push_back({0, 0 ,0});
return ans;
}
signed main() {
ll k;
cin >> k;
if (k <= 19) {
solve_smallk(k);
return 0;
}
vector<char> symbols = {'.', 'X', 'd', 'r'};
for (int n = 1; n <= 200; ++n) {
vector<cell> ans = solve_recurs(k, n - 1, n - 1);
if (ans.empty())
continue;
vector<vector<int>> v(n, vector<int>(n, -1));
for (int i = 0; i < n - 1; ++i)
v[i][n - 1] = 1, v[n - 1][i] = 2;
for (auto x : ans) if (x.t != -6)
v[x.i][x.j] = x.t;
cout << n << ' ' << n << '\n';
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << symbols[v[i][j] + 1];
}
cout << '\n';
}
return 0;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Correct! Your size: 5 |
2 |
Correct |
1 ms |
212 KB |
Correct! Your size: 5 |
3 |
Correct |
1 ms |
212 KB |
Correct! Your size: 5 |
4 |
Correct |
1 ms |
212 KB |
Correct! Your size: 5 |
5 |
Correct |
1 ms |
232 KB |
Correct! Your size: 5 |
6 |
Correct |
1 ms |
212 KB |
Correct! Your size: 5 |
7 |
Correct |
0 ms |
212 KB |
Correct! Your size: 5 |
8 |
Correct |
1 ms |
212 KB |
Correct! Your size: 5 |
9 |
Correct |
1 ms |
212 KB |
Correct! Your size: 5 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
1 ms |
340 KB |
Partially Correct! Your size: 73 |
2 |
Partially correct |
1 ms |
340 KB |
Partially Correct! Your size: 77 |
3 |
Partially correct |
1 ms |
340 KB |
Partially Correct! Your size: 77 |
4 |
Partially correct |
1 ms |
296 KB |
Partially Correct! Your size: 69 |
5 |
Partially correct |
1 ms |
340 KB |
Partially Correct! Your size: 75 |
6 |
Partially correct |
1 ms |
340 KB |
Partially Correct! Your size: 73 |
7 |
Partially correct |
1 ms |
300 KB |
Partially Correct! Your size: 71 |
8 |
Partially correct |
1 ms |
340 KB |
Partially Correct! Your size: 73 |