oj.uz

Submission #315070

# Submission time Handle Problem Language Result Execution time Memory
315070 2020-10-22T02:08:47 Z casperwang Costinland (info1cup19_costinland) C++14
72.3068 / 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] = '.';
  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)) & (sum ^ K)) {
        a = b = j, ans[0][j] = ans[j][0] = 'X';
        sum += (1LL<<(N-j));
      } else if ((1LL<<(N-j-1)) & (sum ^ K)) {
        a = j, ans[0][j] = 'X';
        sum += (1LL<<(N-j-1));
      }
    }
    sum += 2;
    if (sum >= K+1) ans[0][a] = 'd';
    if (sum >= K+2) 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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct! Your size: 3
2 Correct 1 ms 204 KB Correct! Your size: 3
3 Correct 1 ms 204 KB Correct! Your size: 3
4 Correct 1 ms 204 KB Correct! Your size: 3
5 Correct 1 ms 204 KB Correct! Your size: 4
6 Correct 1 ms 204 KB Correct! Your size: 4
7 Correct 1 ms 204 KB Correct! Your size: 4
8 Correct 1 ms 204 KB Correct! Your size: 4
9 Correct 1 ms 204 KB Correct! Your size: 5

Subtask #2
52.306815544 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Partially Correct! Your size: 59
2 Partially correct 1 ms 204 KB Partially Correct! Your size: 59
3 Partially correct 2 ms 204 KB Partially Correct! Your size: 60
4 Partially correct 1 ms 204 KB Partially Correct! Your size: 60
5 Partially correct 1 ms 204 KB Partially Correct! Your size: 60
6 Partially correct 1 ms 204 KB Partially Correct! Your size: 60
7 Partially correct 1 ms 204 KB Partially Correct! Your size: 60
8 Partially correct 1 ms 204 KB Partially Correct! Your size: 58