Submission #315062

#	Time	Username	Problem	Language	Result	Execution time	Memory
315062		casperwang	Costinland (info1cup19_costinland)	C++14	20 / 100	1 ms	208 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] = '.';
  if (K < (1LL<<N-1)) {
    for (int i = 0; i+1 < N; i++) {
      for (int j = 0; j < (N-1-i); j++)
        ans[i][j] = 'X';
      for (int j = (N-1-i); j+1 < N; j++)
        ans[i][j] = '.';
    }
    ans[N-2][0] = '.';
    return;
  }
  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 a = 1, b = 1, sum = (1LL<<(N-1));
    for (int j = 2; j+1 < N; j++) {
      if ((1LL<<(N-j)) & K) {
        a = b = j, ans[0][j] = ans[j][0] = 'X';
        sum += (1LL<<(N-j));
      } else if ((1LL<<(N-j-1)) & K) {
        a = j, ans[0][j] = 'X';
        sum += (1LL<<(N-j-1));
      }
    }
    sum += 2;
    if (sum >= K + 1 && a != -1) ans[0][a] = 'd';
    if (sum >= K + 2 && b != -1) ans[b][0] = 'r';
  }
 /* 
  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 + 1;
  while (t != lb(t)) t -= lb(t);
  N = __lg(t*2);
  mkarr(K, N);
  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;
}

Compilation message (stderr)

costinland.cpp: In function 'void mkarr(long long int, long long int)':
costinland.cpp:40:18: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   40 |   if (K < (1LL<<N-1)) {
      |                 ~^~

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