oj.uz

답안 #866064

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
866064 2023-10-25T11:12:41 Z boris_mihov Chess Rush (CEOI20_chessrush) C++17
8 / 100
 143 ms 262144 KB 
#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 x, Line y)
{
    if (x.a == y.a) return 0;
    if (((y.b - x.b) % (x.a - y.a)) != 0) return 0;
    int x1 = (y.b - x.b) / (x.a - y.a);
    int y1 = x.a * x1 + x.b;
    if (1 <= x1 && x1 <= r && 1 <= y1 && y1 <= c) return 1;
    return 0;
}

bool intersectSpecial(Line b)
{
    return (b.a + b.b >= 1 && b.a + 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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 143 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 143 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 143 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 143 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -