oj.uz

Submission #553721

# Submission time Handle Problem Language Result Execution time Memory
553721 2022-04-26T17:13:18 Z Stickfish Chess Rush (CEOI20_chessrush) C++17
73 / 100
 107 ms 49132 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);
    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

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 11 ms 9428 KB Output is correct
2 Incorrect 74 ms 36028 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9428 KB Output is correct
2 Correct 15 ms 11620 KB Output is correct
3 Correct 11 ms 9300 KB Output is correct
4 Correct 30 ms 20008 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9280 KB Output is correct
2 Correct 11 ms 9500 KB Output is correct
3 Correct 11 ms 9428 KB Output is correct
4 Correct 14 ms 9536 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9280 KB Output is correct
2 Correct 11 ms 9500 KB Output is correct
3 Correct 11 ms 9428 KB Output is correct
4 Correct 14 ms 9536 KB Output is correct
5 Correct 77 ms 40908 KB Output is correct
6 Correct 47 ms 30260 KB Output is correct
7 Correct 15 ms 12132 KB Output is correct
8 Correct 107 ms 49132 KB Output is correct
9 Correct 14 ms 11348 KB Output is correct
10 Correct 24 ms 14036 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9940 KB Output is correct
2 Correct 16 ms 11596 KB Output is correct
3 Correct 16 ms 11464 KB Output is correct
4 Correct 13 ms 9428 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9940 KB Output is correct
2 Correct 16 ms 11596 KB Output is correct
3 Correct 16 ms 11464 KB Output is correct
4 Correct 13 ms 9428 KB Output is correct
5 Correct 13 ms 9932 KB Output is correct
6 Correct 13 ms 9940 KB Output is correct
7 Correct 14 ms 11476 KB Output is correct
8 Correct 17 ms 11720 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9940 KB Output is correct
2 Correct 16 ms 11596 KB Output is correct
3 Correct 16 ms 11464 KB Output is correct
4 Correct 13 ms 9428 KB Output is correct
5 Correct 13 ms 9932 KB Output is correct
6 Correct 13 ms 9940 KB Output is correct
7 Correct 14 ms 11476 KB Output is correct
8 Correct 17 ms 11720 KB Output is correct
9 Correct 15 ms 12116 KB Output is correct
10 Correct 17 ms 12132 KB Output is correct
11 Correct 29 ms 14448 KB Output is correct
12 Correct 35 ms 14484 KB Output is correct
13 Correct 19 ms 12196 KB Output is correct
14 Correct 19 ms 11336 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9940 KB Output is correct
2 Correct 16 ms 11596 KB Output is correct
3 Correct 16 ms 11464 KB Output is correct
4 Correct 13 ms 9428 KB Output is correct
5 Correct 13 ms 9932 KB Output is correct
6 Correct 13 ms 9940 KB Output is correct
7 Correct 14 ms 11476 KB Output is correct
8 Correct 17 ms 11720 KB Output is correct
9 Correct 15 ms 12116 KB Output is correct
10 Correct 17 ms 12132 KB Output is correct
11 Correct 29 ms 14448 KB Output is correct
12 Correct 35 ms 14484 KB Output is correct
13 Correct 19 ms 12196 KB Output is correct
14 Correct 19 ms 11336 KB Output is correct
15 Correct 17 ms 12140 KB Output is correct
16 Correct 17 ms 12116 KB Output is correct
17 Incorrect 100 ms 48952 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9428 KB Output is correct
2 Incorrect 74 ms 36028 KB Output isn't correct
3 Halted 0 ms 0 KB -