oj.uz

Submission #866085

# Submission time Handle Problem Language Result Execution time Memory
866085 2023-10-25T11:38:37 Z boris_mihov Chess Rush (CEOI20_chessrush) C++17
36 / 100
 234 ms 37832 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);
            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 6 ms 16476 KB Output is correct
2 Runtime error 19 ms 37832 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 6 ms 14428 KB Output is correct
2 Correct 7 ms 14436 KB Output is correct
3 Correct 6 ms 14428 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 16476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 16476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

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

Subtask #6
8.0 / 8.0

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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14424 KB Output is correct
2 Correct 50 ms 14428 KB Output is correct
3 Correct 35 ms 14428 KB Output is correct
4 Correct 8 ms 14428 KB Output is correct
5 Correct 7 ms 14428 KB Output is correct
6 Correct 7 ms 14428 KB Output is correct
7 Correct 37 ms 14484 KB Output is correct
8 Correct 52 ms 14428 KB Output is correct
9 Correct 9 ms 14428 KB Output is correct
10 Correct 14 ms 14428 KB Output is correct
11 Correct 234 ms 14464 KB Output is correct
12 Correct 206 ms 14476 KB Output is correct
13 Correct 11 ms 14500 KB Output is correct
14 Correct 7 ms 14484 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14424 KB Output is correct
2 Correct 50 ms 14428 KB Output is correct
3 Correct 35 ms 14428 KB Output is correct
4 Correct 8 ms 14428 KB Output is correct
5 Correct 7 ms 14428 KB Output is correct
6 Correct 7 ms 14428 KB Output is correct
7 Correct 37 ms 14484 KB Output is correct
8 Correct 52 ms 14428 KB Output is correct
9 Correct 9 ms 14428 KB Output is correct
10 Correct 14 ms 14428 KB Output is correct
11 Correct 234 ms 14464 KB Output is correct
12 Correct 206 ms 14476 KB Output is correct
13 Correct 11 ms 14500 KB Output is correct
14 Correct 7 ms 14484 KB Output is correct
15 Correct 11 ms 14428 KB Output is correct
16 Correct 11 ms 14428 KB Output is correct
17 Incorrect 2 ms 4444 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

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