Submission #866062

#	Time	Username	Problem	Language	Result	Execution time	Memory
866062		boris_mihov	Chess Rush (CEOI20_chessrush)	C++17	0 / 100	167 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;
}

struct Line
{
    llong a, b;
    bool lie(int x, int y)
    {
        return (a * x + b == y);
    }
};

bool intersect(Line a, Line b)
{
    if (a.a == b.a) return 0;
    if (((b.b - a.b) % (a.a - b.a)) != 0) return 0;
    int x = (b.b - a.b) / (a.a - b.a);
    int y = a.a * x + a.b;
    if (1 <= x && x <= r && 1 <= y && y <= c) return 1;
    return 0;
}

bool intersectSpecial(Line b)
{
    return (b.b >= 1 && b.b <= c);   
}

bool intersectSpecial2(Line b)
{
    return (b.a * r + b.b >= 1 && b.a * r + b.b <= c);   
}

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 << r - 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')
        {
            Line hB = {0, colB};
            Line upB = {1, colB - 1};
            Line downB = {-1, colB + 1};

            if (hB.lie(r, colE) || upB.lie(r, colE) || downB.lie(r, colE))
            {
                std::cout << 1 << ' ' << 1 << '\n';
                continue;
            }

            Line hE = {0, colE};
            Line upE = {1, colE - r};
            Line downE = {-1, colE + r};
            std::vector <Line> begin, end;

            begin.push_back(hB);
            begin.push_back(upB);
            begin.push_back(downB);

            end.push_back(hE);
            end.push_back(upE);
            end.push_back(downE);

            int ways = 0;
            for (const Line &beg : begin)
            {
                for (const Line &en : end)
                {
                    ways += intersect(beg, en);
                }
            }

            for (const Line &en : end)
            {
                ways += intersectSpecial(en);
            }

            for (const Line &beg : begin)
            {
                ways += intersectSpecial2(beg);
            }


            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