제출 #754804

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
754804		Stickfish	Costinland (info1cup19_costinland)	C++17	20 / 100	1 ms	212 KiB

costinland

#include <iostream>
#include <vector>
#include <bitset>
using ll = long long;
using namespace std;

void solve_smallk(int k) {
    for (int m = 1; m < (1 << 16); m += 2) {
        vector<bitset<4>> v(4);
        for (int i = 0; i < 4; ++i) for (int j = 0; j < 4; ++j) {
            v[i][j] = m & (1 << (i * 4 + j));
        }
        vector<vector<pair<int, int>>> dp(5, vector<pair<int, int>>(5, {0, 0}));
        dp[0][0] = {1, 0};
        for (int i = 0; i < 4; ++i) for (int j = 0; j < 4; ++j) {
            if (v[i][j]) {
                dp[i + 1][j].first += dp[i][j].first + dp[i][j].second;
                dp[i][j + 1].second += dp[i][j].first + dp[i][j].second;
            } else {
                dp[i + 1][j].first += dp[i][j].first;
                dp[i][j + 1].second += dp[i][j].second;
            }
        }
        int ans = 0;
        for (int i = 0; i < 5; ++i) {
            ans += dp[4][i].first + dp[i][4].second;
        }
        if (ans == k) {
            cout << "5 5\n";
            for (int i = 0; i < 4; ++i) {
                for (int j = 0; j < 4; ++j) {
                    cout << (v[i][j] ? 'X' : '.');
                }
                cout << "d\n";
            }
            cout << "rrrr.\n";
            return;
        }
    }
    cout << "-1\n";
}

struct cell {
    int i;
    int j;
    int t;

    cell() {}

    cell(int i_, int j_, int t_): i(i_), j(j_), t(t_) {}

    cell reverse() {
        return {j, i, (3 - t) % 3};
    }
};

vector<cell> solve_recurs(ll k, int n, int m) {
    if (n <= 0)
        return {};
    if (k == 1)
        return {{0, 0, -6}};
    if (n > m) {
        vector<cell> ans = solve_recurs(k, m , n);
        for (auto& x : ans)
            x = x.reverse();
        return ans;
    }
    if (k % 2 == 0) {
        vector<cell> ans = solve_recurs(k / 2, n - 1, m - 1);
        if (ans.empty())
            return {};
        for (auto& x : ans)
            ++x.i, ++x.j;
        ans.push_back({0, 0, 0});
        ans.push_back({0, 1, 1});
        ans.push_back({1, 0, 2});
        return ans;
    }
    vector<cell> ans = solve_recurs(k - 1, n, m - 1);
    if (ans.empty())
        return {};
    for (auto& x : ans)
        ++x.j;
    ans.push_back({0, 0 ,0});
    return ans;
}

signed main() {
    ll k;
    cin >> k;
    if (k <= 19) {
        solve_smallk(k);
        return 0;
    }
    vector<char> symbols = {'.', 'X', 'd', 'r'};
    for (int n = 1; n <= 200; ++n) {
        vector<cell> ans = solve_recurs(k, n - 1, n - 1);
        if (ans.empty())
            continue;
        vector<vector<int>> v(n, vector<int>(n, -1));
        for (int i = 0; i < n - 1; ++i)
            v[i][n - 1] = 1, v[n - 1][i] = 2;
        for (auto x : ans) if (x.t != -6)
            v[x.i][x.j] = x.t;
        
        cout << n << ' ' << n << '\n';
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cout << symbols[v[i][j] + 1];
            }
            cout << '\n';
        }
        return 0;
    }
}

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