oj.uz

Submission #815260

# Submission time Handle Problem Language Result Execution time Memory
815260 2023-08-08T13:35:24 Z finn__ Chess Rush (CEOI20_chessrush) C++17
36 / 100
 1048 ms 5272 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 - (c - start) + c - 2) / (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 5084 KB Output is correct
2 Incorrect 140 ms 5064 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 36 ms 5120 KB Output is correct
2 Correct 32 ms 5092 KB Output is correct
3 Correct 44 ms 5060 KB Output is correct
4 Correct 107 ms 5108 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 5116 KB Output is correct
2 Incorrect 47 ms 5132 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 40 ms 5132 KB Output is correct
2 Correct 105 ms 5052 KB Output is correct
3 Correct 88 ms 5068 KB Output is correct
4 Correct 34 ms 5112 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5132 KB Output is correct
2 Correct 105 ms 5052 KB Output is correct
3 Correct 88 ms 5068 KB Output is correct
4 Correct 34 ms 5112 KB Output is correct
5 Correct 84 ms 5168 KB Output is correct
6 Correct 82 ms 5124 KB Output is correct
7 Correct 143 ms 5176 KB Output is correct
8 Correct 178 ms 5184 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5132 KB Output is correct
2 Correct 105 ms 5052 KB Output is correct
3 Correct 88 ms 5068 KB Output is correct
4 Correct 34 ms 5112 KB Output is correct
5 Correct 84 ms 5168 KB Output is correct
6 Correct 82 ms 5124 KB Output is correct
7 Correct 143 ms 5176 KB Output is correct
8 Correct 178 ms 5184 KB Output is correct
9 Correct 179 ms 5196 KB Output is correct
10 Correct 397 ms 5088 KB Output is correct
11 Correct 1048 ms 5172 KB Output is correct
12 Correct 779 ms 5184 KB Output is correct
13 Correct 213 ms 5144 KB Output is correct
14 Correct 34 ms 5140 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5132 KB Output is correct
2 Correct 105 ms 5052 KB Output is correct
3 Correct 88 ms 5068 KB Output is correct
4 Correct 34 ms 5112 KB Output is correct
5 Correct 84 ms 5168 KB Output is correct
6 Correct 82 ms 5124 KB Output is correct
7 Correct 143 ms 5176 KB Output is correct
8 Correct 178 ms 5184 KB Output is correct
9 Correct 179 ms 5196 KB Output is correct
10 Correct 397 ms 5088 KB Output is correct
11 Correct 1048 ms 5172 KB Output is correct
12 Correct 779 ms 5184 KB Output is correct
13 Correct 213 ms 5144 KB Output is correct
14 Correct 34 ms 5140 KB Output is correct
15 Correct 207 ms 5184 KB Output is correct
16 Correct 256 ms 5188 KB Output is correct
17 Incorrect 351 ms 5272 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 5084 KB Output is correct
2 Incorrect 140 ms 5064 KB Output isn't correct
3 Halted 0 ms 0 KB -