Submission #866046

#	Time	Username	Problem	Language	Result	Execution time	Memory
866046		boris_mihov	Chess Rush (CEOI20_chessrush)	C++17	0 / 100	140 ms	262144 KiB

chessrush

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <stack>

typedef long long llong;
const int MAXN = 1000 + 10;
const int MOD = 1e9 + 7;
const int INF = 2e9;

int r, c, q;
llong power(int num, int base)
{
    if (base == 0)
    {
        return 1;
    }

    if (base & 1)
    {
        return (num * power(num, base - 1)) % MOD;
    }

    llong res = power(num, base - 1);
    return (res * res) % MOD;
}

void solve()
{  
    for (int i = 1 ; i <= q ; ++i)
    {
        char qType;
        int colB, colE;
        std::cin >> qType >> colB >> colE;
        if (qType == 'P')
        {
            if (colB != colE) std::cout << 0 << ' ' << 0 << '\n';
            else std::cout << 1 << ' ' << 1 << '\n';
            continue;
        }

        if (qType == 'R')
        {
            if (colB == colE) std::cout << 1 << ' ' << 1 << '\n';
            else std::cout << 2 << ' ' << 2 << '\n';
            continue;
        }

        if (qType == 'B')
        {
            if (((1 + colB) % 2) != (r + colE) % 2)
            {
                std::cout << 0 << ' ' << 0 << '\n';
                continue;
            }

            int minus = (colB - colE + r - 1) / 2;
            int plus = minus - (colB - colE);
            int stepsPlus = ((minus) / (c - 1) + ((minus) % (c - 1) > 0) + (plus - (c - colB)) / (c - 1) + (((plus - (c - colB)) % (c - 1)) > 0)) + (plus > 0 && c != colB);
            int stepsMinus = ((plus) / (c - 1) + ((plus) % (c - 1) > 0) + (minus - (colB - 1)) / (c - 1) + (((minus - (colB - 1)) % (c - 1)) > 0)) + (minus > 0 && 1 != colB);
            if (stepsPlus == stepsMinus)
            {
                std::cout << stepsPlus << ' ' << 2 << '\n';
            } else
            {
                std::cout << std::min(stepsPlus, stepsMinus) << ' ' << 1 << '\n';
            }

            continue;
        }

        if (qType == 'Q')
        {
            if (colB == colE || (1 + colB) == (r - 1 + colE) || (1 - colB) == (r - 1 - colE))
            {
                std::cout << 1 << ' ' << 1 << '\n';
                continue;
            }

            int ways = 4;
            if (colE >= r) ways++;
            if (colE + r - 1 <= c) ways++;
            if (r - colB <= colE) ways++;
            if (c - (r - (c - colB)) + 1 >= colE) ways++;
            std::cout << 2 << ' ' << ways << '\n';
            continue;
        }

        if (qType == 'K')
        {
            int diffC = abs(colB - colE);
            int diffR = abs(r - 1);
            int sum = std::max(diffC, diffR);

            diffC = std::min(diffC, diffR);
            llong ways = 1;

            for (int i = sum ; i >= sum - diffC + 1 ; --i)
            {
                ways = (ways * i) % MOD;
                ways = (ways * power(i - (sum - diffC), MOD - 2)) % MOD;
            }

            std::cout << sum << ' ' << ways << '\n';
        }
    }
}   

void input()
{
    std::cin >> r >> c >> q;
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 8
• Subtask 3: 0 / 15
• Subtask 4: 0 / 22
• Subtask 5: 0 / 5
• Subtask 6: 0 / 8
• Subtask 7: 0 / 15
• Subtask 8: 0 / 20
• Subtask 9: 0 / 7