Submission #814675

#	Time	Username	Problem	Language	Result	Execution time	Memory
814675		finn__	Chess Rush (CEOI20_chessrush)	C++17	51 / 100	1362 ms	24612 KiB

chessrush

#include <bits/stdc++.h>
using namespace std;

constexpr size_t N = 100;
constexpr int64_t INF = 1LL << 42, MOD = 1000000007;

template <size_t L>
struct Matrix
{
    int64_t m[L][L][2];

    Matrix operator*(Matrix const &b) const
    {
        Matrix c;
        for (size_t i = 0; i < L; ++i)
            for (size_t j = 0; j < L; ++j)
                c.m[i][j][0] = INF, c.m[i][j][1] = 0;

        for (size_t i = 0; i < L; ++i)
            for (size_t j = 0; j < L; ++j)
                for (size_t k = 0; k < L; ++k)
                {
                    if (m[i][k][0] + b.m[k][j][0] < c.m[i][j][0])
                        c.m[i][j][0] = m[i][k][0] + b.m[k][j][0], c.m[i][j][1] = 0;
                    if (m[i][k][0] + b.m[k][j][0] == c.m[i][j][0])
                        c.m[i][j][1] = (c.m[i][j][1] + m[i][k][1] * b.m[k][j][1]) % MOD;
                }

        return c;
    }

    array<int64_t[2], L> operator*(array<int64_t[2], L> const &b)
    {
        array<int64_t[2], L> c;
        for (size_t i = 0; i < L; ++i)
            c[i][0] = INF, c[i][1] = 0;

        for (size_t i = 0; i < L; ++i)
            for (size_t j = 0; j < L; ++j)
            {
                if (m[i][j][0] + b[j][0] < c[i][0])
                    c[i][0] = m[i][j][0] + b[j][0], c[i][1] = 0;
                if (m[i][j][0] + b[j][0] == c[i][0])
                    c[i][1] = (c[i][1] + m[i][j][1] * b[j][1]) % MOD;
            }

        return c;
    }
};

Matrix<2 * N> bpow[31];
Matrix<N> kpow[31];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int r, c, q;
    cin >> r >> c >> q;

    // Build matrix for bishop

    for (size_t i = 0; i < 2 * N; ++i)
        for (size_t j = 0; j < 2 * N; ++j)
        {
            bpow[1].m[i][j][0] = INF;
            bpow[1].m[i][j][1] = 0;
        }

    for (size_t i = 0; i < c; ++i)
    {
        // d = 0
        if (i + 1 < c)
        {
            bpow[1].m[i][i + 1][0] = 0;
            bpow[1].m[i][i + 1][1] = 1;
            bpow[1].m[i][i + 1 + N][0] = 1;
            bpow[1].m[i][i + 1 + N][1] = 1;
        }
        // d = 1
        if (i)
        {
            bpow[1].m[i + N][i - 1][0] = 1;
            bpow[1].m[i + N][i - 1][1] = 1;
            bpow[1].m[i + N][i - 1 + N][0] = 0;
            bpow[1].m[i + N][i - 1 + N][1] = 1;
        }
    }

    for (size_t i = 2; i < 31; ++i)
        bpow[i] = bpow[i - 1] * bpow[i - 1];

    // Build king matrix for king

    for (size_t i = 0; i < N; ++i)
        for (size_t j = 0; j < N; ++j)
        {
            kpow[1].m[i][j][0] = INF;
            kpow[1].m[i][j][1] = 0;
        }

    for (int i = 0; i < c; ++i)
        for (int j = 0; j < c; ++j)
            kpow[1].m[i][j][0] = kpow[1].m[i][j][1] = max(1, abs(i - j));

    for (size_t i = 2; i < 31; ++i)
        kpow[i] = kpow[i - 1] * kpow[i - 1];

    while (q--)
    {
        char type;
        int start, finish;
        cin >> type >> start >> finish;

        switch (type)
        {
        case 'P':
        {
            if (start == finish)
                cout << r - 1 << " 1\n";
            else
                cout << "0 0\n";
            break;
        }
        case 'R':
        {
            if (start == finish)
                cout << "1 1\n";
            else
                cout << "2 2\n";
            break;
        }
        case 'Q':
        {
            if (start == finish || abs(start - finish) == (r - 1))
                cout << "1 1\n";
            else
            {
                int ans = 4 + (r == c) * ((start == 1 || start == c) + (finish == 1 || finish == c));
                if ((r - abs(start - finish)) & 1)
                {
                    int side_space = (r - 1 - abs(start - finish)) / 2;
                    ans += min(start, finish) - side_space >= 1;
                    ans += max(start, finish) + side_space <= c;
                }
                cout << "2 " << ans << '\n';
            }
            break;
        }
        case 'B':
        {
            array<int64_t[2], 2 * N> state;
            for (size_t i = 0; i < 2 * N; ++i)
                state[i][0] = INF, state[i][1] = 0;
            state[start - 1][0] = 1;
            state[start - 1][1] = 1;
            state[start - 1 + N][0] = 1;
            state[start - 1 + N][1] = 1;

            size_t k = r - 1, i = 1;
            while (k)
            {
                if (k & 1)
                    state = bpow[i] * state;
                ++i;
                k >>= 1;
            }

            int64_t num_turns = min(state[finish - 1][0], state[finish - 1 + N][0]),
                    num_ways = 0;
            if (state[finish - 1][0] == num_turns)
                num_ways += state[finish - 1][1];
            if (state[finish - 1 + N][0] == num_turns)
                num_ways += state[finish - 1 + N][1];

            if (num_turns == INF)
                cout << "0 0\n";
            else
                cout << num_turns << ' ' << num_ways << '\n';
            break;
        }
        case 'K':
        {
            array<int64_t[2], N> state;
            for (size_t i = 0; i < N; ++i)
                state[i][0] = INF, state[i][1] = 0;
            state[start - 1][0] = 0;
            state[start - 1][1] = 1;

            size_t k = r - 1, i = 1;
            while (k)
            {
                if (k & 1)
                    state = kpow[i] * state;
                ++i;
                k >>= 1;
            }

            cout << state[finish - 1][0] << ' ' << state[finish - 1][1] << '\n';
            break;
        }
        }
    }
}

Compilation message (stderr)

chessrush.cpp: In function 'int main()':
chessrush.cpp:71:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |     for (size_t i = 0; i < c; ++i)
      |                        ~~^~~
chessrush.cpp:74:19: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |         if (i + 1 < c)
      |             ~~~~~~^~~

• Subtask 1: 0 / 0
• Subtask 2: 8 / 8
• Subtask 3: 15 / 15
• Subtask 4: 0 / 22
• Subtask 5: 5 / 5
• Subtask 6: 8 / 8
• Subtask 7: 15 / 15
• Subtask 8: 0 / 20
• Subtask 9: 0 / 7