Submission #754808

#	Time	Username	Problem	Language	Result	Execution time	Memory
754808		Stickfish	Costinland (info1cup19_costinland)	C++17	67.12 / 100	1 ms	340 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};
    }
};

struct block {
    int n;
    int m;
    ll d;
    vector<cell> cells;

    block() {};

    block(int n_, int m_, ll d_, vector<cell> cells_): n(n_), m(m_), d(d_), cells(cells_) {}
};

vector<block> blocks;

vector<cell> solve_recurs(ll k, int n, int m) {
    if (n <= 0 || m <= 0)
        return {};
    if (k == 1)
        return {{0, 0, 1}};
    if (n > m) {
        vector<cell> ans = solve_recurs(k, m , n);
        for (auto& x : ans)
            x = x.reverse();
        return ans;
    }

    for (auto b : blocks) {
        if (k % b.d || n < b.n || m < b.m)
            continue;
        vector<cell> ans = solve_recurs(k / b.d, n - b.n, m - b.m);
        if (ans.empty())
            return {};
        for (auto& x : ans)
            x.i += b.n, x.j += b.m;
        for (auto x : b.cells)
            ans.push_back(x);
        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;
}

void init_blocks() {
    blocks.push_back({
        1, 2, 3,
        {{0, 0, 0}, {0, 1, 0}, {0, 2, 1}, {1, 1, 2}, {1, 0, 2}}
    });
    blocks.push_back({
        1, 1, 2,
        {{0, 0, 0}, {0, 1, 1}, {1, 0, 2}}
    });
}

signed main() {
    ll k;
    cin >> k;
    if (k <= 19) {
        solve_smallk(k);
        return 0;
    }
    init_blocks();
    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: 47.123287672 / 80