oj.uz

Submission #553722

# Submission time Handle Problem Language Result Execution time Memory
553722 2022-04-26T17:13:45 Z Stickfish Chess Rush (CEOI20_chessrush) C++17
100 / 100
 1154 ms 60876 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};
}

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) {
    int sz = a.sz;
    matrix ans(sz);
    for (int t = 0; t < sz; ++t) {
        for (int j = 0; j < sz; ++j) {
            ans[0][j] = Add(ans[0][j], Mul(a[t][j], a[0][t]));
            if (t == sz - 1)
                ans[sz - 1][sz - j - 1] = ans[sz - j - 1][sz - 1] = ans[j][0] = ans[0][j];
        }
    }
    for (int e=1; 2*e<sz; ++e) {
        for (int s=1; s+1<sz; ++s) {
            if (s-e>=0)ans[e][s] = ans[s][e] = Add(ans[s-e][0], ans[s+1][e-1]);
            else ans[e][s] = ans[s][e] = Add(ans[0][s + e], ans[s - 1][e - 1]);
        }
    }
    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;
}

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 (j)
                ans[i][j] = Add(ans[i][j], a[i][j - 1]);
            if (j + 1 < a.sz)
                ans[i][j] = Add(ans[i][j], a[i][j + 1]);
        }
    }
    return ans;
}

matrix pw(int sz, int m) {
    matrix ans(sz);
    for (int i = 0; i < sz; ++i)
        ans[i][i] = 1;
    bool hey = false;
    for (int bt = 30; bt >= 0; --bt) {
        if (hey)
            ans = square(ans);
        if (m & (1 << bt)) {
            ans = mult_single(ans);
            hey = true;
        }
    }
    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);
        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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9428 KB Output is correct
2 Correct 387 ms 43628 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9428 KB Output is correct
2 Correct 18 ms 11572 KB Output is correct
3 Correct 11 ms 9300 KB Output is correct
4 Correct 66 ms 21824 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9288 KB Output is correct
2 Correct 12 ms 9428 KB Output is correct
3 Correct 9 ms 9428 KB Output is correct
4 Correct 9 ms 9556 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9288 KB Output is correct
2 Correct 12 ms 9428 KB Output is correct
3 Correct 9 ms 9428 KB Output is correct
4 Correct 9 ms 9556 KB Output is correct
5 Correct 359 ms 52860 KB Output is correct
6 Correct 181 ms 33224 KB Output is correct
7 Correct 15 ms 12072 KB Output is correct
8 Correct 925 ms 60808 KB Output is correct
9 Correct 14 ms 11312 KB Output is correct
10 Correct 35 ms 13964 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9976 KB Output is correct
2 Correct 17 ms 11604 KB Output is correct
3 Correct 15 ms 11348 KB Output is correct
4 Correct 11 ms 9420 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9976 KB Output is correct
2 Correct 17 ms 11604 KB Output is correct
3 Correct 15 ms 11348 KB Output is correct
4 Correct 11 ms 9420 KB Output is correct
5 Correct 11 ms 9916 KB Output is correct
6 Correct 14 ms 9900 KB Output is correct
7 Correct 16 ms 11472 KB Output is correct
8 Correct 15 ms 11692 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9976 KB Output is correct
2 Correct 17 ms 11604 KB Output is correct
3 Correct 15 ms 11348 KB Output is correct
4 Correct 11 ms 9420 KB Output is correct
5 Correct 11 ms 9916 KB Output is correct
6 Correct 14 ms 9900 KB Output is correct
7 Correct 16 ms 11472 KB Output is correct
8 Correct 15 ms 11692 KB Output is correct
9 Correct 15 ms 12072 KB Output is correct
10 Correct 15 ms 12200 KB Output is correct
11 Correct 31 ms 14532 KB Output is correct
12 Correct 29 ms 14540 KB Output is correct
13 Correct 17 ms 12116 KB Output is correct
14 Correct 15 ms 11220 KB Output is correct

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9976 KB Output is correct
2 Correct 17 ms 11604 KB Output is correct
3 Correct 15 ms 11348 KB Output is correct
4 Correct 11 ms 9420 KB Output is correct
5 Correct 11 ms 9916 KB Output is correct
6 Correct 14 ms 9900 KB Output is correct
7 Correct 16 ms 11472 KB Output is correct
8 Correct 15 ms 11692 KB Output is correct
9 Correct 15 ms 12072 KB Output is correct
10 Correct 15 ms 12200 KB Output is correct
11 Correct 31 ms 14532 KB Output is correct
12 Correct 29 ms 14540 KB Output is correct
13 Correct 17 ms 12116 KB Output is correct
14 Correct 15 ms 11220 KB Output is correct
15 Correct 20 ms 12132 KB Output is correct
16 Correct 17 ms 12116 KB Output is correct
17 Correct 905 ms 60864 KB Output is correct
18 Correct 1087 ms 57032 KB Output is correct
19 Correct 811 ms 54928 KB Output is correct
20 Correct 826 ms 57024 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9428 KB Output is correct
2 Correct 387 ms 43628 KB Output is correct
3 Correct 13 ms 9428 KB Output is correct
4 Correct 18 ms 11572 KB Output is correct
5 Correct 11 ms 9300 KB Output is correct
6 Correct 66 ms 21824 KB Output is correct
7 Correct 10 ms 9288 KB Output is correct
8 Correct 12 ms 9428 KB Output is correct
9 Correct 9 ms 9428 KB Output is correct
10 Correct 9 ms 9556 KB Output is correct
11 Correct 359 ms 52860 KB Output is correct
12 Correct 181 ms 33224 KB Output is correct
13 Correct 15 ms 12072 KB Output is correct
14 Correct 925 ms 60808 KB Output is correct
15 Correct 14 ms 11312 KB Output is correct
16 Correct 35 ms 13964 KB Output is correct
17 Correct 12 ms 9976 KB Output is correct
18 Correct 17 ms 11604 KB Output is correct
19 Correct 15 ms 11348 KB Output is correct
20 Correct 11 ms 9420 KB Output is correct
21 Correct 11 ms 9916 KB Output is correct
22 Correct 14 ms 9900 KB Output is correct
23 Correct 16 ms 11472 KB Output is correct
24 Correct 15 ms 11692 KB Output is correct
25 Correct 15 ms 12072 KB Output is correct
26 Correct 15 ms 12200 KB Output is correct
27 Correct 31 ms 14532 KB Output is correct
28 Correct 29 ms 14540 KB Output is correct
29 Correct 17 ms 12116 KB Output is correct
30 Correct 15 ms 11220 KB Output is correct
31 Correct 20 ms 12132 KB Output is correct
32 Correct 17 ms 12116 KB Output is correct
33 Correct 905 ms 60864 KB Output is correct
34 Correct 1087 ms 57032 KB Output is correct
35 Correct 811 ms 54928 KB Output is correct
36 Correct 826 ms 57024 KB Output is correct
37 Correct 937 ms 60876 KB Output is correct
38 Correct 1154 ms 57068 KB Output is correct
39 Correct 1041 ms 57068 KB Output is correct
40 Correct 14 ms 9480 KB Output is correct
41 Correct 921 ms 56988 KB Output is correct
42 Correct 12 ms 9556 KB Output is correct