Submission #553685

#	Time	Username	Problem	Language	Result	Execution time	Memory
553685		Stickfish	Chess Rush (CEOI20_chessrush)	C++17	73 / 100	187 ms	49012 KiB

chessrush

#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};
}

const int MAXC = 1524;
int choose[MAXC * 2][MAXC * 2];
int balls_borders[MAXC][MAXC];
int choose_n0;

pair<int, int> bishop_goleft(int r, int c, int j0, int j1) {
    if (j0 == c - 1 && j1 == 0 && r == c)
        return {1, 1};
    int loopcnt = max(0, r / (c - 1) / 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;
        if (minmoves == 3) {
            if (lst + rm0 >= rmv)
                ++cnt;
            continue;
        }
        cnt = Add(cnt, balls_borders[minmoves - 4 - choose_n0][rmv - rm0]);
        if (lst + rm0 < rmv) {
            cnt = Sub(cnt, balls_borders[minmoves - 4 - choose_n0][rmv - rm0 - lst - 1]);
        }
    }
    //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 * 2 - 1 < sz; ++i) {
            for (int t = 0; t < sz; ++t) {
                if (f[i][t] == 0)
                    continue;
                for (int j = 0; j < sz; ++j) {
                    ans[i][j] = Add(ans[i][j], Mul(m[t][j], f[i][t]));
                }
            }
        }
        for (int i = 0; i * 2 - 1 < sz; ++i) {
            for (int j = 0; j < sz; ++j) {
                ans[sz - i - 1][sz - j - 1] = ans[i][j];
            }
        }
        return ans;
    }

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

matrix square(matrix a) {
    return a * a;
}

matrix mult_single(matrix a) {
    matrix ans(a.sz);
    for (int i = 0; i < a.sz; ++i) {
        for (int j = 0; j < a.sz; ++j) {
            ans[i][j] = a[i][j];
            if (i)
                ans[i][j] = Add(ans[i][j], a[i - 1][j]);
            if (i + 1 < a.sz)
                ans[i][j] = Add(ans[i][j], a[i + 1][j]);
        }
    }
    return ans;
}

matrix pw(int sz, int m) {
    matrix ans(sz);
    for (int i = 0; i < sz; ++i)
        ans[i][i] = 1;
    for (int bt = 30; bt >= 0; --bt) {
        ans = square(ans);
        if (m & (1 << bt))
            ans = mult_single(ans);
    }
    return ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int r, c, q;
    cin >> r >> c >> q;
    matrix king_ans(c);
    if (c <= 100)
        king_ans = pw(c, r - 1);

    choose_n0 = max(0, r / (c - 1) - c - 100);
    for (int nadd = 0; nadd <= c * 2 + 1000; ++nadd) {
        int n = choose_n0 + nadd;
        choose[nadd][0] = 1;
        for (int k = 1; k <= c * 2 + 1000 && k <= n; ++k) {
            if (nadd == 0)
                choose[nadd][k] = Div(Mul(choose[nadd][k - 1], n - k + 1), k);
            else
                choose[nadd][k] = Add(choose[nadd - 1][k], choose[nadd - 1][k - 1]);
        }
    }
    for (int t = 0; t < c + 500; ++t) {
        for (int p = 0; p < c + 500; ++p) {
            balls_borders[t][p] = choose[p + t][p];
            if (p)
                balls_borders[t][p] = Add(balls_borders[t][p], balls_borders[t][p - 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 (stderr)

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

• Subtask 1: 0 / 0
• Subtask 2: 8 / 8
• Subtask 3: 15 / 15
• Subtask 4: 22 / 22
• Subtask 5: 5 / 5
• Subtask 6: 8 / 8
• Subtask 7: 15 / 15
• Subtask 8: 0 / 20
• Subtask 9: 0 / 7