oj.uz

Submission #552822

# Submission time Handle Problem Language Result Execution time Memory
552822 2022-04-24T06:18:51 Z Stickfish Chess Rush (CEOI20_chessrush) C++17
36 / 100
 2000 ms 4180 KB 
#include <iostream>
#include "arithmetics.h"
#include <vector>
#include <cassert>
using namespace std;
using ll = long long;

pair<int, int> pawn(int r, int c, int j0, int j1) {
    if (j0 == j1)
        return {r - 1, 1};
    else
        return {0, 0};
}

pair<int, int> rook(int r, int c, int j0, int j1) {
    if (j0 == j1)
        return {1, 1};
    else
        return {2, 2};
}

struct point {
    ll x, y;

    point(){}

    point(ll x_, ll y_): x(x_), y(y_) {}

    point operator/(ll t) const {
        return {x / t, y / t};
    }

    point operator*(ll t) const {
        return {x * t, y * t};
    }

    bool operator==(point pt) const {
        return x == pt.x && y == pt.y;
    }

    bool operator!=(point pt) const {
        return x != pt.x || y != pt.y;
    }

    ll operator*(point pt) const {
        return x * pt.y - y * pt.x;
    }

    ll operator^(point pt) const {
        return x * pt.x + y * pt.y;
    }

    point operator+(point pt) const {
        return {x + pt.x, y + pt.y};
    }

    point operator-(point pt) const {
        return {x - pt.x, y - pt.y};
    }

    point rotate_45_normal() {
        point ans(x - y, x + y);
        if (abs(x + y) == 2 || abs(x - y) == 2)
            return ans / 2;
        else
            return ans;
    }

    point rotate_90() {
        return {-y, x};
    }

};

pair<int, int> queen(int r, int c, int j0, int j1) {
    for (point dir(1, 0); dir != point(-1, 0); dir = dir.rotate_45_normal()) {
        //cout << "! " << dir.x << ' ' << dir.y << endl;
        if (dir * point(j1 - j0, r - 1) == 0)
            return {1, 1};
    }
    int cnt = 2;
    for (point dir(1, 1); dir != point(-1, -1); dir = dir.rotate_90()) {
        // (j0, 0) + dir * k = (j1, y0)
        ll y0 = (j1 - j0) / dir.x * dir.y;
        if (0 <= y0 && y0 < r)
            cnt += 2;
        // (j0, 0) + dir * k = (x1, r - 1)
        ll x1 = j0 + (r - 1) / dir.y * dir.x;
        if (0 <= x1 && x1 < c)
            ++cnt;
        // (x2, 0) + dir * k = (j1, r - 1)
        ll x2 = j1 - (r - 1) / dir.y * dir.x;
        if (0 <= x2 && x2 < c)
            ++cnt;
    }
    if ((j0 + j1 + r) % 2) {
        int jright = 2 * c - j1 - 1;
        if (point(jright - j0, r - 1) * point(1, 1) >= 0)
            ++cnt;
        int jleft = -j1 - 1;
        if (point(-1, 1) * point(jleft - j0, r - 1) >= 0)
            ++cnt;
    }
    return {2, cnt};
}

int choose(int n, int k) {
    if (k * 2 > n)
        return choose(n, n - k);
    int ans = 1;
    for (int p = n; p > n - k; --p) {
        ans = Mul(ans, p);
    }
    int fct = 1;
    for (int p = 1; p <= k; ++p) {
        fct = Mul(fct, p);
    }
    return Div(ans, fct);
}

pair<int, int> bishop_goleft(int r, int c, int j0, int j1) {
    if (j0 == 0 && j1 == c - 1 && r == c)
        return {1, 1};
    if (j0 == c - 1 && j1 == 0 && r == c)
        return {1, 1};
    int loopcnt = min(0, r / c / 2 - 3);
    point pt(0, j0 + loopcnt * (c - 1) * 2);
    int minmoves = 1 + loopcnt * 2;
    int rmv = 0;
    int lst = 0;
    while (true) {
        if ((point(j1, r - 1) - pt) * point(1, 1) >= 0) {
            ++minmoves;
            lst = r - 1 - pt.y;
            pt = pt + point(lst, lst);
            rmv = abs(j1 - pt.x) / 2;
            break;
        }
        minmoves += 2;
        pt = pt + point(c - 1, c - 1);
        if (point(-1, 1) * (point(j1, r - 1) - pt) >= 0) {
            lst = r - 1 - pt.y;
            pt = pt + point(-lst, lst);
            rmv = abs(j1 - pt.x) / 2;
            break;
        }
        pt = pt + point(1 - c, c - 1);
    }
    lst = c - 1 - lst;
    int cnt = 0;
    if (minmoves == 2)
        return {2, 1};
    for (int rm0 = 0; rm0 <= j0 && rm0 <= rmv; ++rm0) {
        int Cvl = 0;
        for (int rml = 0; rml <= lst && rm0 + rml <= rmv; ++rml) {
            //cout << "! " << ' ' << rmv << ' ' << rm0 << ' ' << rml << " : " << rmv - rm0 - rml << ' ' << minmoves - 2 << endl;
            if (rmv - rm0 - rml == 0) {
                ++cnt;
                continue;
            }
            if (minmoves == 3)
                continue;
            cnt = Add(cnt, choose(rmv - rm0 - rml + minmoves - 4, minmoves - 4));
        }
    }
    //cout << "---" << ' ' << minmoves << endl;
    return {minmoves, cnt};
}

pair<int, int> bishop(int r, int c, int j0, int j1) {
    if ((r + j0 + j1) % 2 == 0)
        return {0, 0};
    pair<int, int> ansup = bishop_goleft(r, c, j0, j1);
    pair<int, int> ansdown = bishop_goleft(r, c, c - j0 - 1, c - j1 - 1);
    if (ansup.first == ansdown.first)
        return {ansup.first, Add(ansup.second, ansdown.second)};
    return min(ansup, ansdown);
}

struct matrix {
    matrix(int sz_): sz(sz_), f(sz_, vector<int>(sz_, 0)) {}

    vector<int>& operator[](int i) {
        return f[i];
    }
    
    matrix operator*(matrix m) {
        matrix ans(sz);
        for (int i = 0; i < sz; ++i) {
            for (int j = 0; j < sz; ++j) {
                for (int t = 0; t < sz; ++t) {
                    ans[i][j] = Add(ans[i][j], Mul(m[t][j], f[i][t]));
                }
            }
        }
        return ans;
    }

    int sz;
    vector<vector<int>> f;
};

matrix pw(matrix a, int m) {
    if (m == 1)
        return a;
    if (m % 2)
        return a * pw(a, m - 1);
    return pw(a * a, m / 2);
}

signed main() {
    int r, c, q;
    cin >> r >> c >> q;
    matrix king_ans(c);
    for (int i = 0; i < c; ++i) {
        king_ans[i][i] = 1;
        if (i)
            king_ans[i][i - 1] = 1;
        if (i + 1 < c)
            king_ans[i][i + 1] = 1;
    }
    if (c <= 100)
        king_ans = pw(king_ans, r - 1);
    while (q--) {
        char t;
        int j0, j1;
        cin >> t >> j0 >> j1;
        --j0, --j1;
        pair<int, int> ans;
        if (t == 'P') {
            ans = pawn(r, c, j0, j1);
        } else if (t == 'Q') {
            ans = queen(r, c, j0, j1);
        } else if (t == 'R') {
            ans = rook(r, c, j0, j1);
        } else if (t == 'K') {
            ans = {r - 1, king_ans[j0][j1]};
        } else if (t == 'B') {
            ans = bishop(r, c, j0, j1);
        }
        cout << ans.first << ' ' << ans.second << '\n';
    }
}

Compilation message

chessrush.cpp: In function 'std::pair<int, int> bishop_goleft(int, int, int, int)':
chessrush.cpp:154:13: warning: unused variable 'Cvl' [-Wunused-variable]
  154 |         int Cvl = 0;
      |             ^~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 2076 ms 2744 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 852 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 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 5 ms 340 KB Output is correct
2 Correct 126 ms 1020 KB Output is correct
3 Correct 80 ms 828 KB Output is correct
4 Correct 1 ms 212 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 126 ms 1020 KB Output is correct
3 Correct 80 ms 828 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 6 ms 340 KB Output is correct
6 Correct 5 ms 300 KB Output is correct
7 Correct 80 ms 844 KB Output is correct
8 Correct 126 ms 932 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 126 ms 1020 KB Output is correct
3 Correct 80 ms 828 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 6 ms 340 KB Output is correct
6 Correct 5 ms 300 KB Output is correct
7 Correct 80 ms 844 KB Output is correct
8 Correct 126 ms 932 KB Output is correct
9 Correct 16 ms 596 KB Output is correct
10 Correct 26 ms 864 KB Output is correct
11 Correct 731 ms 3928 KB Output is correct
12 Correct 662 ms 3700 KB Output is correct
13 Correct 18 ms 596 KB Output is correct
14 Correct 1 ms 212 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 126 ms 1020 KB Output is correct
3 Correct 80 ms 828 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 6 ms 340 KB Output is correct
6 Correct 5 ms 300 KB Output is correct
7 Correct 80 ms 844 KB Output is correct
8 Correct 126 ms 932 KB Output is correct
9 Correct 16 ms 596 KB Output is correct
10 Correct 26 ms 864 KB Output is correct
11 Correct 731 ms 3928 KB Output is correct
12 Correct 662 ms 3700 KB Output is correct
13 Correct 18 ms 596 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 19 ms 680 KB Output is correct
16 Correct 22 ms 584 KB Output is correct
17 Incorrect 4 ms 4180 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 2076 ms 2744 KB Time limit exceeded
3 Halted 0 ms 0 KB -