oj.uz

Submission #815288

# Submission time Handle Problem Language Result Execution time Memory
815288 2023-08-08T13:56:20 Z finn__ Chess Rush (CEOI20_chessrush) C++17
73 / 100
 1039 ms 5260 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 - 2) / (c - 1) - 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
                {
                    ++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 5048 KB Output is correct
2 Incorrect 144 ms 5068 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 35 ms 5124 KB Output is correct
2 Correct 32 ms 5160 KB Output is correct
3 Correct 33 ms 5040 KB Output is correct
4 Correct 103 ms 5092 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 5044 KB Output is correct
2 Correct 46 ms 5068 KB Output is correct
3 Correct 35 ms 5064 KB Output is correct
4 Correct 34 ms 5076 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 5044 KB Output is correct
2 Correct 46 ms 5068 KB Output is correct
3 Correct 35 ms 5064 KB Output is correct
4 Correct 34 ms 5076 KB Output is correct
5 Correct 109 ms 5260 KB Output is correct
6 Correct 109 ms 5088 KB Output is correct
7 Correct 35 ms 5116 KB Output is correct
8 Correct 112 ms 5100 KB Output is correct
9 Correct 34 ms 5176 KB Output is correct
10 Correct 79 ms 5084 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5068 KB Output is correct
2 Correct 105 ms 5132 KB Output is correct
3 Correct 98 ms 5080 KB Output is correct
4 Correct 45 ms 5164 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5068 KB Output is correct
2 Correct 105 ms 5132 KB Output is correct
3 Correct 98 ms 5080 KB Output is correct
4 Correct 45 ms 5164 KB Output is correct
5 Correct 88 ms 5160 KB Output is correct
6 Correct 90 ms 5172 KB Output is correct
7 Correct 141 ms 5068 KB Output is correct
8 Correct 179 ms 5188 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5068 KB Output is correct
2 Correct 105 ms 5132 KB Output is correct
3 Correct 98 ms 5080 KB Output is correct
4 Correct 45 ms 5164 KB Output is correct
5 Correct 88 ms 5160 KB Output is correct
6 Correct 90 ms 5172 KB Output is correct
7 Correct 141 ms 5068 KB Output is correct
8 Correct 179 ms 5188 KB Output is correct
9 Correct 188 ms 5176 KB Output is correct
10 Correct 370 ms 5172 KB Output is correct
11 Correct 1039 ms 5168 KB Output is correct
12 Correct 775 ms 5180 KB Output is correct
13 Correct 223 ms 5184 KB Output is correct
14 Correct 56 ms 5052 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5068 KB Output is correct
2 Correct 105 ms 5132 KB Output is correct
3 Correct 98 ms 5080 KB Output is correct
4 Correct 45 ms 5164 KB Output is correct
5 Correct 88 ms 5160 KB Output is correct
6 Correct 90 ms 5172 KB Output is correct
7 Correct 141 ms 5068 KB Output is correct
8 Correct 179 ms 5188 KB Output is correct
9 Correct 188 ms 5176 KB Output is correct
10 Correct 370 ms 5172 KB Output is correct
11 Correct 1039 ms 5168 KB Output is correct
12 Correct 775 ms 5180 KB Output is correct
13 Correct 223 ms 5184 KB Output is correct
14 Correct 56 ms 5052 KB Output is correct
15 Correct 230 ms 5068 KB Output is correct
16 Correct 231 ms 5188 KB Output is correct
17 Incorrect 356 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 33 ms 5048 KB Output is correct
2 Incorrect 144 ms 5068 KB Output isn't correct
3 Halted 0 ms 0 KB -