oj.uz

Submission #866086

# Submission time Handle Problem Language Result Execution time Memory
866086 2023-10-25T11:39:29 Z boris_mihov Chess Rush (CEOI20_chessrush) C++17
36 / 100
 2000 ms 37724 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 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);
            if (res.first == INF) res = {0, 0};
            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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16476 KB Output is correct
2 Runtime error 24 ms 37724 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14428 KB Output is correct
2 Correct 6 ms 14344 KB Output is correct
3 Correct 8 ms 14428 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16472 KB Output is correct
2 Execution timed out 2033 ms 24664 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16472 KB Output is correct
2 Execution timed out 2033 ms 24664 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 50 ms 14428 KB Output is correct
3 Correct 34 ms 14424 KB Output is correct
4 Correct 7 ms 14424 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 50 ms 14428 KB Output is correct
3 Correct 34 ms 14424 KB Output is correct
4 Correct 7 ms 14424 KB Output is correct
5 Correct 7 ms 14496 KB Output is correct
6 Correct 7 ms 14428 KB Output is correct
7 Correct 35 ms 14484 KB Output is correct
8 Correct 50 ms 14484 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 50 ms 14428 KB Output is correct
3 Correct 34 ms 14424 KB Output is correct
4 Correct 7 ms 14424 KB Output is correct
5 Correct 7 ms 14496 KB Output is correct
6 Correct 7 ms 14428 KB Output is correct
7 Correct 35 ms 14484 KB Output is correct
8 Correct 50 ms 14484 KB Output is correct
9 Correct 10 ms 14424 KB Output is correct
10 Correct 13 ms 14680 KB Output is correct
11 Correct 229 ms 14468 KB Output is correct
12 Correct 208 ms 14424 KB Output is correct
13 Correct 11 ms 14424 KB Output is correct
14 Correct 7 ms 14428 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 50 ms 14428 KB Output is correct
3 Correct 34 ms 14424 KB Output is correct
4 Correct 7 ms 14424 KB Output is correct
5 Correct 7 ms 14496 KB Output is correct
6 Correct 7 ms 14428 KB Output is correct
7 Correct 35 ms 14484 KB Output is correct
8 Correct 50 ms 14484 KB Output is correct
9 Correct 10 ms 14424 KB Output is correct
10 Correct 13 ms 14680 KB Output is correct
11 Correct 229 ms 14468 KB Output is correct
12 Correct 208 ms 14424 KB Output is correct
13 Correct 11 ms 14424 KB Output is correct
14 Correct 7 ms 14428 KB Output is correct
15 Correct 11 ms 14424 KB Output is correct
16 Correct 13 ms 14428 KB Output is correct
17 Incorrect 3 ms 4372 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16476 KB Output is correct
2 Runtime error 24 ms 37724 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -