제출 #315054

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
315054		casperwang	Costinland (info1cup19_costinland)	C++14	0 / 100	2 ms	204 KiB

costinland

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 70;
int K, N;
char ans[MAXN][MAXN];

int solve(char a[MAXN][MAXN], int N) {
  int dp[MAXN][MAXN][2];
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      dp[i][j][0] = dp[i][j][1] = 0;
  dp[0][0][0] = 1;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (i == N-1 && j == N-1) break;
      if (a[i][j] == 'X') {
        dp[i+1][j][0] += dp[i][j][0] + dp[i][j][1];
        dp[i][j+1][1] += dp[i][j][0] + dp[i][j][1];
      } else if (a[i][j] == '.') {
        dp[i+1][j][0] += dp[i][j][0];
        dp[i][j+1][1] += dp[i][j][1];
      } else if (a[i][j] == 'r') {
        dp[i][j+1][1] += dp[i][j][0] + dp[i][j][1];
      } else if (a[i][j] == 'd') {
        dp[i+1][j][0] += dp[i][j][0] + dp[i][j][1];
      }
    }
  }
  return dp[N-1][N-1][0] + dp[N-1][N-1][1];
}

void mkarr(int K, int N) {
  for (int i = 0; i < N; i++) {
    ans[i][N-1] = 'd';
    ans[N-1][i] = 'r';
  }
  ans[N-1][N-1] = '.';
  for (int i = 0; i+1 < N; i++) {
    for (int j = 0; j+1 < N; j++) {
      if (i == j)
        ans[i][j] = 'X';
      else if (i+1 == j)
        ans[i][j] = 'd';
      else if (j+1 == i)
        ans[i][j] = 'r';
      else
        ans[i][j] = '.';
    }
  }
  if (K != (1LL<<(N-1))) {
    ans[0][1] = ans[1][0] = 'X';
    int c = -1, sum = (1LL<<(N-1));
    for (int j = 2; j+1 < N; j++) {
      if ((1LL<<(N-j)) & K) {
        c = j, ans[0][j] = ans[j][0] = 'X';
        sum += (1LL<<(N-j));
      }
    }
    sum += 2;
    if (sum >= K + 1 && c != -1) ans[0][c] = 'd';
    if (sum >= K + 2 && c != -1) ans[c][0] = 'r';
    //cout << sum << "\n";
  }
 /* 
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cout << ans[i][j];
    }
    cout << "\n";
  }
  */ 
}

int lb(int a) {
  return a &- a;
}

signed main() {
  cin >> K;
  int t = K;
  while (t != lb(t)) t -= lb(t);
  N = __lg(t*2);
  mkarr(K, N);
  if (K == 3) {
    N = 3;
    ans[0][0] = 'X';
    ans[1][0] = 'X';
    ans[2][0] = ans[0][1] = ans[1][1] = '.';
    ans[2][0] = ans[2][1] = 'r';
    ans[0][2] = ans[1][2] = 'd';
    ans[2][2] = '.';
  }
  cout << N << " " << N << "\n";
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cout << ans[i][j];
    }
    cout << "\n";
  }
  //cout << solve(ans, N) << "\n";
  return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80