Submission #866085

#	Time	Username	Problem	Language	Result	Execution time	Memory
866085		boris_mihov	Chess Rush (CEOI20_chessrush)	C++17	36 / 100	234 ms	37832 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 MAXM = 100 + 10;
const int MOD = 1e9 + 7;
const int INF = 2e9;
 
int r, c, q;
int buff[MAXN][MAXN];
struct Matrix
{
    int m[MAXN][MAXN];
    Matrix()
    {
        for (int i = 1 ; i <= c ; ++i)
        {
            for (int j = 1 ; j <= c ; ++j)
            {
                m[i][j] = 0;
            }
        }
    }
 
    Matrix(int par)
    {
        for (int i = 1 ; i <= c ; ++i)
        {
            for (int j = 1 ; j <= c ; ++j)
            {
                m[i][j] = (i == j);
            }
        }
    }
 
    friend Matrix operator * (Matrix &a, Matrix &b)
    {
        Matrix res;
        for (int i = 1 ; i <= c ; ++i)
        {
            for (int j = 1 ; j <= c ; ++j)
            {
                for (int k = 1 ; k <= c ; ++k)
                {
                    res.m[i][j] = (res.m[i][j] + 1LL * a.m[i][k] * b.m[k][j]) % MOD;
                }
            }
        }
 
        return res;
    }    
 
    friend void operator *= (Matrix &a, Matrix &b)
    {
        for (int i = 1 ; i <= c ; ++i)
        {
            for (int j = 1 ; j <= c ; ++j)
            {
                buff[i][j] = 0;
            }
        }
 
        for (int i = 1 ; i <= c ; ++i)
        {
            for (int j = 1 ; j <= c ; ++j)
            {
                for (int k = 1 ; k <= c ; ++k)
                {
                    buff[i][j] = (buff[i][j] + 1LL * a.m[i][k] * b.m[k][j]) % MOD;
                }
            }
        }
 
        for (int i = 1 ; i <= c ; ++i)
        {
            for (int j = 1 ; j <= c ; ++j)
            {
                a.m[i][j] = buff[i][j];
            }
        }
    }           
};
 
void powerMatrix(Matrix &king)
{
    Matrix begin(1);
    Matrix trans;
 
    for (int i = 1 ; i <= c ; ++i)
    {
        for (int j = std::max(1, i - 1) ; j <= std::min(c, i + 1) ; ++j)
        {
            trans.m[i][j] = 1;
        }
    }
 
    for (int log = 0 ; (1 << log) < r ; ++log)
    {
        if ((r - 1) & (1 << log))
        {
            begin *= trans;
        }
 
        trans *= trans;
    }
 
    for (int i = 1 ; i <= c ; ++i)
    {
        for (int j = 1 ; j <= c ; ++j)
        {
            king.m[i][j] = begin.m[i][j];
        }
    }
}
 
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);   
}

std::pair <int,int> dp[MAXM][MAXM][MAXM];
bool bl[MAXM][MAXM][MAXM];

std::pair <int,int> f(int row, int col, int wanted)
{
    if (row == r)
    {
        if (wanted == col) return {0, 1};
        return {INF, 0};
    }

    if (bl[row][col][wanted])
    {
        return dp[row][col][wanted];
    }

    dp[row][col][wanted] = {INF, 0};
    for (int deltaPlus = 1 ; row + deltaPlus <= r && col + deltaPlus <= c ; ++deltaPlus)
    {
        auto [dist, ways] = f(row + deltaPlus, col + deltaPlus, wanted); dist++;
        if (dist < dp[row][col][wanted].first) dp[row][col][wanted] = {dist, 0};
        if (dist == dp[row][col][wanted].first) dp[row][col][wanted].second = (dp[row][col][wanted].second + ways) % MOD;
    }

    for (int deltaMinus = 1 ; row + deltaMinus <= r && col - deltaMinus >= 1 ; ++deltaMinus)
    {
        auto [dist, ways] = f(row + deltaMinus, col - deltaMinus, wanted); dist++;
        if (dist < dp[row][col][wanted].first) dp[row][col][wanted] = {dist, 0};
        if (dist == dp[row][col][wanted].first) dp[row][col][wanted].second = (dp[row][col][wanted].second + ways) % MOD;
    }

    return dp[row][col][wanted];
}

 
void solve()
{  
    Matrix king;
    if (c <= 100) powerMatrix(king);
    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')
        {
            std::pair <int,int> res = f(1, colB, colE);
            std::cout << res.first << ' ' << res.second << '\n';
            continue;
            
            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')
        {
            std::cout << r - 1 << ' ' << king.m[colB][colE] << '\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: 8 / 8
• Subtask 3: 0 / 15
• Subtask 4: 0 / 22
• Subtask 5: 5 / 5
• Subtask 6: 8 / 8
• Subtask 7: 15 / 15
• Subtask 8: 0 / 20
• Subtask 9: 0 / 7