oj.uz

Submission #315043

# Submission time Handle Problem Language Result Execution time Memory
315043 2020-10-22T01:14:21 Z 2qbingxuan Costinland (info1cup19_costinland) C++14
63.589 / 100
 2 ms 208 KB 
#include <bits/stdc++.h>
#ifdef local
#define debug(args...) qqbx(#args, args)
template <typename ...T> void qqbx(const char *s, T ...args) {
    int cnt = sizeof...(T);
    (std::cerr << "(" << s << ") = (" , ... , (std::cerr << args << (--cnt ? ", " : ")\n")));
}
#else
#define debug(...) ((void)0)
#endif // local
#define pb emplace_back
#define all(v) begin(v), end(v)
using namespace std;
using ll = long long;

ll calc(vector<string> v) {
    int n = v.size(), m = v[0].size();
    vector<vector<array<ll,2>>> dp(n, vector<array<ll,2>>(m));
    dp[0][0][0] = 1;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) {
        if(i == n-1 && j == m-1) continue;
        if(v[i][j] == '.') {
            dp[i+1][j][0] += dp[i][j][0];
            dp[i][j+1][1] += dp[i][j][1];
        } else {
            ll s = dp[i][j][0] + dp[i][j][1];
            if(v[i][j] != 'r')
                dp[i+1][j][0] += s;
            if(v[i][j] != 'd')
                dp[i][j+1][1] += s;
        }
    }
    return dp[n-1][m-1][0] + dp[n-1][m-1][1];
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    ll k;
    cin >> k;
    /* int n, m; */
    /* cin >> n >> m; */
    /* for(int i = 0; i < n; i++) cin >> v[i]; */
    /* cout << calc(v) << '\n'; */
    int n = 0;
    while((1LL<<n) <= k) ++n;
    k -= (1LL<<n-1);
    debug(k);
    n += 1;
    debug(n);
    vector<string> v(n, string(n, '.'));
    for(int i = 0; i < n; i++) v[i][n-1] = 'd', v[n-1][i] = 'r';
    v[n-1][n-1] = '.';
    for(int i = 0; i < n-2; i++) {
        v[i][i] = 'X';
        v[i+1][i] = 'r';
        v[i][i+1] = 'd';
        if(k >> i & 1) {
            v[i][i+1] = 'X';
            k -= 1LL << i;
        }
    }
    cout << n << ' ' << n << '\n';
    for(int i = 0; i < n; i++) cout << v[i] << '\n';
    /* cout << calc(v) << '\n'; */
}

Compilation message

costinland.cpp: In function 'int main()':
costinland.cpp:45:17: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   45 |     k -= (1LL<<n-1);
      |                ~^~

Subtask #1
12.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: 4
3 Correct 1 ms 204 KB Correct! Your size: 4
4 Correct 1 ms 204 KB Correct! Your size: 4
5 Correct 1 ms 204 KB Correct! Your size: 4
6 Correct 1 ms 204 KB Correct! Your size: 5
7 Correct 1 ms 204 KB Correct! Your size: 5
8 Correct 1 ms 204 KB Correct! Your size: 5
9 Partially correct 1 ms 204 KB Partially Correct! Your size: 6

Subtask #2
51.589012952 / 80.0

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