#include <bits/stdc++.h>
#define int long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
char c[501][501];
void defa(int n, int m){
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(i != n - 1 && j != m - 1) { if(c[i][j] != 'X') c[i][j] = '.'; }
else if((i == n - 1) && (j == m - 1)) c[i][j] = '.';
else if(i == n - 1) c[i][j] = 'r';
else c[i][j] = 'd';
}
}
}
void pr(int n, int m){
cout << n << ' ' << m << endl;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cout << c[i][j];
}
cout << endl;
}
}
void part1(int K){
int n = 0, m = 0;
if(K <= 5){
n = 2; m = 5;
defa(n, m);
for(int i = 0; i < K - 1; i++){
c[0][i] = 'X';
}
pr(n, m);
}else if(K <= 8){
n = 5; m = 5;
defa(n, m);
for(int i = 0; i < 4; i++){
c[0][i] = 'X';
}
for(int i = 0; i < K - 4; i++){
c[i][0] = 'X';
}
pr(n, m);
}else if(K <= 10){
n = 5; m = 5;
defa(n, m);
for(int i = 0; i < 4; i++){
c[0][i] = 'X';
}
for(int i = 0; i < K - 6; i++){
c[i][0] = 'X';
}
c[1][1] = 'X';
pr(n, m);
}else if(K <= 12){
n = 5; m = 5;
defa(n, m);
for(int i = 0; i < 4; i++){
c[0][i] = 'X';
}
for(int i = 0; i < K - 8; i++){
c[i][0] = 'X';
}
c[1][1] = 'X';
c[2][2] = 'X';
pr(n, m);
}else if(K <= 16){
n = 5; m = 5;
defa(n, m);
for(int i = 0; i < 3; i++){
c[0][i] = c[1][i] = 'X';
}
K -= 10;
if(K){
c[2][min(3LL, K) - 1] = 'X';
K -= min(3LL, K);
}
if(K){
c[3][min(3LL, K) - 1] = 'X';
K -= min(3LL, K);
}
pr(n, m);
}else if(K <= 19){
n = 5; m = 5;
defa(n, m);
for(int i = 0; i < 4; i++){
c[0][i] = c[1][i] = 'X';
}
K -= 15;
if(K){
c[2][min(4LL, K) - 1] = 'X';
K -= min(4LL, K);
}
if(K){
c[3][min(4LL, K) - 1] = 'X';
K -= min(4LL, K);
}
pr(n, m);
}
}
__int128_t C[501][501];
bool part2(int K){
if(K <= 49){
int n = 49, m = 49; defa(n, m);
for(int i = 0; i < K - 1; i++) c[0][i] = 'X';
pr(n, m); return true;
}
int m = 49;
for(int l = 1; l <= 20; l++){
if(K <= C[m - 1][l + 1]){
K -= C[m - 1][l];
for(int j = 0; j < l; j++){
for(int i = 0; i <= m - 2; i++){
c[j][i] = 'X';
}
}
int j = l;
for(;; j++){
for(int k = m - 2; k >= 0; k--){
if(K >= C[k][l - 1]){
K -= C[k][l - 1];
c[j][k] = 'X';
}
}
if(K == 0) break;
vector<int> v;
for(int k = 0; k <= m - 2; k++){
if(c[j][k] == 'X') v.push_back(k);
}
for(int i = 0; i + 1 < v.size(); i++){
C[v[i + 1]][l - 1] += C[v[i]][l - 1];
}
}
int n = j + 2; defa(n, m); pr(n, m);
return true;
}
}
return false;
}
int32_t main(){
for(int i = 0; i <= 500; i++){
C[i][0] = C[0][i] = 1;
}
for(int i = 1; i <= 500; i++){
for(int j = 1; j <= 500; j++){
C[i][j] = C[i - 1][j] + C[i][j - 1];
}
}
int K; cin >> K;
if(K <= 19){
part1(K);
}else{
part2(K);
}
}
Compilation message
costinland.cpp: In function 'bool part2(long long int)':
costinland.cpp:137:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for(int i = 0; i + 1 < v.size(); i++){
| ~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4180 KB |
Correct! Your size: 5 |
| 2 |
Correct |
3 ms |
4180 KB |
Correct! Your size: 5 |
| 3 |
Correct |
3 ms |
4180 KB |
Correct! Your size: 5 |
| 4 |
Correct |
2 ms |
4180 KB |
Correct! Your size: 5 |
| 5 |
Correct |
3 ms |
4180 KB |
Correct! Your size: 5 |
| 6 |
Correct |
2 ms |
4180 KB |
Correct! Your size: 5 |
| 7 |
Correct |
3 ms |
4180 KB |
Correct! Your size: 5 |
| 8 |
Correct |
2 ms |
4180 KB |
Correct! Your size: 5 |
| 9 |
Correct |
2 ms |
4180 KB |
Correct! Your size: 5 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4180 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
