oj.uz

Submission #815270

# Submission time Handle Problem Language Result Execution time Memory
815270 2023-08-08T13:42:37 Z finn__ Chess Rush (CEOI20_chessrush) C++17
36 / 100
 1029 ms 5308 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 = 1 + (r - 1 - (c - start) + c - 2) / (c - 1),
                        t = (((r - 1 - (c - start)) / (c - 1)) & 1) ? 1 : c;
                bool last_dir = t == 1;
                t += (last_dir ? 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
                {
                    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 31 ms 5068 KB Output is correct
2 Incorrect 134 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 5044 KB Output is correct
2 Correct 34 ms 5088 KB Output is correct
3 Correct 32 ms 5084 KB Output is correct
4 Correct 106 ms 5088 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5080 KB Output is correct
2 Incorrect 33 ms 5088 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 37 ms 5148 KB Output is correct
2 Correct 106 ms 5044 KB Output is correct
3 Correct 86 ms 5112 KB Output is correct
4 Correct 34 ms 5064 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 5148 KB Output is correct
2 Correct 106 ms 5044 KB Output is correct
3 Correct 86 ms 5112 KB Output is correct
4 Correct 34 ms 5064 KB Output is correct
5 Correct 77 ms 5308 KB Output is correct
6 Correct 78 ms 5112 KB Output is correct
7 Correct 138 ms 5180 KB Output is correct
8 Correct 176 ms 5068 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 5148 KB Output is correct
2 Correct 106 ms 5044 KB Output is correct
3 Correct 86 ms 5112 KB Output is correct
4 Correct 34 ms 5064 KB Output is correct
5 Correct 77 ms 5308 KB Output is correct
6 Correct 78 ms 5112 KB Output is correct
7 Correct 138 ms 5180 KB Output is correct
8 Correct 176 ms 5068 KB Output is correct
9 Correct 165 ms 5188 KB Output is correct
10 Correct 357 ms 5188 KB Output is correct
11 Correct 1029 ms 5068 KB Output is correct
12 Correct 761 ms 5084 KB Output is correct
13 Correct 213 ms 5172 KB Output is correct
14 Correct 33 ms 5124 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 5148 KB Output is correct
2 Correct 106 ms 5044 KB Output is correct
3 Correct 86 ms 5112 KB Output is correct
4 Correct 34 ms 5064 KB Output is correct
5 Correct 77 ms 5308 KB Output is correct
6 Correct 78 ms 5112 KB Output is correct
7 Correct 138 ms 5180 KB Output is correct
8 Correct 176 ms 5068 KB Output is correct
9 Correct 165 ms 5188 KB Output is correct
10 Correct 357 ms 5188 KB Output is correct
11 Correct 1029 ms 5068 KB Output is correct
12 Correct 761 ms 5084 KB Output is correct
13 Correct 213 ms 5172 KB Output is correct
14 Correct 33 ms 5124 KB Output is correct
15 Correct 211 ms 5292 KB Output is correct
16 Correct 223 ms 5184 KB Output is correct
17 Incorrect 346 ms 5172 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

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