oj.uz

Submission #815250

# Submission time Handle Problem Language Result Execution time Memory
815250 2023-08-08T13:31:36 Z finn__ Chess Rush (CEOI20_chessrush) C++17
36 / 100
 1041 ms 5292 KB 
#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;
    }
};

template <typename T>
T binary_exp(T x, T y)
{
    T z = 1;

    while (y)
    {
        if (y & 1)
            z = (z * x) % MOD;
        x = (x * x) % MOD;
        y >>= 1;
    }

    return z;
}

template <typename T>
T modular_inverse(T x) { return binary_exp(x, MOD - 2); }

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 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':
        {
            if (!((r - abs(start - finish)) & 1))
            {
                cout << "0 0\n";
                break;
            }

            if (abs(start - finish) == r - 1)
            {
                cout << "1 1\n";
                break;
            }

            // Solve for the case when the first move is to the right, then just swap positions
            auto solve_bishop = [&]()
            {
                if (start == c)
                    return make_pair((int64_t)INF, (int64_t)0);
                int64_t moves = 2 + (r - (c - start)) / (c - 1),
                        t = (moves & 1) ? 1 : c;
                bool last_dir = t == 1;
                t += (moves == 1 ? 1 : -1) * (r - 1 - (c - 1) * (moves - 2) - (c - start));
                if (t == finish)
                    return make_pair(moves, int64_t(1));

                int64_t f;
                if ((finish > t && last_dir) || (finish < t && !last_dir))
                {
                    f = abs(t - finish) / 2;
                }
                else
                {
                    ++moves;
                    if (last_dir)
                        f = c - (t + finish) / 2;
                    else
                        f = (t + finish) / 2 - 1;
                }

                int64_t num_ways = 1;
                for (int64_t i = 0; i < f; ++i)
                    num_ways = (num_ways * (moves - 1 + i)) % MOD;
                int64_t factorial = 1;
                for (int64_t i = 2; i <= f; ++i)
                    factorial = (factorial * i) % MOD;
                num_ways = (num_ways * modular_inverse(factorial)) % MOD;

                return make_pair(moves, num_ways);
            };

            auto [dis_right, ways_right] = solve_bishop();
            start = c - start + 1;
            finish = c - finish + 1;
            auto [dis_left, ways_left] = solve_bishop();

            int64_t dis = min(dis_left, dis_right);
            int64_t ways = 0;
            if (dis == dis_left)
                ways += ways_left;
            if (dis == dis_right)
                ways += ways_right;

            cout << dis << ' ' << ways % MOD << '\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;
        }
        }
    }
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5068 KB Output is correct
2 Incorrect 133 ms 5092 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5068 KB Output is correct
2 Correct 34 ms 5132 KB Output is correct
3 Correct 35 ms 5148 KB Output is correct
4 Correct 102 ms 5084 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5144 KB Output is correct
2 Incorrect 32 ms 5040 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5144 KB Output is correct
2 Incorrect 32 ms 5040 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 5188 KB Output is correct
2 Correct 105 ms 5084 KB Output is correct
3 Correct 86 ms 5116 KB Output is correct
4 Correct 33 ms 5112 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 5188 KB Output is correct
2 Correct 105 ms 5084 KB Output is correct
3 Correct 86 ms 5116 KB Output is correct
4 Correct 33 ms 5112 KB Output is correct
5 Correct 77 ms 5168 KB Output is correct
6 Correct 79 ms 5060 KB Output is correct
7 Correct 139 ms 5200 KB Output is correct
8 Correct 177 ms 5180 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 5188 KB Output is correct
2 Correct 105 ms 5084 KB Output is correct
3 Correct 86 ms 5116 KB Output is correct
4 Correct 33 ms 5112 KB Output is correct
5 Correct 77 ms 5168 KB Output is correct
6 Correct 79 ms 5060 KB Output is correct
7 Correct 139 ms 5200 KB Output is correct
8 Correct 177 ms 5180 KB Output is correct
9 Correct 160 ms 5176 KB Output is correct
10 Correct 372 ms 5292 KB Output is correct
11 Correct 1041 ms 5168 KB Output is correct
12 Correct 769 ms 5180 KB Output is correct
13 Correct 210 ms 5180 KB Output is correct
14 Correct 43 ms 5072 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 5188 KB Output is correct
2 Correct 105 ms 5084 KB Output is correct
3 Correct 86 ms 5116 KB Output is correct
4 Correct 33 ms 5112 KB Output is correct
5 Correct 77 ms 5168 KB Output is correct
6 Correct 79 ms 5060 KB Output is correct
7 Correct 139 ms 5200 KB Output is correct
8 Correct 177 ms 5180 KB Output is correct
9 Correct 160 ms 5176 KB Output is correct
10 Correct 372 ms 5292 KB Output is correct
11 Correct 1041 ms 5168 KB Output is correct
12 Correct 769 ms 5180 KB Output is correct
13 Correct 210 ms 5180 KB Output is correct
14 Correct 43 ms 5072 KB Output is correct
15 Correct 207 ms 5184 KB Output is correct
16 Correct 223 ms 5176 KB Output is correct
17 Incorrect 347 ms 5184 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5068 KB Output is correct
2 Incorrect 133 ms 5092 KB Output isn't correct
3 Halted 0 ms 0 KB -