oj.uz

Submission #814675

# Submission time Handle Problem Language Result Execution time Memory
814675 2023-08-08T08:56:07 Z finn__ Chess Rush (CEOI20_chessrush) C++17
51 / 100
 1362 ms 24612 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;
    }
};

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 matrix for bishop

    for (size_t i = 0; i < 2 * N; ++i)
        for (size_t j = 0; j < 2 * N; ++j)
        {
            bpow[1].m[i][j][0] = INF;
            bpow[1].m[i][j][1] = 0;
        }

    for (size_t i = 0; i < c; ++i)
    {
        // d = 0
        if (i + 1 < c)
        {
            bpow[1].m[i][i + 1][0] = 0;
            bpow[1].m[i][i + 1][1] = 1;
            bpow[1].m[i][i + 1 + N][0] = 1;
            bpow[1].m[i][i + 1 + N][1] = 1;
        }
        // d = 1
        if (i)
        {
            bpow[1].m[i + N][i - 1][0] = 1;
            bpow[1].m[i + N][i - 1][1] = 1;
            bpow[1].m[i + N][i - 1 + N][0] = 0;
            bpow[1].m[i + N][i - 1 + N][1] = 1;
        }
    }

    for (size_t i = 2; i < 31; ++i)
        bpow[i] = bpow[i - 1] * bpow[i - 1];

    // 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':
        {
            array<int64_t[2], 2 * N> state;
            for (size_t i = 0; i < 2 * N; ++i)
                state[i][0] = INF, state[i][1] = 0;
            state[start - 1][0] = 1;
            state[start - 1][1] = 1;
            state[start - 1 + N][0] = 1;
            state[start - 1 + N][1] = 1;

            size_t k = r - 1, i = 1;
            while (k)
            {
                if (k & 1)
                    state = bpow[i] * state;
                ++i;
                k >>= 1;
            }

            int64_t num_turns = min(state[finish - 1][0], state[finish - 1 + N][0]),
                    num_ways = 0;
            if (state[finish - 1][0] == num_turns)
                num_ways += state[finish - 1][1];
            if (state[finish - 1 + N][0] == num_turns)
                num_ways += state[finish - 1 + N][1];

            if (num_turns == INF)
                cout << "0 0\n";
            else
                cout << num_turns << ' ' << num_ways << '\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;
        }
        }
    }
}

Compilation message

chessrush.cpp: In function 'int main()':
chessrush.cpp:71:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |     for (size_t i = 0; i < c; ++i)
      |                        ~~^~~
chessrush.cpp:74:19: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |         if (i + 1 < c)
      |             ~~~~~~^~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 24368 KB Output is correct
2 Incorrect 838 ms 24436 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 283 ms 24396 KB Output is correct
2 Correct 275 ms 24396 KB Output is correct
3 Correct 281 ms 24360 KB Output is correct
4 Correct 648 ms 24432 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 24336 KB Output is correct
2 Correct 292 ms 24300 KB Output is correct
3 Correct 276 ms 24312 KB Output is correct
4 Correct 323 ms 24400 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 24336 KB Output is correct
2 Correct 292 ms 24300 KB Output is correct
3 Correct 276 ms 24312 KB Output is correct
4 Correct 323 ms 24400 KB Output is correct
5 Incorrect 1087 ms 24424 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 24456 KB Output is correct
2 Correct 443 ms 24368 KB Output is correct
3 Correct 396 ms 24348 KB Output is correct
4 Correct 268 ms 24304 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 24456 KB Output is correct
2 Correct 443 ms 24368 KB Output is correct
3 Correct 396 ms 24348 KB Output is correct
4 Correct 268 ms 24304 KB Output is correct
5 Correct 375 ms 24352 KB Output is correct
6 Correct 331 ms 24352 KB Output is correct
7 Correct 457 ms 24436 KB Output is correct
8 Correct 506 ms 24444 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 24456 KB Output is correct
2 Correct 443 ms 24368 KB Output is correct
3 Correct 396 ms 24348 KB Output is correct
4 Correct 268 ms 24304 KB Output is correct
5 Correct 375 ms 24352 KB Output is correct
6 Correct 331 ms 24352 KB Output is correct
7 Correct 457 ms 24436 KB Output is correct
8 Correct 506 ms 24444 KB Output is correct
9 Correct 434 ms 24424 KB Output is correct
10 Correct 703 ms 24444 KB Output is correct
11 Correct 1362 ms 24572 KB Output is correct
12 Correct 1091 ms 24612 KB Output is correct
13 Correct 498 ms 24456 KB Output is correct
14 Correct 277 ms 24336 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 24456 KB Output is correct
2 Correct 443 ms 24368 KB Output is correct
3 Correct 396 ms 24348 KB Output is correct
4 Correct 268 ms 24304 KB Output is correct
5 Correct 375 ms 24352 KB Output is correct
6 Correct 331 ms 24352 KB Output is correct
7 Correct 457 ms 24436 KB Output is correct
8 Correct 506 ms 24444 KB Output is correct
9 Correct 434 ms 24424 KB Output is correct
10 Correct 703 ms 24444 KB Output is correct
11 Correct 1362 ms 24572 KB Output is correct
12 Correct 1091 ms 24612 KB Output is correct
13 Correct 498 ms 24456 KB Output is correct
14 Correct 277 ms 24336 KB Output is correct
15 Correct 517 ms 24444 KB Output is correct
16 Correct 516 ms 24344 KB Output is correct
17 Incorrect 970 ms 24520 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 24368 KB Output is correct
2 Incorrect 838 ms 24436 KB Output isn't correct
3 Halted 0 ms 0 KB -