oj.uz

Submission #815249

# Submission time Handle Problem Language Result Execution time Memory
815249 2023-08-08T13:30:10 Z finn__ Chess Rush (CEOI20_chessrush) C++17
36 / 100
 1028 ms 5312 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
                {
                    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 35 ms 5160 KB Output is correct
2 Incorrect 133 ms 5116 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 33 ms 5156 KB Output is correct
3 Correct 34 ms 5080 KB Output is correct
4 Correct 101 ms 5100 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5064 KB Output is correct
2 Incorrect 37 ms 5096 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 5064 KB Output is correct
2 Incorrect 37 ms 5096 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 38 ms 5140 KB Output is correct
2 Correct 104 ms 5096 KB Output is correct
3 Correct 86 ms 5108 KB Output is correct
4 Correct 35 ms 5160 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5140 KB Output is correct
2 Correct 104 ms 5096 KB Output is correct
3 Correct 86 ms 5108 KB Output is correct
4 Correct 35 ms 5160 KB Output is correct
5 Correct 80 ms 5312 KB Output is correct
6 Correct 82 ms 5296 KB Output is correct
7 Correct 132 ms 5112 KB Output is correct
8 Correct 178 ms 5144 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5140 KB Output is correct
2 Correct 104 ms 5096 KB Output is correct
3 Correct 86 ms 5108 KB Output is correct
4 Correct 35 ms 5160 KB Output is correct
5 Correct 80 ms 5312 KB Output is correct
6 Correct 82 ms 5296 KB Output is correct
7 Correct 132 ms 5112 KB Output is correct
8 Correct 178 ms 5144 KB Output is correct
9 Correct 163 ms 5176 KB Output is correct
10 Correct 365 ms 5248 KB Output is correct
11 Correct 1028 ms 5184 KB Output is correct
12 Correct 759 ms 5196 KB Output is correct
13 Correct 212 ms 5168 KB Output is correct
14 Correct 32 ms 5132 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5140 KB Output is correct
2 Correct 104 ms 5096 KB Output is correct
3 Correct 86 ms 5108 KB Output is correct
4 Correct 35 ms 5160 KB Output is correct
5 Correct 80 ms 5312 KB Output is correct
6 Correct 82 ms 5296 KB Output is correct
7 Correct 132 ms 5112 KB Output is correct
8 Correct 178 ms 5144 KB Output is correct
9 Correct 163 ms 5176 KB Output is correct
10 Correct 365 ms 5248 KB Output is correct
11 Correct 1028 ms 5184 KB Output is correct
12 Correct 759 ms 5196 KB Output is correct
13 Correct 212 ms 5168 KB Output is correct
14 Correct 32 ms 5132 KB Output is correct
15 Correct 211 ms 5308 KB Output is correct
16 Correct 220 ms 5136 KB Output is correct
17 Incorrect 343 ms 5180 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

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