oj.uz

Submission #315051

# Submission time Handle Problem Language Result Execution time Memory
315051 2020-10-22T01:40:58 Z casperwang Costinland (info1cup19_costinland) C++14
0 / 100
 2 ms 204 KB 
#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) ans[0][c] = 'd';
    if (sum >= K + 2) 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);
  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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB The output does not fit the requirements
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Partially Correct! Your size: 59
2 Incorrect 2 ms 204 KB The matrix does not generate the required number of Costins
3 Halted 0 ms 0 KB -